iterators in sets - should they be const?
Andy Champ
conformance to the new 0x standard the types of set::iterator and
set::const_iterator are identical.
We have quite a bit of code that relies on being able to modify objects
in sets.
I'm pretty sure the idea is that a set falls in a big heap if you do
anything that modifies the key-ness of the objects. (all this of course
applies equally well to the key parts of a map).
IIRC the requirements for an object in a set is that operator< is
consistent; if a<b is true, then b<a is false. And it stays that way.
I'm sure that the logic behind this decision is that in order to ensure
the stability of the compares the objects should not change.
But I would argue that making the iterator const does not do this; such
a simple thing as having operator< refer to an embedded pointer, which
contains the real data to be compared, allows the set to get broken.
You just have to not do it.
And there can be lots of other data stored in a object which does not
affect operator<, and which you could quite validly want to change
without breaking the set - and now you can't.
With a const iterator you have to extract the object from the set (copy
construct, possibly rebalance the tree) fiddle with it, then put it back
(another copy construct, and possibly balance the tree again). This
can't be good!
This can't be a new discussion; can anyone tell me where it came up
originally?
Andy
Francesco S. Carta
> I've just got bitten by this in the new Visual Studio, where in
> conformance to the new 0x standard the types of set::iterator and
> set::const_iterator are identical.
That requirement is already in C++03 and I suppose in C++98 too.
The following is expected to work regardless of whether you declare the
iterator as const or not, and any attempt to modify a non-mutable data
member of a set key should halt the compilation process.
#include <iostream>
#include <set>
using namespace std;
struct Mutable {
int order;
mutable int data;
Mutable(int order = 0, int data = 0) : order(order), data(data) {};
};
bool operator<(const Mutable& lhs, const Mutable& rhs) {
return lhs.order < rhs.order;
}
int main() {
set<Mutable> s;
s.insert(Mutable());
s.insert(Mutable(1));
s.insert(Mutable(2));
s.insert(Mutable(3));
set<Mutable>::const_iterator it;
for(it = s.begin(); it != s.end(); ++it) {
it->data = it->order * 10 + 1;
cout << it->data << endl;
}
return 0;
}
> We have quite a bit of code that relies on being able to modify objects
> in sets.
And you must be doing that using "mutable" just like I did above.
Otherwise, your implementation would be non conforming.
--
FSC - http://userscripts.org/scripts/show/59948
http://fscode.altervista.org - http://sardinias.com
Bo Persson
It has been a long discussion (10 years :-) about the best solution.
None was really found!
The current position is that making the iterators const protects us
from accidentally modifying the key. Anyone believing that "I know
what I am doing" can use a const_cast to bypass the protection (and
suffer the consequences).
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#103
Bo Persson
Francesco S. Carta
> Andy Champ <no....@nospam.invalid>, on 08/09/2010 21:23:46, wrote:
>
>> I've just got bitten by this in the new Visual Studio, where in
>> conformance to the new 0x standard the types of set::iterator and
>> set::const_iterator are identical.
>
> That requirement is already in C++03 and I suppose in C++98 too.
Sorry, misrecalled that. In any case, mutable does the trick.
Joshua Maurice
> I've just got bitten by this in the new Visual Studio, where in
> conformance to the new 0x standard the types of set::iterator and
> set::const_iterator are identical.
>
> We have quite a bit of code that relies on being able to modify objects
> in sets.
Well, your code was always broken C++. With the new conformance, the
compiler now tells you its broken C++.
> I'm pretty sure the idea is that a set falls in a big heap if you do
> anything that modifies the key-ness of the objects. (all this of course
> applies equally well to the key parts of a map).
>
> IIRC the requirements for an object in a set is that operator< is
> consistent; if a<b is true, then b<a is false. And it stays that way.
Technically it's more than that. The standard requires it to be a
strict weak ordering (irreflexive, asymmetric, transitive, and the
resulting equality relation is transitive), but I think you get the
idea.
http://en.wikipedia.org/wiki/Strict_weak_ordering
> I'm sure that the logic behind this decision is that in order to ensure
> the stability of the compares the objects should not change.
>
> But I would argue that making the iterator const does not do this; such
> a simple thing as having operator< refer to an embedded pointer, which
> contains the real data to be compared, allows the set to get broken.
> You just have to not do it.
Yes. The user could also typecast away the const and modify it as
well. The basic idea is that people will program in a sane manner,
with const correct classes, so that your example case should not
arise. The standard library containers are meant to cater to the
common use case, and to facilitate writing correct code, not cover all
possible corner cases.
> And there can be lots of other data stored in a object which does not
> affect operator<, and which you could quite validly want to change
> without breaking the set - and now you can't.
Use std::map. You can
1- Partition the class into two separate classes, the key object and
value class.
2- Duplicate the operator< relevant data into a new key class.
3- Or some other scheme.
> With a const iterator you have to extract the object from the set (copy
> construct, possibly rebalance the tree) fiddle with it, then put it back
> (another copy construct, and possibly balance the tree again). This
> can't be good!
>
> This can't be a new discussion; can anyone tell me where it came up
> originally?
I would suggest looking at using std::map as described above. If you
actually need a container where you change the current operator< key
and require the guy outside the container to "know" that he hasn't
changed the ordering of the contained elements, then std::map and
std::set are not for you.
Leigh Johnston
"Andy Champ" <no....@nospam.invalid> wrote in message
news:1-mdnWrlfshMbRrR...@eclipse.net.uk...
I deal with this issue here: http://www.i42.co.uk/stuff/mutable_set.htm
/Leigh
Howard Hinnant
Others have already answered the state of affairs and the best
workaround today. I'm posting to explore an option for the future
(after C++0X).
I have a suggested addition to the map/set interface in the 2009-09-19
comment of LWG 839 (http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-
closed.html#839):
typedef details node_ptr;
node_ptr remove(const_iterator p);
pair<iterator, bool> insert(node_ptr&& nd);
iterator insert(const_iterator p, node_ptr&& nd);
This would allow you to change a value in set by first extracting it,
without erasing the node that is holding the value, modifying the
value (still held by the node) outside of the set, and then
reinserting the node into the set (having the set accept the external
node, instead of allocating a new one). If one didn't modify the
sorting order, one could even use the insert-with-hint so that the
insertion didn't have to search:
auto p = s.remove(i++);
p.modify();
s.insert(i, std::move(p));
The whole operation is exception safe. The remove can not throw. If
the p.modify() throws, the set is unaffected in the sense that the
node pointed to by i is already removed. The insert should be
noexcept(true) as there is no allocation.
I'm posting to gather comments on this possible (and future)
modification to the API of (multi)set/map.
Yes, it has been implemented.
-Howard
Leigh Johnston
"Howard Hinnant" <howard....@gmail.com> wrote in message
news:7919f63d-0f0d-4b57...@z25g2000vbn.googlegroups.com...
What if some exception is thrown between the remove and the insert?
Wouldn't the node leak as it is not currently owned by anything? You would
have to use RAII *and* the set's allocator to ensure proper deallocation,
this and exposing node implementation detail seems a bit pants to me. Did
you read my alternative solution of augmenting std::map's interface?
http://www.i42.co.uk/stuff/mutable_set.htm
/Leigh
Howard Hinnant
> "Howard Hinnant" <howard.hinn...@gmail.com> wrote in message
> > auto p = s.remove(i++);
> > p.modify();
> > s.insert(i, std::move(p));
I have a type-o here. I should have written:
auto p = s.remove(i++);
p->modify();
s.insert(i, std::move(p));
(i.e. "->" instead of ".") This assumes that the value_type of the
set has a non-const modify() member. One could also write:
*p = T(some_new_value);
where T is std::set<T>. Sorry for the type-o. That clearly
obfuscated my intent.
> > The whole operation is exception safe. The remove can not throw. If
> > the p.modify() throws, the set is unaffected in the sense that the
> > node pointed to by i is already removed. The insert should be
> > noexcept(true) as there is no allocation.
>
> What if some exception is thrown between the remove and the insert?
> Wouldn't the node leak as it is not currently owned by anything? You would
> have to use RAII *and* the set's allocator to ensure proper deallocation,
> this and exposing node implementation detail seems a bit pants to me.
"p" has type:
std::set<T>::node_ptr;
This node_ptr is "unique_ptr-like". It has unique ownership of the
node and contains a reference to the set's allocator so that it can
deallocate it. If p->modify() throws, p.~node_ptr() destructs the
value_type and deallocates the node. p is a smart pointer that
dereferences the node's value_type, not the node itself. So node
details are not exposed. Only the node's value_type is exposed, and
in a "const-free" manner.
More details here:
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839
under the comment that begins with:
[ 2009-09-19 Howard adds: ]
> Did
> you read my alternative solution of augmenting std::map's interface?http://www.i42.co.uk/stuff/mutable_set.htm
Yes. Thank you for sharing it. It seems like a good alternative,
especially for the short term. It can be used today.
-Howard
Andy Champ
haven't seen your post.
On 08/09/2010 22:17, Bo Persson wrote:
>
> It has been a long discussion (10 years :-) about the best solution.
> None was really found!
>
I can see that!
> The current position is that making the iterators const protects us
> from accidentally modifying the key. Anyone believing that "I know
> what I am doing" can use a const_cast to bypass the protection (and
> suffer the consequences).
>
Ah, but that's my point.
Making the iterators const protects you _only_ if you have a simple key,
which doesn't refer to any external data.
It's quite easy to have a key object that references some external data
that would alter the operation of its operator<(). So making the
iterator const does not give proper protection.
But on the other hand if you have a value object as your key, and not
all the data in the object is used for key operations, you cannot easily
alter that data.
So it stops you doing some things you should be allowed to; and it
doesn't stop you doing some things you shouldn't be allowed to.
> http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#103
>
If the committee is coming out with documents like that...
... actually, thinking back, I've been on standards committees, and
that's quite typical.
I note the following discussion point:
"Disallowing user modification of keys by changing the standard to
require an iterator for associative container to be the same as
const_iterator would be overkill since that will unnecessarily
significantly restrict the usage of associative container."
and then the following proposed resolution: "... It is unspecified
whether or not iterator and const_iterator are the same type."
Francesco,
We may well end up with something like your mutable structure. Or just
pull out the raw pointer, and const_cast it so we can fiddle with it.
Or something, in several dozen places :(
Which of course means that the structure is genuinely mutable, even if
we have a const pointer to it.
I'd have preferred a situation that gave me flexibility over inadequate
protection. Ah well, I have to live with it!
Andy
tni
> We may well end up with something like your mutable structure. Or just
> pull out the raw pointer, and const_cast it so we can fiddle with it.
Using the const_cast would be a good recipe for getting miscompiled code.
Seungbeom Kim
>
> Yes. The user could also typecast away the const and modify it as
> well. The basic idea is that people will program in a sane manner,
> with const correct classes, so that your example case should not
> arise. The standard library containers are meant to cater to the
> common use case, and to facilitate writing correct code, not cover all
> possible corner cases.
Simple value types being used as keys are a common case, but definitely
not "the" common use case, though they are surely the simplest case.
Entity types are also common, not just corner cases, but they are
under-served by the current standard containers.
> Use std::map. You can
> 1- Partition the class into two separate classes, the key object and
> value class.
> 2- Duplicate the operator< relevant data into a nebw key class.
> 3- Or some other scheme.
I can hardly imagine any sane design would partition a self-contained
entity class into the key and "the others"; e.g. would you have a person
class with the name used as the key removed? I would not. (Except when
the key was not a part of the entity in the first place, of course, in
which case you wouldn't have tried std::set either.) A major downside
is that it cuts the access to the key from "the others" part.
So what most people would do is to duplicate the key part, which is
certainly wasteful and worse than what could be done ideally.
Std::map is meant for mappings (of A to B, where A and B are separate)
and works best when used for such. They are different from sets.
I wish the standard exposed the internal data structure that both
std::set and std::map are built on, so that I don't have to write
everything from scratch when neither is exactly right for my needs.
http://groups.google.com/group/comp.lang.c++.moderated/msg/6cfe7cf0bc34d791
--
Seungbeom Kim
Seungbeom Kim
>
> Making the iterators const protects you _only_ if you have a simple key,
> which doesn't refer to any external data.
>
> It's quite easy to have a key object that references some external data
> that would alter the operation of its operator<(). So making the
> iterator const does not give proper protection.
>
> But on the other hand if you have a value object as your key, and not
> all the data in the object is used for key operations, you cannot easily
> alter that data.
>
> So it stops you doing some things you should be allowed to; and it
> doesn't stop you doing some things you shouldn't be allowed to.
Ah, that's too bad.
This seems against one of the C++ language design rules (described in D&E):
"It is more important to allow a useful feature than to prevent every misuse."
--
Seungbeom Kim
Andy Champ
>
> We may well end up with something like your mutable structure. Or just
> pull out the raw pointer, and const_cast it so we can fiddle with it. Or
> something, in several dozen places :(
>
> Which of course means that the structure is genuinely mutable, even if
> we have a const pointer to it.
>
> I'd have preferred a situation that gave me flexibility over inadequate
> protection. Ah well, I have to live with it!
>
> Andy
Just re-visiting this. Of course, we _don't_ have to live with it at
all. I just have to invent my own set class.
Of course we want it to look just like the ordinary set - so it inherits
from it. It isn't intended to be a complete implementation, just good
enough for our needs.
So far we've had to override iterator and reverse_iterator; the new
classes have copy constructors from the std::set::iterator/
reverse_iterator, default constructors, and replacement operator* and
operator-> functions. These last two methods contain const_cast on the
returned data from the base type.
The new set class has a construct empty method (we haven't needed the
others yet) and overrides for begin, end, rbegin, rend, insert and find.
I dare say new methods will be added as we need them :)
Andy
Leigh Johnston
"Andy Champ" <no....@nospam.invalid> wrote in message
news:CsGdnf1XSdWE4gfR...@eclipse.net.uk...
Sounds horrid, did you not read http://www.i42.co.uk/stuff/mutable_set.htm?
My solution does not require a const_cast which is the least desirable
workaround.
/Leigh
Brian Wood
>
I wrote an article in support of that some time back --
http://webEbenezer.net/take4. Since then Boost Intrusive
has been developed and it has an rbtree class that I find
helpful.
Brian Wood
Ebenezer Enterprises
http://webEbenezer.net
www.wnd.com