intvec_iter e = ivec.end();
for (intvec_iter i = ivec.begin(); i != e; i++)
if (p(*i))
ivec.erase(i)
does not work correctly. Does the code
for (int i = ivec.size() - 1; i >= 0; i--)
if (p(ivec[i]))
ivec.erase(ivec.begin() + i)
work correctly? Explain.
The first example doesn't work correctly because the iterator ivec.end()
is invalidated every time ivec has an element is inserted or deleted. The
iterator stored in e becomes invalid after the first erasure, after which
the meaning of the comparison i != e becomes undefined.
The second example tries to avoid the problems of the first example in two ways: by using indices instead of iterators and by working backward through the vector. The correctness of this approach can be seen by considering the loop invariant
ivec[0 .. i] have not yet been processed.
By setting i to one less than the length of ivec, the invariant is
initially true. Each iteration of the for statement processes element i
and then decreases i by one, so the invariant is re-established at the end
of each iteration. (If you're having trouble seeing the invariant, try
re-implementing the for statement as a while statement.)
The truth of the invariant gives us the correctness argument. Because none of
the elements from 0 to i have been processed yet, the value of i
is a legitimate index value and the value ivec[i] is a valid element of
the vector.
Note the invariant doesn't say anything about whether or not the code is
operating on ivec correctly; it just says that the code isn't operating on
ivec incorrectly.
What do you think of your colleague's proposal. Explain.
Functions that remove elements from a container have to be member functions of the associated container class; how an element is removed from a linked list is different from how an element is removed from a vector.
Given an iterator, it is not possible to figure out from which particular container instance the iterator came. (This is only generally true; the standard doesn't require this behavior, although it may be possible to extend the STL code to allow for it.) Because the generic algorithms manipulate containers via iterators, they can't remove elements from containers using only the iterators from those containers. (Iterator adaptors are not iterators, but rather functions (actually classes) that behave like iterators and keep, among other things, information about the container from which the iterators are being derived.)
It seems your colleague got one right.
partition(s, e, p) and a stable_partition(s, e, p) generic
algorithms.
Given an iterator range and a predicate, a partition shuffles the contents of the iterator range so that all the elements in the range for which the predicate is true appear before all the elements in the range for which the predicate is false. A stable partition behaves the same as a partition with one additional feature: a stable partition preserves the relative orders of the elements in the two parts of the partition.
The code
int i; vector<int> ivec; for (i = 0; i < 10; i++) ivec.push_back(i); vector<int> iv = ivec; cout << "before partition(), "; for (i = 0; i < 10; i++) cout << " " << iv[i]; cout << "\n"; partition(iv.begin(), iv.end(), odd); cout << "after partition(), "; for (i = 0; i < 10; i++) cout << " " << iv[i]; cout << "\n"; iv = ivec; cout << "before stable_partition(), "; for (i = 0; i < 10; i++) cout << " " << iv[i]; cout << "\n"; stable_partition(iv.begin(), iv.end(), odd); cout << "after stable_partition(), "; for (i = 0; i < 10; i++) cout << " " << iv[i]; cout << "\n";
demonstrates the difference by printing
before partition(), 0 1 2 3 4 5 6 7 8 9 after partition(), 9 1 7 3 5 4 6 2 8 0 before stable_partition(), 0 1 2 3 4 5 6 7 8 9 after stable_partition(), 1 3 5 7 9 0 2 4 6 8
when executed.
This answer is not entirely correct. What's wrong?
remove() generic algorithms are
unfortunately named. Explain why.
The remove() generic algorithms are unfortunately named because they don't
remove anything; they just shuffle elements around in the iterator range.
This page last modified on 24 October 2001.