“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.  Does that refer to the iterator passed as the first argument, 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?

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?

—John