[Effective-cpp] Item 22: Avoid in-place key modification in set and multiset

[Robert Haynes]

Item 22: Avoid in-place key modification in set and multiset

This item begins with Scott explaining that it's best not to directly
modify items in sets and multisets, because these items are stored
in sorted order, and modification could break the sortedness
constraint.  This isn't a problem with other associative containers
because, for a map<K,V> or multimap<K,V>, each element is
stored as a pair<const Key, Value> - i.e. the keys are declared const
and are not modifiable (except possibly with const_cast usage). But
items in set and multiset are not declared const, and are allowed to be
modified.

Scott provides an example of when direct modification might be
desirable,
by creating sets of Employee objects which have, among others, title and

EmployeeID data members. The objects are then stored in sorted order
based on the EmployeeID, and code is given to directly change an
employee's title.  The example seems simple enough, but provides a
reason for why objects aren't declared const.  Scott just warns heavily,

though, that changing the key part of the object could corrupt the
container and lead to undefined results.

Scott goes on to point out that some implementations have ways
of preventing direct modification on elements by having the operator*()
of a set<T>::Iterator return a const T&, so that modifications fail
because
of the const qualification. This also means that the example code
introduced
earlier would fail to compile with such implementations.  So code that
does
modify set elements isn't portable. Unless casts are used.  A workaround

shown for such implementations is to const_cast the object to a
non-const
reference and make the desired modification. But since casting can be
dangerous, and the same attempts, say on a map or multimap, may lead to
undefined behavior, a more general approach to element modification for
associative containers is given.

- locate the element to be changed
- make a copy of the element
- modify the copy
- remove the original element from the container
- insert the copy into the container

The last step can even be optimized, by inserting the element directly
in place
using the original iterator obtained in step one, since the keys of the
original and
modified elements are the same.

--------
Rob Haynes