c++ - what happens when you modify an element of an std::set?

Question

If I change an element of an std::set, for example, through an iterator, I know it is not "reinserted" or "resorted", but is there any mention of if it triggers undefined behavior? For example, I would imagine insertions would screw up. Is there any mention of specifically what happens?

Answer 1

You should not edit the values stored in the set directly. I copied this from MSDN documentation which is somewhat authoritative:

The STL container class set is used for the storage and retrieval of data from a collection in which the values of the elements contained are unique and serve as the key values according to which the data is automatically ordered. The value of an element in a set may not be changed directly. Instead, you must delete old values and insert elements with new values.

Why this is is pretty easy to understand. The set implementation will have no way of knowing you have modified the value behind its back. The normal implementation is a red-black tree. Having changed the value, the position in the tree for that instance will be wrong. You would expect to see all manner of wrong behaviour, such as exists queries returning the wrong result on account of the search going down the wrong branch of the tree.

Answer 2

The precise answer is platform dependant but as a general rule, a "key" (the stuff you put in a set or the first type of a map) is suppose to be "immutable". To put it simply, that should not be modified, and there is no such thing as automatic re-insertion.

More precisely, the member variables used for to compare the key must not be modified.

Windows vc compiler is quite flexible (tested with VC8) and this code compile:

// creation
std::set<int> toto;
toto.insert(4);
toto.insert(40);
toto.insert(25);

// bad modif
(*toto.begin())=100;

// output
for(std::set<int>::iterator it = toto.begin(); it != toto.end(); ++it)
{
    std::cout<<*it<<" ";
}
std::cout<<std::endl;

The output is 100 25 40, which is obviously not sorted... Bad... Still, such behavior is useful when you want to modify data not participating in the operator <. But you better know what you're doing: that's the price you get for being too flexible.

Some might prefer gcc behavior (tested with 3.4.4) which gives the error "assignment of read-only location". You can work around it with a const_cast:

const_cast<int&>(*toto.begin())=100;

That's now compiling on gcc as well, same output: 100 25 40. But at least, doing so will probably makes you wonder what's happening, then go to stack overflow and see this thread :-)

Answer 3

You cannot do this; they are const. There exists no method by which the set can detect you making a change to the internal element, and as a result you cannot do so. Instead, you have to remove and reinsert the element. If you are using elements that are expensive to copy, you may have to switch to using pointers and custom comparators (or switch to a C++1x compiler that supports rvalue references, which would make things a whole lot nicer).