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

[Robert Haynes]

Oops, sorry about the spacing.  Here's a clearer version.

Rob

--------------------

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