Algorithms, Containers, and Iterators
There is a fact that is crucial to understand in using algorithms, iterators, and containers:
The sort, remove_if, and partition functions all move elements to new positions in the underlying container, but they do not change the properties of the container itself. For example, remove_if does not change the size of the container on which it operates; it merely copies elements around within the container.
This distinction is especially important in understanding how algorithms interact with the containers that they use for output. Let's look in more detail at our use of remove_if. As we've seen, the call
remove_if(students.begin(), students.end(), fgrade)
did not change the size of students. Rather, it copied each element for which the predicate was false to the beginning of students and left the rest of the elements alone. When we need to shorten the vector to discard those elements, we must do so ourselves.
In our example, we said
students.erase(remove_if(students.begin(), students.end(), fgrade), students.end());
Here, erase changes the vector by removing the sequence indicated by its arguments. This call to erase shortens students so that it contains only the elements we want. Note that erase must be a member of vector because it acts directly on the container, not just on its elements.
Similarly, it is important to be aware of the interaction between iterators and algorithms, and between iterators and container operations. We've already seen that container operations such as erase and insert invalidate the iterator for the element erased. More important, in the case of vectors and strings, operations such as erase or insert also invalidate any iterator denoting elements after the one erased or inserted. Because these operations can invalidate iterators, we must be careful about saving iterator values if we are using these operations.
Similarly, functions such as partition or remove_if, which can move elements around within the container, will change which element is denoted by particular iterators. After running one of these functions, we cannot rely on an iterator continuing to denote a specific element.