10.1. Overview

Fundamental

Most of the algorithms are defined in the algorithm header. The library also defines a set of generic numeric algorithms that are defined in the numeric header.

In general, the algorithms do not work directly on a container. Instead, they operate by traversing a range of elements bounded by two iterators (§ 9.2.1, p. 331). Typically, as the algorithm traverses the range, it does something with each element. For example, suppose we have a vector of ints and we want to know if that vector holds a particular value. The easiest way to answer this question is to call the library find algorithm:

int val = 42; // value we'll look for
// result will denote the element we want if it's in vec, or vec.cend() if not
auto result = find(vec.cbegin(), vec.cend(), val);
// report the result
cout << "The value " << val
     << (result == vec.cend()
           ? " is not present" : " is present") << endl;

The first two arguments to find are iterators denoting a range of elements, and the third argument is a value. find compares each element in the given range to the given value. It returns an iterator to the first element that is equal to that value. If there is no match, find returns its second iterator to indicate failure. Thus, we can determine whether the element was found by comparing the return value with the second iterator argument. We do this test in the output statement, which uses the conditional operator (§ 4.7, p. 151) to report whether the value was found.

Because find operates in terms of iterators, we can use the same find function to look for values in any type of container. For example, we can use find to look for a value in a list of strings:

string val = "a value";  // value we'll look for
// this call to find looks through string elements in a list
auto result = find(1st.cbegin(), 1st.cend(), val);

Similarly, because pointers act like iterators on built-in arrays, we can use find to look in an array:

int ia[] = {27, 210, 12, 47, 109, 83};
int val = 83;
int* result = find(begin(ia), end(ia), val);

Here we use the library begin and end functions (§ 3.5.3, p. 118) to pass a pointer to the first and one past the last elements in ia.

We can also look in a subrange of the sequence by passing iterators (or pointers) to the first and one past the last element of that subrange. For example, this call looks for a match in the elements ia[1], ia[2], and ia[3]:

// search the elements starting from ia[1] up to but not including ia[4]
auto result = find(ia + 1, ia + 4, val);

How the Algorithms Work

To see how the algorithms can be used on varying types of containers, let’s look a bit more closely at find. Its job is to find a particular element in an unsorted sequence of elements. Conceptually, we can list the steps find must take:

1. It accesses the first element in the sequence.
2. It compares that element to the value we want.
3. If this element matches the one we want, find returns a value that identifies this element.
4. Otherwise, find advances to the next element and repeats steps 2 and 3.
5. find must stop when it has reached the end of the sequence.
6. If find gets to the end of the sequence, it needs to return a value indicating that the element was not found. This value and the one returned from step 3 must have compatible types.

None of these operations depends on the type of the container that holds the elements. So long as there is an iterator that can be used to access the elements, find doesn’t depend in any way on the container type (or even whether the elements are stored in a container).

Iterators Make the Algorithms Container Independent, ...

All but the second step in the find function can be handled by iterator operations: The iterator dereference operator gives access to an element’s value; if a matching element is found, find can return an iterator to that element; the iterator increment operator moves to the next element; the “off-the-end” iterator will indicate when find has reached the end of its given sequence; and find can return the off-the-end iterator (§ 9.2.1, p. 331) to indicate that the given value wasn’t found.

...But Algorithms Do Depend on Element-Type Operations

Although iterators make the algorithms container independent, most of the algorithms use one (or more) operation(s) on the element type. For example, step 2, uses the element type’s == operator to compare each element to the given value.

Other algorithms require that the element type have the < operator. However, as we’ll see, most algorithms provide a way for us to supply our own operation to use in place of the default operator.

INFO

Exercises Section 10.1

Exercise 10.1: The algorithm header defines a function named count that, like find, takes a pair of iterators and a value. count returns a count of how often that value appears. Read a sequence of ints into a vector and print the count of how many elements have a given value.

Exercise 10.2: Repeat the previous program, but read values into a list of strings.

INFO

Key Concept: Algorithms Never Execute Container Operations

The generic algorithms do not themselves execute container operations. They operate solely in terms of iterators and iterator operations. The fact that the algorithms operate in terms of iterators and not container operations has a perhaps surprising but essential implication: Algorithms never change the size of the underlying container. Algorithms may change the values of the elements stored in the container, and they may move elements around within the container. They do not, however, ever add or remove elements directly.

As we’ll see in § 10.4.1 (p. 401), there is a special class of iterator, the inserters, that do more than traverse the sequence to which they are bound. When we assign to these iterators, they execute insert operations on the underlying container. When an algorithm operates on one of these iterators, the iterator may have the effect of adding elements to the container. The algorithm itself, however, never does so.