Re: iterators in sets - should they be const?

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.

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