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
:
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?
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.
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.
The library algorithms operate on iterators, not containers. Therefore, an algorithm cannot (directly) add or 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.