10.3.1. Passing a Function to an Algorithm

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.

Predicates

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.

Sorting Algorithms

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