Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Mutable objects for std::set
192 views
Skip to first unread message
Kaba
Nov 23, 2011, 11:10:50 AM11/23/11
to
Hi,
Let f be a function (in the mathematical sense) mapping objects of type
Type to a totally ordered set (for simplicity), called keys. By this
ordering, std::set is able to organize data of type Type in an efficient
way to enable fast associative searching, insertion and removal (e.g. by
a red-black tree). An essential requirement for this to be possible is
that the key associated to each object remains unchanged when stored in
std::set. Otherwise invariants of underlying data structures could be
easily broken (e.g. binary search property of a red-black tree).
As a principle of programming, if there is ever an invariant, then that
invariant must be checked automatically by the compiler, or by the
library at runtime (function preconditions, assertions). There are
exceptions, of course, when other priorities conflict, such as
performance or memory use (e.g. checking if iterators are part of the
same container).
As a good example of programming, the std::set enforces the invariant of
unchanging keys, by making all external references to its objects const.
This makes sure that changing a key does not happen by accident. On the
other hand, this decision conflicts with genericity. I often find myself
dealing with objects whose state can, and should, be freely changed
without affecting their associated key. There are several hacks that can
be used to work around this problem:
1) The first hack is to use the mutable keyword in the Type's member
variables. However, this would be incorrect when the member variable is
part of the logical state of the object (compared to just physical
state, which can include additional cache variables).
2) The second hack is to use const_cast for the object to gain access to
modifying its state. This is more correct. However, const_cast exists
only to correct for the mistakes done in the past (and for some tricks
to avoid code replication in const/non-const pair of member functions).
3) The third hack is to change to use std::map instead, by separating
the key to its own object, and then associating it with the rest of the
object. However, this is not always sufficient. The problem is that now
the key is not accessible from the value object. Where this is a
problem, the key must be duplicated to the value type. Interestingly,
the key in the value object is now in danger of being modified different
to the key in the key object.
The best practical approach at the moment, in my opinion, is to use the
second hack of const_cast.
The conflict in genericity is caused by the following problem:
The enforcement of the references to objects of std::set to const
is too strict.
The core of this claim is in that it should only be the associated key
of the object which should be protected from change, and not the whole
object. The latter is usually a sufficient condition for the former (one
can make up situations where this does not hold, such as keys retrieved
by reference from somewhere else). However, it is not a necessary
condition.
I now wonder what other ways there would be to enforce unchanging keys
in std::set, which would allow for changing the other unrelated state of
the object.
An obvious solution would be to remove the constness of the references
completely. However, this would open up a very probable source of bugs,
where the novices change the elements arbitrarily. And not only the
novices; since this goes against the principle of checking invariants,
it would open the door to Murphy's law (it will happen by accident also
to professionals). Thus I don't see this as an option.
Of course, the same problem concerns std::unordered_set also.
I don't know whether there is a better solution to the problem than the
current one + const_cast. However, at least the problem has now been
formulated.
What are your thoughts?
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Let f be a function (in the mathematical sense) mapping objects of type
Type to a totally ordered set (for simplicity), called keys. By this
ordering, std::set is able to organize data of type Type in an efficient
way to enable fast associative searching, insertion and removal (e.g. by
a red-black tree). An essential requirement for this to be possible is
that the key associated to each object remains unchanged when stored in
std::set. Otherwise invariants of underlying data structures could be
easily broken (e.g. binary search property of a red-black tree).
As a principle of programming, if there is ever an invariant, then that
invariant must be checked automatically by the compiler, or by the
library at runtime (function preconditions, assertions). There are
exceptions, of course, when other priorities conflict, such as
performance or memory use (e.g. checking if iterators are part of the
same container).
As a good example of programming, the std::set enforces the invariant of
unchanging keys, by making all external references to its objects const.
This makes sure that changing a key does not happen by accident. On the
other hand, this decision conflicts with genericity. I often find myself
dealing with objects whose state can, and should, be freely changed
without affecting their associated key. There are several hacks that can
be used to work around this problem:
1) The first hack is to use the mutable keyword in the Type's member
variables. However, this would be incorrect when the member variable is
part of the logical state of the object (compared to just physical
state, which can include additional cache variables).
2) The second hack is to use const_cast for the object to gain access to
modifying its state. This is more correct. However, const_cast exists
only to correct for the mistakes done in the past (and for some tricks
to avoid code replication in const/non-const pair of member functions).
3) The third hack is to change to use std::map instead, by separating
the key to its own object, and then associating it with the rest of the
object. However, this is not always sufficient. The problem is that now
the key is not accessible from the value object. Where this is a
problem, the key must be duplicated to the value type. Interestingly,
the key in the value object is now in danger of being modified different
to the key in the key object.
The best practical approach at the moment, in my opinion, is to use the
second hack of const_cast.
The conflict in genericity is caused by the following problem:
The enforcement of the references to objects of std::set to const
is too strict.
The core of this claim is in that it should only be the associated key
of the object which should be protected from change, and not the whole
object. The latter is usually a sufficient condition for the former (one
can make up situations where this does not hold, such as keys retrieved
by reference from somewhere else). However, it is not a necessary
condition.
I now wonder what other ways there would be to enforce unchanging keys
in std::set, which would allow for changing the other unrelated state of
the object.
An obvious solution would be to remove the constness of the references
completely. However, this would open up a very probable source of bugs,
where the novices change the elements arbitrarily. And not only the
novices; since this goes against the principle of checking invariants,
it would open the door to Murphy's law (it will happen by accident also
to professionals). Thus I don't see this as an option.
Of course, the same problem concerns std::unordered_set also.
I don't know whether there is a better solution to the problem than the
current one + const_cast. However, at least the problem has now been
formulated.
What are your thoughts?
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Daniel Krügler
Nov 24, 2011, 3:50:43 AM11/24/11
to
On 2011-11-23 17:10, Kaba wrote:
[..]
I'm not sure whether I really grasp what you are saying here. But I
think that associate/unordered containers are indeed over constraining.
This is my main complaint expressed in the first part of
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#1214
Is this what you are referring to?
The reason why I'm strongly in favour for fixing this is, because the
current wording basically only allows approach (1), because approach (2)
as a feasible way to modify keys of such containers in a controlled way
is based on the assumption that the underlying object is not const. If
it were, the usage of const_cast would cause undefined behaviour.
I don't think that the actual intention was to reject path (2) and I
would like to have this path re-enabled.
In regard to your comparison of such associative containers with other
containers: IMO it is a myth to expect that you can replace different
container with each other without the potential need of adapting your
code. I think any modification attempt to the key property of
associative/unordered containers should be rejected during compile-time
unless you use an explicit tool for it.
Assuming #1214 becomes fixed, a controlled const_cast looks like the
right way for it. If you don't like const_cast in your code, I suggest
to add a helper function (template) with a proper name that clearly
signals the modification attempt, like
make_my_key_mutable_because_I_told_you_so ;-)
HTH & Greetings from Bremen,
Daniel Krügler
--
[..]
think that associate/unordered containers are indeed over constraining.
This is my main complaint expressed in the first part of
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#1214
Is this what you are referring to?
The reason why I'm strongly in favour for fixing this is, because the
current wording basically only allows approach (1), because approach (2)
as a feasible way to modify keys of such containers in a controlled way
is based on the assumption that the underlying object is not const. If
it were, the usage of const_cast would cause undefined behaviour.
I don't think that the actual intention was to reject path (2) and I
would like to have this path re-enabled.
In regard to your comparison of such associative containers with other
containers: IMO it is a myth to expect that you can replace different
container with each other without the potential need of adapting your
code. I think any modification attempt to the key property of
associative/unordered containers should be rejected during compile-time
unless you use an explicit tool for it.
Assuming #1214 becomes fixed, a controlled const_cast looks like the
right way for it. If you don't like const_cast in your code, I suggest
to add a helper function (template) with a proper name that clearly
signals the modification attempt, like
make_my_key_mutable_because_I_told_you_so ;-)
HTH & Greetings from Bremen,
Daniel Krügler
--
Martin B.
Nov 24, 2011, 3:40:52 PM11/24/11
to
On 23.11.2011 17:10, Kaba wrote:
> Hi,
>
> ...
make sense to wrap the type in something that can be put into the set
instead of the type. This wrapper would only allow the appropriate
modifications (possibly via const_cast or mutable).
I have to admit though that I'm out of luck thinking of how/if this
could be generically implemented in a sane way. :-)
cheers,
Martin
--
I'm here to learn, you know.
Just waiting for someone,
to jump from the shadows,
telling me why I'm wrong.
> Hi,
>
> ...
>
> As a good example of programming, the std::set enforces the invariant of
> unchanging keys, by making all external references to its objects const.
> This makes sure that changing a key does not happen by accident. On the
> other hand, this decision conflicts with genericity. I often find myself
> dealing with objects whose state can, and should, be freely changed
> without affecting their associated key. There are several hacks that can
> be used to work around this problem:
>
> 1) The first hack is to use the mutable keyword in the Type's member
> variables. ...
> As a good example of programming, the std::set enforces the invariant of
> unchanging keys, by making all external references to its objects const.
> This makes sure that changing a key does not happen by accident. On the
> other hand, this decision conflicts with genericity. I often find myself
> dealing with objects whose state can, and should, be freely changed
> without affecting their associated key. There are several hacks that can
> be used to work around this problem:
>
> 1) The first hack is to use the mutable keyword in the Type's member
>
> 2) The second hack is to use const_cast for the object to gain access to
> modifying its state. This is more correct. ...
> 2) The second hack is to use const_cast for the object to gain access to
>
> 3) The third hack is to change to use std::map instead, by separating
> the key to its own object, and then associating it with the rest of the
> object. However, this is not always sufficient. ...
> 3) The third hack is to change to use std::map instead, by separating
> the key to its own object, and then associating it with the rest of the
>
> The best practical approach at the moment, in my opinion, is to use the
> second hack of const_cast.
>
>...
> The best practical approach at the moment, in my opinion, is to use the
> second hack of const_cast.
>
> Of course, the same problem concerns std::unordered_set also.
>
> I don't know whether there is a better solution to the problem than the
> current one + const_cast. However, at least the problem has now been
> formulated.
>
> What are your thoughts?
>
Maybe for types that have a "key part" and a "non-key part" it might
>
> I don't know whether there is a better solution to the problem than the
> current one + const_cast. However, at least the problem has now been
> formulated.
>
> What are your thoughts?
>
make sense to wrap the type in something that can be put into the set
instead of the type. This wrapper would only allow the appropriate
modifications (possibly via const_cast or mutable).
I have to admit though that I'm out of luck thinking of how/if this
could be generically implemented in a sane way. :-)
cheers,
Martin
--
I'm here to learn, you know.
Just waiting for someone,
to jump from the shadows,
telling me why I'm wrong.
piotrN
Nov 24, 2011, 3:46:44 PM11/24/11
to
Hi,
I can imagine the 4th hack - more elegant, generic and no intrusive
(in my opinion ;).
Assuming that you have object with the key that is not changeable -
like this:
class myobject {
public:
myobject(int key, int value) : itsKey(key), itsValue(value) {}
int key() const { return itsKey; }
void setValue(int value) { itsValue = value; }
int value() const { return itsValue; }
private:
int itsKey;
int itsValue;
};
class myobject_compare_bykey : public std::binary_function<myobject ,
myobject, bool> {
public:
bool operator()(const myobject& l, const myobject& r) const
{
return l.key() < r.key();
}
};
And I understand that your issue here is that in std::set<myobject,
myobject_compare_bykey> you cannot call myobject::setValue - even if
changing this value would not impact the set of "myobject".
My 4th approach would be creating template like this one:
template <class _Key, class _Compare = std::less<_Key> >
class MutableKey {
public:
MutableKey (const _Key& key) : itsKey(key) {}
_Key& key() const { return itsKey; }
private:
mutable _Key itsKey;
_Compare itsCompare;
friend bool operator < (const MutableKey & l, const MutableKey & r)
{
return l.itsCompare(l.itsKey, r.itsKey);
}
};
With this template you are free to use myobject::setValue :
std::set<MutableKey <myobject, myobject_compare_bykey> > myobjectset;
myobjectset.insert(myobject(1, 101));
myobjectset.begin()->key().setValue(107); // no compilator
complaining
Full example here: http://www.ideone.com/c405Q
Regards,
PiotrN
--
(in my opinion ;).
Assuming that you have object with the key that is not changeable -
like this:
class myobject {
public:
myobject(int key, int value) : itsKey(key), itsValue(value) {}
int key() const { return itsKey; }
void setValue(int value) { itsValue = value; }
int value() const { return itsValue; }
private:
int itsKey;
int itsValue;
};
class myobject_compare_bykey : public std::binary_function<myobject ,
myobject, bool> {
public:
bool operator()(const myobject& l, const myobject& r) const
{
return l.key() < r.key();
}
};
And I understand that your issue here is that in std::set<myobject,
myobject_compare_bykey> you cannot call myobject::setValue - even if
changing this value would not impact the set of "myobject".
My 4th approach would be creating template like this one:
template <class _Key, class _Compare = std::less<_Key> >
class MutableKey {
public:
MutableKey (const _Key& key) : itsKey(key) {}
_Key& key() const { return itsKey; }
private:
mutable _Key itsKey;
_Compare itsCompare;
friend bool operator < (const MutableKey & l, const MutableKey & r)
{
return l.itsCompare(l.itsKey, r.itsKey);
}
};
With this template you are free to use myobject::setValue :
std::set<MutableKey <myobject, myobject_compare_bykey> > myobjectset;
myobjectset.insert(myobject(1, 101));
myobjectset.begin()->key().setValue(107); // no compilator
complaining
Full example here: http://www.ideone.com/c405Q
Regards,
PiotrN
--
0 new messages