As one example, assume that we want to print the vector
after we call elimDups
(§ 10.2.3, p. 384). However, we’ll also assume that we want to see the words ordered by their size, and then alphabetically within each size. To reorder the vector
by length, we’ll use a second, overloaded version of sort
. This version of sort
takes a third argument that is a predicate.
A predicate is an expression that can be called and that returns a value that can be used as a condition. The predicates used by library algorithms are either unary predicates (meaning they have a single parameter) or binary predicates (meaning they have two parameters). The algorithms that take predicates call the given predicate on the elements in the input range. As a result, it must be possible to convert the element type to the parameter type of the predicate.
The version of sort
that takes a binary predicate uses the given predicate in place of <
to compare elements. The predicates that we supply to sort
must meet the requirements that we’ll describe in § 11.2.2 (p. 425). For now, what we need to know is that the operation must define a consistent order for all possible elements in the input sequence. Our isShorter
function from § 6.2.2 (p. 211) is an example of a function that meets these requirements, so we can pass isShorter
to sort
. Doing so will reorder the elements by size:
// comparison function to be used to sort by word length
bool isShorter(const string &s1, const string &s2)
{
return s1.size() < s2.size();
}
// sort on word length, shortest to longest
sort(words.begin(), words.end(), isShorter);
If words
contains the same data as in § 10.2.3 (p. 384), this call would reorder words
so that all the words of length 3 appear before words of length 4, which in turn are followed by words of length 5, and so on.
When we sort words
by size, we also want to maintain alphabetic order among the elements that have the same length. To keep the words of the same length in alphabetical order we can use the stable_sort
algorithm. A stable sort maintains the original order among equal elements.
Ordinarily, we don’t care about the relative order of equal elements in a sorted sequence. After all, they’re equal. However, in this case, we have defined “equal” to mean “have the same length.” Elements that have the same length still differ from one another when we view their contents. By calling stable_sort
, we can maintain alphabetical order among those elements that have the same length:
elimDups(words); // put words in alphabetical order and remove duplicates
// resort by length, maintaining alphabetical order among words of the same length
stable_sort(words.begin(), words.end(), isShorter);
for (const auto &s : words) // no need to copy the strings
cout << s << " "; // print each element separated by a space
cout << endl;
Assuming words
was in alphabetical order before this call, after the call, words
will be sorted by element size, and the words of each length remain in alphabetical order. If we run this code on our original vector
, the output will be
fox red the over slow jumps quick turtle
Exercise 10.11: Write a program that uses stable_sort
and isShorter
to sort a vector
passed to your version of elimDups
. Print the vector
to verify that your program is correct.
Exercise 10.12: Write a function named compareIsbn
that compares the isbn()
members of two Sales_data
objects. Use that function to sort
a vector
that holds Sales_data
objects.
Exercise 10.13: The library defines an algorithm named partition
that takes a predicate and partitions the container so that values for which the predicate is true
appear in the first part and those for which the predicate is false
appear in the second part. The algorithm returns an iterator just past the last element for which the predicate returned true
. Write a function that takes a string
and returns a bool
indicating whether the string
has five characters or more. Use that function to partition words
. Print the elements that have five or more characters.