CS 509 Test 3

CS 509, Advanced Programming II

Fall 2001 - Test 3

Explain why the code
```
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
```
ivec_iter b = ivec.begin()
for (ivec_iter i = ivec.end() - 1; i != b; i--)
  if (p(*i))
    ivec.erase(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 seems like a cleaver fix for the first example. The iterator ivec.begin() can't become invalid because all the elements being deleted are after it in ivec. Deleting from back to front makes sure that b always refers to a valid iterator.
Unfortunately, the second example still has an invalidation problem, this time with the interator stored in i. If p(*i) is true then the element referenced by i is erased, which invalidates i. Once i is invalidated, the operation i++ has undefined behavior. The second example doesn't work correctly either.
A colleage of yours is confused about which generic algorithms can change the size of a container. When you suggest that algorithms that take only iterators cannot change the associated container's size, your colleage counters with the splice() function. Explain your response.
You colleague is correct in that the splice() function does accept iterators and does change the size of containers. However, you colleague is wrong in asserting that splice() is a generic algorithm; it is a member function of the list class.
Explain the the difference between a partition and a stable partition.
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. That is, if element x appears to the left of element y before the stable partition, and the predicate is true (for example) for both x and y, then x appears to the left of y in the true part of the partition; a similar arrangement holds if the predicate is false for both elements.
For example, if the iterator range specifies the value sequence
```
1, 2, 3, 4, 5, 6
```
and the predicate is odd(), then
```
5, 3, 1, 4, 2, 6
```
is a valid partition of the range but an invalid stable partition because, for example, 3 appears to the left of 5 in the original range but appears to the right of 5 when both are in the same part of the partition (the fact that 2 and 3 are also reversed is not important because the don't appear in the same part of the partition).
```
1, 3, 5, 2, 4, 6
```
is the valid stable partition.
Write a small code example showing why the remove(s, e, v) algorithm is misnamed.
remove() is misnamed because it doesn't remove anything; it just shuffles elements around in the iterator range. The following bit of code
```
vector ivec(10, 0);
cout << "before remove(), ivec.size() = " << ivec.size() << "\n";
remove(ivec.begin(), ivec.end(), 0);
cout << "after remove(), ivec.size() = " << ivec.size() << "\n";
```
demonstrates this by printing
```
before remove(), ivec.size() = 10
after remove(), ivec.size() = 10
```
when executed. If remove() actually removed elements from the range, then ivec would be empty after the call.

This page last modified on 24 October 2001.