John M. Dlugosz writes:

“replace performs this substitution in such a manner that: … Iterator and reference validity are preserved.” I suppose "Iterator validity is preserved" means that no iterators are invalidated by this operation. 

Correct.

Does that refer to the iterator passed as the first argument, too? 

Too.

That is, the iterator that referred to the replaced element now refers to the new element?  And other indexes' iterators referring to the same element (e.g. project()) too?  That might still be "valid" in the STL sense but might not continue to work if the position changed (e.g. it is now past the end of the range you are following).  That's presuming the changed (but still "valid") iterator follows the new sort order rather than remembering the original order.  Can someone clarify?

After modifying x, iterators pointing to x will still point to the same element, even if x gets resorted to a different position. This induces this typical problem: for(it=...,end=...,it!=end;++it){ c.replace(it,...); } After replacing, it will move around and can even lie past last. This can be remedied (in some ocassions) as follows: for(it=...,end=...,it!=end;){ c.replace(it++,...); } See? We increment it to the next element *before* replacing so as to ensure that we visit the whole range. But there's still has a potential problem: elements can be visited twice. Suppose the range is a b c d e f with it pointing to b, and suppose after replacing b the range looks like a c d e b f so that b will be visited again. If that's your case, take a look at http://lists.boost.org/boost-users/2006/03/18048.php where a solution is proposed.

My original reason for writing was to as what is meant by "reference validity is preserved"?  Does that mean that the address of the items stored in the collection are not changed, and never move around as a result of this operation?

Pointers and references to an element point (refer) to the same element after replacing, just like iteratorts. Not sure if this answers your question. Joaquín M López Muñoz Telefónica Digital