10.2.3. Algorithms That Reorder Container Elements
Some algorithms rearrange the order of elements within a container. An obvious example of such an algorithm is sort. A call to sort arranges the elements in the input range into sorted order using the element type’s < operator.
As an example, suppose we want to analyze the words used in a set of children’s stories. We’ll assume that we have a vector that holds the text of several stories. We’d like to reduce this vector so that each word appears only once, regardless of how many times that word appears in any of the given stories.
For purposes of illustration, we’ll use the following simple story as our input:
the quick red fox jumps over the slow red turtle
Given this input, our program should produce the following vector:
Exercises Section 10.2.2
Exercise 10.6: Using fill_n, write a program to set a sequence of int values to 0.
Exercise 10.7: Determine if there are any errors in the following programs and, if so, correct the error(s):
(a)
vector<int> vec; list<int> lst; int i;
while (cin >> i)
lst.push_back(i);
copy(lst.cbegin(), lst.cend(), vec.begin());
(b)
vector<int> vec;
vec.reserve(10); // reserve is covered in § 9.4 (p. 356)
fill_n(vec.begin(), 10, 0);
Exercise 10.8: We said that algorithms do not change the size of the containers over which they operate. Why doesn’t the use of back_inserter invalidate this claim?
Eliminating Duplicates
To eliminate the duplicated words, we will first sort the vector so that duplicated words appear adjacent to each other. Once the vector is sorted, we can use another library algorithm, named unique, to reorder the vector so that the unique elements appear in the first part of the vector. Because algorithms cannot do container operations, we’ll use the erase member of vector to actually remove the elements:
void elimDups(vector<string> &words)
{
// sort words alphabetically so we can find the duplicates
sort(words.begin(), words.end());
// unique reorders the input range so that each word appears once in the
// front portion of the range and returns an iterator one past the unique range
auto end_unique = unique(words.begin(), words.end());
// erase uses a vector operation to remove the nonunique elements
words.erase(end_unique, words.end());
}
The sort algorithm takes two iterators denoting the range of elements to sort. In this call, we sort the entire vector. After the call to sort, words is ordered as
Note that the words red and the appear twice.
Using unique
Once words is sorted, we want to keep only one copy of each word. The unique algorithm rearranges the input range to “eliminate” adjacent duplicated entries, and returns an iterator that denotes the end of the range of the unique values. After the call to unique, the vector holds
The size of words is unchanged; it still has ten elements. The order of those elements is changed—the adjacent duplicates have been “removed.” We put remove in quotes because unique doesn’t remove any elements. Instead, it overwrites adjacent duplicates so that the unique elements appear at the front of the sequence. The iterator returned by unique denotes one past the last unique element. The elements beyond that point still exist, but we don’t know what values they have.
NoteThe library algorithms operate on iterators, not containers. Therefore, an algorithm cannot (directly) add or remove elements.
Using Container Operations to Remove Elements
To actually remove the unused elements, we must use a container operation, which we do in the call to erase (§ 9.3.3, p. 349). We erase the range of elements from the one to which end_unique refers through the end of words. After this call, words contains the eight unique words from the input.
It is worth noting that this call to erase would be safe even if words has no duplicated words. In that case, unique would return words.end(). Both arguments to erase would have the same value: words.end(). The fact that the iterators are equal would mean that the range passed to erase would be empty. Erasing an empty range has no effect, so our program is correct even if the input has no duplicates.