Mastering STL Algorithms and Function Objects

either unary_function or binary_function, depending on whether they take one or two arguments. These two classes, both defined in <functional>, are templatized on the parameter and return types of the “function” they provide. For example, instead of using ptr_fun() to convert isdigit(), you could write a wrapper function object like this:

#include <functional> #include <algorithm> #include <cctype> #include <string> using namespace std;

class myIsDigit : public unary_function<char, bool>

{

public:

bool operator() (char c) const { return (::isdigit(c)); }

};

bool isNumber(const string& str)

{

string::const_iterator it = find_if(str.begin(), str.end(), not1(myIsDigit()));

return (it == str.end());

}

Note that the overloaded function call operator of the myIsDigit class must be const in order to pass objects to find_if().

The algorithms are allowed to make multiple copies of function object predicates and call different ones for different elements. Thus, you shouldn’t write them such that they count on any internal state to the object being consistent between calls.

Algorithm Details

This chapter describes the general categories of algorithms, with examples of each. The Standard Library Reference resource on the Web site contains a summary of all the algorithms, but for nitty-gritty details, you should consult one of the books on the STL listed in Appendix B.

Recall from Chapter 21 that there are five types of iterators: input, output, forward, bidirectional, and random-access. There is no formal class hierarchy of these iterators, because the implementations for each container are not part of the standard hierarchy. However, one can deduce a hierarchy based on the functionality they are required to provide. Specifically, every random access iterator is also bidirectional, every bidirectional iterator is also forward, and every forward iterator is also input and output.

The standard way for the algorithms to specify what kind of iterators they need is to use the following names for the iterator template arguments: InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator, and RandomAccessIterator. These names are just names: they don’t provide binding type checking. Therefore, you could, for example, try to call an algorithm expecting a

631

Chapter 22

RandomAccessIterator by passing a bidirectional iterator. The template doesn’t do type checking, so it would allow this instantiation. However, the code in the function that uses the random access iterator capabilities would fail to compile on the bidirectional iterator. Thus, the requirement is enforced, just not where you would expect. The error message can therefore be somewhat confusing. For example, attempting to use the generic sort() algorithm, which requires a random access iterator, on a list, which provides only a bidirectional iterator, gives this error in g++:

/usr/include/c++/3.2.2/bits/stl_algo.h: In function `void std::sort(_RandomAccessIter, _RandomAccessIter) [with _RandomAccessIter = std::_List_iterator<int, int&, int*>]’:

Sorting.cpp:38: instantiated from here /usr/include/c++/3.2.2/bits/stl_algo.h:2178: no match for `

std::_List_iterator<int, int&, int*>& - std::_List_iterator<int, int&, int*>&’ operator

Don’t worry if you don’t understand this error yet. The sort() algorithm is covered later in this chapter.

Most of the algorithms are defined in the <algorithm> header file, but a few algorithms are located in <numeric>. They are all in the std namespace. See the Standard Library Reference resource on the Web site for details.

Utility Algorithms

The STL provides three utility algorithms implemented as function templates: min(), max(), and swap(). min() and max() compare two elements of any type with operator< or a user-supplied binary predicate, returning a reference to the smaller or larger element, respectively. swap() takes two elements of any type by reference and switches their values.

These utilities do not work on sequences of elements, so they do not take iterator parameters.

The following program demonstrates the three functions:

#include <algorithm> #include <iostream> using namespace std;

int main(int argc, char** argv)

{

int x = 4, y = 5;

cout << “x is “ << x << “ and y is “ << y << endl; cout << “Max is “ << max(x, y) << endl;

cout << “Min is “ << min(x, y) << endl; swap(x, y);

cout << “x is “ << x << “ and y is “ << y << endl; cout << “Max is “ << max(x, y) << endl;

cout << “Min is “ << min(x, y) << endl;

return (0);

}

632

Mastering STL Algorithms and Function Objects

Here is the program output:

x is 4 and y is 5 Max is 5

Min is 4

x is 5 and y is 4 Max is 5

Min is 4

Nonmodifying Algorithms

The nonmodifying algorithms include functions for searching elements in a range, generating numerical information about elements in a range, comparing two ranges to each other, and processing each element in a range.

Search Algorithms

You’ve already seen two examples of search algorithms: find() and find_if(). The STL provides several other variations of the basic find() algorithm that work on unsorted sequences of elements. adjacent_find() finds the first instance of two consecutive elements that are equal to each other. find_first_of() searches for one of several values simultaneously. search() and find_end() search for subsequences matching a specified sequence of elements, starting from either the beginning or end of the supplied range. search_n() can be thought of as a special case of search() or a general case of adjacent_find(): it finds the first sequence of n consecutive elements matching a supplied value. Finally, min_element() and max_element() find the minimum or maximum element in a sequence.

find_end() is the equivalent of search() that starts from the end of the sequence instead of the beginning. It is not the reverse equivalent of find(). There is no reverse equivalent of find(), find_if(), or other algorithms that search for a single element, because you can use a reverse_iterator to achieve the same effect. reverse_iterators are described in Chapter 23.

find(), adjacent_find(), min_element() quadratic time. All the algorithms use default vide overloaded versions that allow the client

, and max_element() run in linear time. The others run in comparisons of operator== or operator<, but also proto specify a comparison callback.

Here are examples of the preceding search algorithms:

#include <algorithm> #include <iostream> #include <vector> using namespace std;

int main(int argc, char** argv)

{

// The list of elements to be searched int elems[] = {5, 6, 9, 8, 8, 3};

633

Chapter 22

//Construct a vector from the list, exploiting the

//fact that pointers are iterators too. vector<int> myVector(elems, elems + 6); vector<int>::const_iterator it, it2;

//Find the min and max elements in the vector.

it = min_element(myVector.begin(), myVector.end()); it2 = max_element(myVector.begin(), myVector.end());

cout << “The min is “ << *it << “ and the max is “ << *it2 << endl;

// Find the first pair of matching consecutive elements. it = adjacent_find(myVector.begin(), myVector.end()); if (it != myVector.end()) {

cout << “Found two consecutive equal elements of value “ << *it << endl;

}

// Find the first of two values. int targets[] = {8, 9};

it = find_first_of(myVector.begin(), myVector.end(), targets, targets + 2);

if (it != myVector.end()) {

cout << “Found one of 8 or 9: “ << *it << endl;

}

// Find the first subsequence. int sub[] = {8, 3};

it = search(myVector.begin(), myVector.end(), sub, sub + 2); if (it != myVector.end()) {

cout << “Found subsequence 8, 3 at position “ << it - myVector.begin() << endl;

}

// Find the last subsequence (which should be the same as the first). it2 = find_end(myVector.begin(), myVector.end(), sub, sub + 2);

if (it != it2) {

cout << “Error: search and find_end found different subsequences “ << “ even though there is only one match.\n”;

}

// Find the first subsequence of two consecutive 8s. it = search_n(myVector.begin(), myVector.end(), 2, 8); if (it != myVector.end()) {

cout << “Found two consecutive 8s starting at position “ << it - myVector.begin() << endl;

}

return (0);

}

634

Mastering STL Algorithms and Function Objects

Here is the output:

The min is 3 and the max is 9

Found two consecutive equal elements of value 8

Found one of 8 or 9: 9

Found subsequence 8, 3 at position 4

Found two consecutive 8s starting at position 3

There are also several search algorithms that work only on sorted sequences: binary_search(), lower_bound(), upper_bound(), and equal_range(). binary_search() finds a matching element in logarithmic time. The other three are similar to their method equivalents on the map and set containers. See Chapter 21 and the Standard Library Reference resource on the Web site.

Remember to use equivalent container methods when available instead of the algorithms, because the methods are more efficient.

Numerical Processing Algorithms

You’ve seen an example of one numerical processing algorithm already: accumulate(). In addition, the count() and count_if() algorithms are useful for counting the number of elements of a given value in a container. They function similarly to the count() method on the map and set containers.

The other numerical processing algorithms are less useful, so they are not discussed here. See the Standard Library Reference resource on the Web site for details if you are interested.

Comparison Algorithms

You can compare entire ranges of elements in three different ways: equal(), mismatch(), and lexicographical_compare(). Each of the algorithms compares elements at parallel positions in the two ranges to each other in order. equal() returns true if all parallel elements are equal. mismatch() returns iterators referring into each range at the first point where parallel elements are unequal. lexicographical_compare() returns true if all the elements in the first range are less than their parallel elements in the second range, or if the first range is shorter than the second, and all elements up to that point are less than the parallel elements in the second range. You can think of this function as a generalization of alphabetization to noncharacter elements.

If you want to compare the elements of two containers of the same type, you can use operator== or operator< instead of equal() or lexicographical_compare(). The algorithms are useful primarily for comparing sequences of elements from different container types.

635

Chapter 22

Here are some examples of equal(), mismatch(), and lexicographical_compare():

#include <algorithm> #include <vector> #include <list> #include <iostream> using namespace std;

//Function template to populate a container of ints.

//The container must support push_back(). template<typename Container>

void populateContainer(Container& cont)

{

int num;

while (true) {

cout << “Enter a number (0 to quit): “; cin >> num;

if (num == 0) { break;

}

cont.push_back(num);

}

}

int main(int argc, char** argv)

{

vector<int> myVector; list<int> myList;

cout << “Populate the vector:\n”; populateContainer(myVector); cout << “Populate the list:\n”; populateContainer(myList);

if (myList.size() < myVector.size()) {

cout << “Sorry, the list is not long enough.\n”; return (0);

}

// Compare the two containers.

if (equal(myVector.begin(), myVector.end(), myList.begin())) { cout << “The two containers have equal elements\n”;

}else {

//If the containers were not equal, find out why not. pair<vector<int>::iterator, list<int>::iterator> miss =

mismatch(myVector.begin(), myVector.end(), myList.begin()); cout << “The first mismatch is at position “

<<miss.first - myVector.begin() << “. The vector has value “

<<*(miss.first) << “ and the list has value “ << *(miss.second)

<<endl;

}

// Now order them.

if (lexicographical_compare(myVector.begin(), myVector.end(), myList.begin(), myList.end())) {

636

Mastering STL Algorithms and Function Objects

cout << “The vector is lexicographically first.\n”; } else {

cout << “The list is lexicographically first.\n”;

}

return (0);

}

Here is a sample run of the program:

Populate the vector:

Enter a number (0 to quit): 5 Enter a number (0 to quit): 6 Enter a number (0 to quit): 7 Enter a number (0 to quit): 8 Enter a number (0 to quit): 0 Populate the list:

Enter a number (0 to quit): 5 Enter a number (0 to quit): 6 Enter a number (0 to quit): 7 Enter a number (0 to quit): 9 Enter a number (0 to quit): 0

The first mismatch is at position 3. The vector has value 8 and the list has value 9 The vector is lexicographically first.

Operational Algorithms

There is only one algorithm in this category: for_each(). However, it is one of the most useful algorithms in the STL. It executes a callback on each element of the range. You can use it with simple function callbacks for things like printing every element in a container. For example:

#include <algorithm> #include <map> #include <iostream> using namespace std;

void printPair(const pair<int, int>& elem)

{

cout << elem.first << “->” << elem.second << endl;

}

int main(int argc, char** argv)

{

map<int, int> myMap; myMap.insert(make_pair(4, 40)); myMap.insert(make_pair(5, 50)); myMap.insert(make_pair(6, 60)); myMap.insert(make_pair(7, 70)); myMap.insert(make_pair(8, 80));

for_each(myMap.begin(), myMap.end(), &printPair);

return (0);

}

637

Chapter 22

You can also perform much fancier tasks by using a functor to retain information between elements. for_each() returns a copy of the callback object, so you can accumulate information in your functor that you can retrieve after for_each() has finished processing each element. For example, you could calculate both the min and max elements in one pass by writing a functor that tracks both the minimum and maximum elements found so far. The MinAndMax functor shown in the following example assumes that the range on which it is called contains at least one element. It uses a Boolean first variable to initialize min and max to the first element, after which it compares each subsequent element to the currently stored min and max values.

#include <algorithm> #include <functional> #include <vector> #include <iostream> using namespace std;

//The populateContainer() function is identical to the one shown above for

//comparison alglorithms, so is omitted here.

class MinAndMax : public unary_function<int, void>

{

public:

MinAndMax();

void operator()(int elem);

// Make min and max public for easy access. int min, max;

protected: bool first;

};

MinAndMax::MinAndMax() : min(-1), max(-1), first(true)

{

}

void MinAndMax::operator()(int elem)

{

if (first) {

min = max = elem;

}else if (elem < min) { min = elem;

}else if (elem > max) { max = elem;

}

first = false;

}

int main(int argc, char** argv)

{

vector<int> myVector; populateContainer(myVector);

638