Does a vector sort invalidate iterators?

Question

 std::vector<string> names;
 std::vector<string>::iterator start = names.begin();
 std::vector<string>::iterator end = names.end();
 sort (start,end);
 //are my start and end valid at this point?
 //or they do not point to front and tail resp?

Answer 1

They still point to the beginning and end. The values in those slots of the vector have probably changed, but the storage location in which each resides remains the same.

Answer 2

In short - yes.

Here are cases when iterators are getting invalidated in the std::vector:

• Memory will be reallocated automatically if more than capacity() - size() elements are inserted into the vector. Reallocation does not change size(), nor does it change the values of any elements of the vector. It does, however, increase capacity(), and it invalidates any iterators that point into the vector.
• A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector's iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end.

In case with re-allocation (capacity or size change), start iterator can change because realloc() could possibly return a new memory region due to fragmentation issues.

Obviously, sort cannot change the size of the vector or its capacity. But it can remove and insert elements from/into the middle. That will invalidate iterators. Are those special iterators being invalidated as well? It is implementation specific and I would not rely on that.

Answer 3

std::vector keeps its elements in contiguous memory. std::sort takes arguments (iterators) by value and re-arranges the sequence between them. The net result is your local variables start and end are still pointing to first and one-past-the-last elements of the vector.

Answer 4

std::sort will not invalidate iterators to a vector. The sort template uses the * operator on the iterators to access and modify the contents of the vector, and modifying a vector element though an iterator to an element already in the vector will not invalidate any iterators.

In summary,

• your existing iterators will not be invalidated
• however, the elements they point to may have been modified

In addition to the support for the standard provided by Kirill V. Lyadvinsky (http://stackoverflow.com/questions/3885482/does-a-vector-sort-change-iterators-if-i-have-start-and-end-before-sort/3885638#3885638):

• 25/5 "Algorithms library"

If an algorithm’s Effects section says that a value pointed to by any iterator passed as an argument is modified, then that algorithm has an additional type requirement: The type of that argument shall satisfy the requirements of a mutable iterator (24.1).

• 24.1/4 "Iterator requirements"

Besides its category, a forward, bidirectional, or random access iterator can also be mutable or constant depending on whether the result of the expression *i behaves as a reference or as a reference to a constant.