• Choose a category
• All
• Classic-Fiction

By Root 1572 0

elements in containers, and perform a whole host of other operations. The beauty of the algorithms is that they are independent not only of the types of the underlying elements, but of the types of the containers on which they operate. Algorithms perform their work using only the iterator interfaces.

Many of the algorithms accept callbacks, which can be a function pointer or something that behaves like a function pointer, such as an object with an overloaded operator() or a C++11 inline lambda expression. Conveniently, the STL provides a set of classes that can be used to create callback objects for the algorithms. These callback objects are called function objects, or just functors.

OVERVIEW OF ALGORITHMS

The “magic” behind the algorithms is that they work on iterator intermediaries instead of on the containers themselves. In that way, they are not tied to specific container implementations. All the STL algorithms are implemented as function templates, where the template type parameters are usually iterator types. The iterators themselves are specified as arguments to the function. Templatized functions can usually deduce the template types from the function arguments, so you can generally call the algorithms as if they were normal functions, not templates.

The iterator arguments are usually iterator ranges. As Chapter 12 explains, iterator ranges are half-open for most containers such that they include the first element in the range, but exclude the last. The end iterator is really a “past-the-end” marker.

The C++11 forward_list container only supports forward iterators. This means that algorithms requiring bidirectional or random access iterators will not work on a forward_list; for example copy_backward(), random_shuffle(), stable_sort(), etc. do not work on a forward_list.

Some algorithms require additional template type parameters and arguments, which are sometimes function callbacks. These callbacks can be function pointers, function objects or C++11 lambda expressions.

Most algorithms are defined in the header file, while some numerical algorithms are defined in the header file.

The best way to understand the algorithms is to look at some examples first. After you’ve seen how a few of them work, it’s easy to pick up the others. This section describes the find(), find_if(), and accumulate() algorithms in detail. The next sections present the lambda expressions and function objects, and discusses each of the classes of algorithms with representative samples.

The find and find_if Algorithms

find() looks for a specific element in an iterator range. You can use it on elements in any container type. It returns an iterator referring to the element found, or the end iterator of the range in case the element is not found. Note that the range specified in the call to find() need not be the entire range of elements in a container; it could be a subset.

If find() fails to find an element, it returns an iterator equal to the end iterator specified in the function call, not the end iterator of the underlying container.

Here is an example of find(). Note that this example assumes that the user plays nice and enters valid numbers; it does not perform any error checking on the user input. Performing error checking on stream input is discussed in Chapter 15.

#include

#include

#include

using namespace std;

int main()

{

int num;

vector myVector;

while (true) {

cout << "Enter a number to add (0 to stop): ";

cin >> num;

if (num == 0) {

break;

}

myVector.push_back(num);

}

while (true) {

cout << "Enter a number to lookup (0 to stop): ";

cin >> num;

if (num == 0) {

break;

}

auto end = myVector.end();

auto it = find(myVector.begin(), end, num);

if (it == end) {

cout << "Could not find " << num << endl;

} else {

cout << "Found " << *it << endl;

}

}

return 0;

}

Code snippet from AlgorithmOverview\Find.cpp

The call to find() is made with myVector.begin() and end as arguments, where end is defined as myVector.end() for this example,