- Next chapter
- Previous chapter
- Table of contents

# Chapter 10: The Standard Template Library, generic algorithms

> We're always interested in getting feedback. E-mail us if you like this guide, if you think that important material is omitted, if you encounter errors in the code examples or in the documentation, if you find any typos, or generally just if you feel like e-mailing. Mail to Frank Brokken or use an e-mail form. Please state the concerned document version, found in the title.

The `Standard Template Library` (STL) consists of containers, generic algorithms, iterators, function objects, allocators and adaptors. The STL is a general purpose library consisting of algorithms and data structures. The data structures that are used in the algorithms are abstract in the sense that the algorithms can be used on (practically) every data type.

The algorithms can work on these abstract data types due to the fact that they are template based algorithms. In this chapter the construction of these templates in not further discussed (see chapter 16 for that). Rather, the use of these template algorithms is the focus of this chapter.

Several parts of the standard template library have already been discussed in the C++ Annotations. In chapter 7 the abstract containers were discussed, and in section 6.8 function objects and adaptors were covered. Also, iterators were mentioned at several places in this document.

The remaining components of the STL will be covered in this chapter. Iterators, and the generic algorithms will be discussed in the coming sections. Allocators take care of the memory allocation within the STL. The default allocator class suffices for most applications.

Forgetting to delete allocated memory is a common source of errors or memory leaks in a program. The `auto_ptr` template class may be used to prevent these types of problems. The `auto_ptr` class is discussed in section 10.2 of this chapter.

## 10.1: Iterators

Iterators are an abstraction of pointers. In general, the following holds true of iterators:

- Given an iterator `iter`, `*iter` represents the object the iterator points to (alternatively, `iter->` can be used to reach the object the iterator points to).
- `++iter` or `iter++` advances the iterator to the next element. The notion of advancing an iterator to the next element is consequently applied: several containers have a reversed iterator type, in which the `iter++` operation actually reaches an previous element in a sequence.
- For the containers that have their elements stored consecutively in memory pointer arithmetic is available as well. This counts out the `list`, but includes the `vector, queue, deque, set` and `map`. For these containers `iter + 2` points to the second element beyond the one to which `iter` points.

The STL containers produce iterators (i.e., type `iterator`) using member functions `begin()` and `end()` and, in the case of reversed iterators (type `reverse_iterator`), `rbegin()` and `rend()`. Standard practice requires the iterator range to be left inclusive: the notation `[left, right)` indicates that `left` is an iterator pointing to the first element that is to be considered, while `right` is an iterator pointing just beyond the last element to be used. The iterator-range is said to be empty when `left == right`.

The following example shows a situation where all elements of a vector of strings are written to `cout` using the iterator range `[begin(), end())`, and the iterator range `[rbegin(), rend())`. Note that the `for-loops` for both ranges are identical:

    #include <iostream>
    #include <vector>
    #include <string>

    int main(int argc, char **argv)
    {
        vector<string>
            args(argv, argv + argc);

        for
        (
            vector<string>::iterator iter = args.begin();
                iter != args.end();
                    ++iter
        )
            cout << *iter << " ";

        cout << endl;

        for
        (
            vector<string>::reverse_iterator iter = args.rbegin();
                iter != args.rend();
                    ++iter
        )
            cout << *iter << " ";

        cout << endl;

        return (0);
    }

Furthermore, the STL defines const_iterator types to be able to visit a range of the elements in a constant container. Whereas the elements of the vector in the previous example could have been altered, the elements of the vector in the next example are immutable, and `const_iterator`s are required:

    #include <iostream>
    #include <vector>
    #include <string>

    int main(int argc, char **argv)
    {
        const vector<string>
            args(argv, argv + argc);

        for
        (
            vector<string>::const_iterator iter = args.begin();
                iter != args.end();
                    ++iter
        )
            cout << *iter << " ";

        cout << endl;

        for
        (
            vector<string>::const_reverse_iterator iter = args.rbegin();
                iter != args.rend();
                    ++iter
        )
            cout << *iter << " ";

        cout << endl;

        return (0);
    }

The examples also illustrate the use of plain pointers for iterators. The initialization `vector<string> sarg(argv, argv + argc)` provides the `sarg` vector with a pair of pointer-based iterators: `argv` points to the first element to initialize `sarg` with, `argv + argc` points just beyond the last element to be used, `argv++` reaches the next string. This is a general characteristic of pointers, which is why they too can be used in situations where `iterators` are expected.

The STL defines five types of iterators. These types recur in the generic algorithms, and in order to be able to create a particular type of iterator yourself it is important to know their characteristic. In general, it must be possible to

- test iterators for equality (`==`)
- test iterators for inequality (`!=`)
- increment iterators using the prefix or postfix increment operator (`++`)
- access the element iterators refer to using the dereference operator (`*`).

- InputIterators: InputIterators can read elements from a container. The dereference operator is guaranteed to work as an `rvalue` in an expression, not as an `lvalue`. Instead of an InputIterator it is also possible to (see below) use a Forward-, Bidirectional- or RandomAccessIterator.
- OutputIterators: OutputIterators can be used to write to a container. The dereference operator is guaranteed to work as an `lvalue` in an expression, not as an `rvalue`. Instead of an OutputIterator it is also possible to (see below) use a Forward-, Bidirectional- or RandomAccessIterator.
- ForwardIterators: ForwardIterators combine InputIterators and OutputIterators. They can be used to traverse the container in one direction, for reading and/or writing. Instead of a ForwardIterator it is also possible to (see below) use a Bidirectional- or RandomAccessIterator.
- BidirectionalIterators: BidirectionalIterators allow the traversal of a container in both directions, for reading and writing. Instead of a BidirectionalIterator it is also possible to (see below) use a RandomAccessIterator. For example, to traverse a list or a deque a BidirectionalIterator may be useful.
- RandomAccessIterators: RandomAccessIterators provide access to any element of the container at any moment. An algorithm such as `sort()` requires a RandomAccessIterator, and can therefore not be used with lists or maps, which only provide BidirectionalIterators.

The example given with the RandomAccessIterator provides an approach towards iterators: look for the iterator that's required by the (generic) algorithm, and then see whether the datastructure supports the required iterator or not. If not, the algorithm cannot be used with the particular datastructure.

### 10.1.1: Insert iterators

The generic algorithms often require a target container into which the results of the algorithm are deposited. For example, the `copy()` algorithm has three parameters, the first two of them define the range of elements which are visited, and the third parameter defines the first position where the result of the copy operation is to be stored. With the `copy()` algorithm the number of elements that are copied are normally available beforehand, since the number is normally equal to the number of elements in the range defined by the first two parameters, but this does not always hold true. Sometimes the number of resulting elements is different from the number of elements in the initial range. The generic algorithm `unique_copy()` is a case in point: the number of elements which are copied to the destination container is normally not known beforehand.

In situations like these, the `inserter()` adaptor functions may be used to create elements in the destination container when they are needed.

There are three `inserter()` adaptors:

- `back_inserter()` calls the container's `push_back()` insert member to add new elements at the end of the container. E.g.,

              copy(source.rbegin(), source.rend(), back_inserter(destination));

  will copy all elements of `source` in reversed order to the back of `destination`.
- `front_inserter()` calls the container's `push_front()` insert member to add new elements at the beginning of the container. E.g.,

              copy(source.begin(), source.end(), front_inserter(destination));

  will copy all elements of `source` to the front of the destination container (thereby also reversing the order of the elements).
- `inserter()` calls the container's `insert()` member to add new elements starting at a specified starting point within the container. E.g.,

              copy(source.begin(), source.end(), inserter(destination,
      destination.begin()));

  will copy all elements of `source` to the destination container, starting at the beginning of `destination`.

### 10.1.2: istream iterators

The `istream_iterator<Type>()` can be used to define an iterator (pair) for an `istream` object or for a subtype of an `istream`. The general form of the `istream_iterator<Type>()` iterator is:
`istream_iterator<Type> identifier(istream &inStream)`
Here, `Type` is the type of the data elements that are to be read from the `istream` stream. `Type` may be any of the types for which the `operator>>()` is defined with `istream` objects.

The default (empty) constructor defines the end of the iterator pair, corresponding to `end-of-stream`. For example,

`istream_iterator<string> endOfStream;`
Note that the actual stream object which is specified for the begin-iterator is not mentioned here.

Using a `back_inserter()` and a set of `istream_iterator<>()`s all strings could be read from `cin` as follows:

    #include <algorithm>
    #include <iterator>
    #include <string>
    #include <vector>

    int main()
    {
        vector<string>
            vs;

        copy(istream_iterator<string>(cin), istream_iterator<string>(),
             back_inserter(vs));

        for
        (
            vector<string>::iterator from = vs.begin();
                from != vs.end();
                    ++from
        )
            cout << *from << " ";
        cout << endl;

        return (0);
    }

In the above example, note the use of the anonymous versions of the `istream_iterator`s. Especially note the use of the anonymous default constructor. Instead of using `istream_iterator<string>()` the (non-anonymous) construction

        istream_iterator<string>
                eos;

        copy(istream_iterator<string>(cin), eos, back_inserter(vs));

could have been used.

The `istream_iterator` iterators is available when the `iterator` header file is included. This is, e.g., the case when `iostream` is included.

### 10.1.3: ostream iterators

The `ostream_iterator<Type>()` can be used to define a destination iterator for an `ostream` object or for a subtype of an `ostream`. The general forms of the `ostream_iterator<Type>()` iterator are:
`ostream_iterator<Type> identifier(ostream &outStream)`
and
`ostream_iterator<Type> identifier(ostream &outStream), char const *delimiter`
`Type` is the type of the data elements that are to be written to the `ostream` stream. `Type` may be any of the types for which the `operator<<()` is defined with `ostream` objects. The latter form of the `ostream_iterators` separates the individual `Type` data elements by `delimiter` strings. The former form does not use any delimiters.

The following example shows the use of a `istream_iterators` and an `ostream_iterator` to copy information of a file to another file. A subtlety is the statement `in.unsetf(ios::skipws)`: it resets the `ios::skipws` flag. The consequence of this is that the default behavior of the `operator>>()`, to skip whitespace, is modified. White space characters are simply returned by the operator, and the file is copied unrestrictedly. Here is the program:

    #include <algorithm>
    #include <fstream>
    #include <iomanip>

    int main(int argc, char **argv)
    {
        ifstream
            in(argv[1]);

        in.unsetf(ios::skipws);

        ofstream
            out(argv[2]);

        copy(istream_iterator<char>(in), istream_iterator<char>(),
             ostream_iterator<char>(out));

        return (0);
    }

The `ostream_iterator` iterators are available when the `iterator` header file is included. This is, e.g., the case when `iostream` is included.

## 10.2: The 'auto_ptr' class

One of the problems using pointers is that strict bookkeeping is required about the memory the pointers point to. When a pointer variable goes out of scope, the memory pointed to by the pointer is suddenly inaccessible, and the program suffers from a memory leak. For example, in the following code, a memory leak is introduced in which 200 `int` values remain allocated:

        #include <iostream>

        int main()
        {
            for (int idx = 0; idx < 200; ++idx)
            {
                int
                    c,
                    *ip;

                cin >> c;               // read an int
                ip = new int(c);        // ip points to int initialized to 'c'
            }                           // no delete-operation
            next();                     // whatever comes next
            return (0);
        }

The standard way to prevent memory leakage is strict bookkeeping: the programmer has to make sure that the memory pointed to by a pointer is deleted just before the pointer variable dies. In the above example the repair would be:

        #include <iostream>

        int main()
        {
            for (int idx = 0; idx < 200; ++idx)
            {
                int
                    c,
                    *ip;

                cin >> c;               // read an int
                ip = new int(c);        // ip points to int initialized to 'c'
                delete ip;              // and delete the allocated memory again
            }
            next();                     // whatever comes next
            return (0);
        }

When a pointer variable is used to point to a single value or object, the bookkeeping becomes less of a burden when the pointer variable is defined as a `auto_ptr` object. The template class `auto_ptr` is available when the header file `memory` is included.

Normally, an `auto_ptr` object is initialized to point to a dynamically created value or object. When the `auto_ptr` object goes out of scope, the memory pointed to by the object is automatically deleted, taking over the programmer's responsibility to delete memory.

Alternative forms to create `auto_ptr` objects are available as well, as discussed in the coming sections.

Note that

- the `auto_ptr` object cannot be used to point to arrays of objects.
- an `auto_ptr` object should only point to memory that was made available dynamically, as only dynamically allocated memory can be deleted.
- multiple `auto_ptr` objects should not be allowed to point to the same block of dynamically allocated memory. Once one `auto_ptr` object goes out of scope, it deletes the memory it points to, immediately rendering the other objects wild. Ways to prevent this situation are discussed below.

The `class auto_ptr` has several memberfunctions which can be used to access the pointer itself and to have the `auto_ptr` point to another block of memory. These memberfunctions are discussed in the following sections as well.

Note:

> By the time these annotations were written the `memory` header file which must be included to use the `auto_ptr` objects was still incomplete. A modified `memory` header file which can be used to replace the current incomplete file can be found at ftp://ftp.icce.rug.nl/pub/frank/egcs/memory. This file can replace the `memory` file in (on Linux systems) `/usr/include/g++`, and on computers running MS-Windows in `Cygnus/B19/include/g++/memory`.

### 10.2.1: Defining auto_ptr variables

There are three ways to define `auto_ptr` objects. Each definition contains the usual `<type>` specifier between pointed brackets. Concrete examples are given in the coming sections, but an overview of the various possibilities is presented here:

- The basic form initializes an `auto_ptr` object to a block of memory that's allocated by the `new` operator:
  `auto_ptr<type> identifier (new-expression);`
  This form is discussed in the next section 10.2.2.
- Another form initializes an `auto_ptr` object through another `auto_ptr` object:
  `auto_ptr<type> identifier(another auto_ptr for type);`
  This form is discussed in the next section 10.2.3.
- The third form simply creates an `auto_ptr` object that does not point to a particular block of memory:
  `auto_ptr<type> identifier;`
  This form is discussed in the next section 10.2.4.

### 10.2.2: Pointing to a newly allocated object

The basic form to initialize an `auto_ptr` object is to pass its constructor a block of memory that's allocated by the `new` operator. The generic form is:
`auto_ptr<type> identifier (new-expression);`

For example, to initialize an `auto_ptr` to a `string` variable the construction

`auto_ptr<string> strPtr (new string("Hello world"));`
can be used. To initialize an `auto_ptr` to a `double` variable the construction
`auto_ptr<double> dPtr (new double(123.456));`
can be used.

Note the use of the operator `new` in the above expressions. The use of the operator `new` ensures the dynamic nature of the memory pointed to by the `auto_ptr` objects, and allows the deletion of the memory once the `auto_ptr` objects go out of scope. Also note that the `type` does not contain the pointer: the `type` used in the `auto_ptr` construction is the same type as used in the `new` expression.

In the example of the 200 `int` values given earlier, the memory leak can be avoided by using `auto_ptr` objects as follows:

        #include <iostream>
        #include <memory>

        int main()
        {
            for (int idx = 0; idx < 200; ++idx)
            {
                int
                    c;

                cin >> c;               // read an int
                auto_ptr<int> ip (new int(c));
            }                           // no delete-operation needed
            return (0);
        }

Following each cycle of the for loop, the memory allocated by the `new int(c)` expression is deleted automatically.

All member functions that are available for objects that are allocated by the `new` expression (like the `string` object in the first example in this section) can be reached via the `auto_ptr` as if it was a plain pointer to the dynamically allocated object. E.g., to insert some text beyond the wordt `hello` in the string pointed to by `strPtr`, an expression like

`strPtr->insert(strPtr->find_first_of(" ") + 1, "C++ ");`
can be used.

### 10.2.3: Pointing to another auto_ptr

Another form to initialize an `auto_ptr` object is to initialize it from another `auto_ptr` object for the same type. The generic form is:
`auto_ptr<type> identifier (other auto_ptr object);`

For example, to initialize an `auto_ptr` to a `string` variable, given the `strPtr` variable defined in the previous section, the construction

`auto_ptr<string> newPtr(strPtr);`
can be used.

A comparable construction can be used with the assignment operator in expressions. One `auto_ptr` object may be assigned to another `auto_ptr` object of the same type. For example:

        #include <iostream>
        #include <memory>
        #include <string>

        int main()
        {
            auto_ptr<string>
                hello(new string("Hello world")),
                hello2(hello),
                hello3(new string("Another string"));

            hello3 = hello2;
            return (0);
        }

Looking at the above example, we see that `hello` is initialized as described in the previous section. A `new` expression is used to allocate a `string` variable dynamically. Next, `hello2` is initialized to `hello`, which is possible, as they are `auto_ptr` objects of the same types. However, in order to prevent problems when either object goes out of scope, special measures are required.

If the program would stop here, both `hello` and `hello2` go out of scope. But only `hello2` would point to the dynamically allocated string `hello world`: once a `auto_ptr` object is used to initialize another `auto_ptr` object, the former (initializing) object does not refer anymore to the allocated string. The string is now `owned' by the latter (initialized) object.

A comparable action takes place in the assignment statement `hello3 = hello2`. Here, prior to the actual assignment, the memory pointed to by `hello3` is deleted automatically. Then `hello3` gains the ownership of the string `Hello world`, and `hello2` cannot be used anymore to reach the string `Hello world`.

### 10.2.4: Creating an plain auto_ptr

The third form to create an `auto_ptr` object simply creates an empty `auto_ptr` object that does not point to a particular block of memory:
`auto_ptr<type> identifier;`

In this case the underlying pointer is set to `0` (zero). Since the `auto_ptr` object itself is not the pointer, its value cannot be compared to `0` to see if it has not been initialized. E.g., code like

        auto_ptr<int>
            ip;

        if (!ip)
            cout << "0-pointer with an auto_ptr object ?" << endl;

will not produce any output (actually, it won't compile either...). So, how do we inspect the value of the pointer that's maintained by the `auto_ptr` object? For this the member `get()` is available. This member function, as well as the other member functions of the class `auto_ptr` are described in the following sections.

### 10.2.5: The get() memberfunction

The memberfunction `get()` of an `auto_ptr` object returns the underlying pointer. The value returned by `get()` is a pointer to the underlying data-type. It may be inspected: if it's zero the `auto_ptr` object does not point to any memory.

The memberfunction `get()` cannot be used to let the `auto_ptr` object point to (another) block of memory. Instead the memberfunction `reset()`, discussed in the next section, should be used.

### 10.2.6: The reset() memberfunction

The memberfunction `reset()` of an `auto_ptr` object can be used to (re)assign a block of memory allocated by the operator `new` to an `auto_ptr`. The function `reset()` does not return a value.

An example of its use is:

        auto_ptr<string>
            str;

        str.reset(new string("Hello"));         // assignment of a value
        str.reset(new string("Hello world"));   // reassignment of a value

The object that is assigned to the pointer using `reset()` must have been allocated using the `new` operator. The object the pointer points to just before applying `reset()`) is deleted first. The value `0` can be passed to `reset()` if the object pointed to by the pointer should be deleted. Following `reset(0)` the pointer variable has been reinitialized.

Note that it is usually more efficient to use a reassignment memberfunction of the object pointed to by the pointer if the only purpose of the exercise is to redefine the value of the object. For example, the `string` class supports a function `assign()` which may be used for that purpose. So, a construction like:

            auto_ptr<string>
                aps(new string("Hello"));

            aps.reset("Hello world");

can more efficiently be implemented as:

            auto_ptr<string>
                aps(new string("Hello"));

            aps->assign("Hello world");

### 10.2.7: The release() memberfunction

As we saw in section 10.2.3, when an `auto_ptr` is assigned to another `auto_ptr`, the pointer providing the value loses its value and is reinitialized to 0. If that's not what we want, the memberfunction `release()` may be used.

The `release()` memeberfunction returns the address of the underlying pointer used by the `auto_ptr` object, and releases the ownership of the object at the same time. The ownership can then be taken over by another `auto_ptr` variable (or, indeed, by any other pointer).

In the following example a pointer is initialized, and then another pointer is created to point to the same string as the first `auto_ptr` points to. The first `auto_ptr` still points to the string, but doesn't own the string anymore. Therefore, when the first `auto_ptr` goes out of scope, it won't delete the string pointed to by the second `auto_ptr`.

        #include <memory>
        #include <string>

        int main()
        {
            auto_ptr<string>
                first;

            {
                auto_ptr<string>
                    second(new string("Hello world"));

                first.reset(second.release());

                cout << "Second auto_ptr still points at: " << *second << endl
                    << "First auto_ptr also points to: " << *first << endl;
            }
            cout << "Second object now out of scope. First auto_ptr\n"
                "still points at: " << *first << endl;
        }

## 10.3: The Generic Algorithms

The following sections describe the generic algorithms in alphabetical order. For each algorithm the following information is provided:

- The required header file(s)
- The function prototype
- A short description
- A short example.

In the prototypes of the algorithms `Type` is used to specify a generic (i.e., template) datatype. The particular kind of iterator that is required is mentioned, and possibly other generic types, e.g., performing `BinaryOperations`, like `plus<Type>()`.

Almost every generic algorithm has as its first two arguments an iterator range `[first, last)`, defining the range of elements on which the algorithm operates.

### 10.3.1: accumulate()

- Header file:

      #include<numeric>

- Function prototypes:
  - `Type accumulate(InputIterator first, InputIterator last, Type init);`
  - `Type accumulate(InputIterator first, InputIterator last, Type init, BinaryOperation op);`
- Description:
  - The first prototype: the `operator+()` is applied to all elements implied by the iterator range and to the initial value `init`, and the resulting value is returned.
  - The second prototype: the `op()` is applied to all elements implied by the iterator range and to the initial value `init`, and the resulting value is returned.
- Example:

      #include<numeric>
      #include<vector>
      #include<iostream>

      int main()
      {
          int
              ia[] = {1, 2, 3, 4};
          vector<int>
              iv(ia, ia + 4);

          cout <<
              "Sum of values: " << accumulate(iv.begin(), iv.end(), int(0)) <<
              endl <<
              "Product of values: " << accumulate(iv.begin(), iv.end(), int(1),
                                              multiplies<int>()) <<
              endl;

          return(0);
      }

### 10.3.2: adjacent_difference()

- Header file:

      #include<numeric>

- Function prototypes:
  - `OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);`
  - `OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation op);`
- Description:
  - The first prototype: The first returned element is equal to the first element of the input range. The remaining returned elements are equal to the difference of the corresponding element in the input range and its previous element.
  - The second prototype: The first returned element is equal to the first element of the input range. The remaining returned elements are equal to the result of the binary operator `op` applied to the corresponding element in the input range (left operand) and its previous element (right operand).
- Example:

      #include<numeric>
      #include<vector>
      #include<iostream>

      int main()
      {
          int
              ia[] = {1, 2, 5, 10};
          vector<int>
              iv(ia, ia + 4),
              ov(iv.size());

          adjacent_difference(iv.begin(), iv.end(), ov.begin());
          copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
          cout << endl;

          adjacent_difference(iv.begin(), iv.end(), ov.begin(), minus<int>());
          copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
          cout << endl;

          return(0);
      }

### 10.3.3: adjacent_find()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);`
  - `OutputIterator adjacent_find(ForwardIterator first, ForwardIterator last, Predicate pred);`
- Description:
  - The first prototype: The iterator pointing to the first element of the first set of two adjacent equal elements is returned. If no such element exists, `last` is returned.
  - The second prototype: The iterator pointing to the first element of the first set of two adjacent elements for which the binary predicate `pred` returns `true` is returned. If no such element exists, `last` is returned.
- Example (see section 10.3.5 for a description of the `copy()` generic algorithm that is used in the following example):

      #include<algorithm>
      #include<string>
      #include<iostream>

      class SquaresDiff
      {
          public:
              SquaresDiff(unsigned minimum): minimum(minimum)
              {}
              bool operator()(unsigned first, unsigned second)
              {
                  return (second * second - first * first  >= minimum);
              }
          private:
              unsigned
                  minimum;
      };

      int main()
      {
          string
              sarr[] =
              {
                  "Alpha", "bravo", "charley", "echo", "echo", "delta",
                  "foxtrot", "golf"
              };
          string
              *last = sarr + sizeof(sarr) / sizeof(string),
              *result = adjacent_find(sarr, last);

          cout << *result << endl;
          result = adjacent_find(++result, last);

          cout << "Second time, starting from the next position:\n" <<
              (
                  result == last ?
                      "** No more adjacent equal elements **"
                  :
                      "*result"
              ) << endl;

          unsigned
              *ires,
              iv[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
              *ilast = iv + sizeof(iv) / sizeof(unsigned);

          ires = adjacent_find(iv, ilast, SquaresDiff(10));
          cout <<
              "The first numbers for which the squares differ by at least 10 are: "
              << *ires << " and " << *(ires + 1) << endl;

          return(0);
      }

### 10.3.4: binary_search()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `bool binary_search(ForwardIterator first, ForwardIterator last, Type const &value);`
  - `bool binary_search(ForwardIterator first, ForwardIterator last, Type const &value, Comparator comp);`
- Description:
  - The first prototype: `value` is looked up using binary search in the range of elements implied by the iterator range `[first, last)`. The elements in the range must have been sorted by the `Type::operator<()` function. `True` is returned if the element was found, `false` otherwise.
  - The second prototype: `value` is looked up using binary search in the range of elements implied by the iterator range `[first, last)`. The elements in the range must have been sorted by the `Comparator` function object. `True` is returned if the element was found, `false` otherwise.
- Example:

      #include <algorithm>
      #include <string>
      #include <iostream>
      #include <functional>

      int main()
      {
          string
              sarr[] =
              {
                  "Alpha", "bravo", "charley", "echo", "delta",
                  "foxtrot", "golf", "hotel"
              };
          string
              *last = sarr + sizeof(sarr) / sizeof(string);
          bool
              result = binary_search(sarr, last, "foxtrot");
          cout << (result ? "found " : "didn't find ") << "foxtrot" << endl;

          reverse(sarr, last);                // reverse the order of elements
                                              // binary search now fails:
          result = binary_search(sarr, last, "foxtrot");
          cout << (result ? "found " : "didn't find ") << "foxtrot" << endl;
                                              // ok when using appropriate
                                              // comparator:
          result = binary_search(sarr, last, "foxtrot", greater<string>());
          cout << (result ? "found " : "didn't find ") << "foxtrot" << endl;

          return(0);
      }

### 10.3.5: copy()

- Header file:

      #include<algorithm>

- Function prototype:
  - `OutputIterator copy(InputIterator first, InputIterator last, OutputIterator destination);`
- Description:
  - The range of elements implied by the iterator range `[first, last)` are copied to an output range, starting at `destination`, using the assignment operator of the underlying data type. The returnvalue is the OutputIterator pointing just beyond the last element that was copied to the destinatin range (so, `last' in the destination range is returned). In the example, note the second call to `copy()`. It uses an `ostream_iterator` for `string` objects. This iterator will write the `string` values to the specified `ostream` (i.e., `cout`), separating the values by the specified separation string (i.e., `" "`).
- Example:

      #include <algorithm>
      #include <string>
      #include <iostream>

      int main()
      {
          string
              sarr[] =
              {
                  "Alpha", "bravo", "charley", "echo", "delta",
                  "foxtrot", "golf", "hotel"
              };
          string
              *last = sarr + sizeof(sarr) / sizeof(string);

          copy(sarr + 2, last, sarr);     // move all elements two positions left

                                          // copy to cout using an ostream_iterator
                                          // for strings,
          copy(sarr, last, ostream_iterator<string>(cout, " "));
          cout << endl;

          return(0);
      }

### 10.3.6: copy_backward()

- Header file:

      #include<algorithm>

- Function prototype:
  - `BidirectionalIterator copy_backward(InputIterator first, InputIterator last, BidirectionalIterator last2);`
- Description:
  - The range of elements implied by the iterator range `[first, last)` are copied from the element at position `last - 1` until (and including) the element at position `first` to the element range, ending at position `last2 - 1`, using the assignment operator of the underlying data type. The destination range is therefore `[last2 - (last - first), last2)`.

    The returnvalue is the BidirectionalIterator pointing at the last element that was copied to the destinatin range (so, `first' in the destination range, pointed to by `last2 - (last - first)`, is returned).

- Example:

      #include <algorithm>
      #include <string>
      #include <iostream>

      int main()
      {
          string
              sarr[] =
              {
                  "Alpha", "bravo", "charley", "echo", "delta",
                  "foxtrot", "golf", "hotel"
              };
          string
              *last = sarr + sizeof(sarr) / sizeof(string);

          copy
          (
              copy_backward(sarr + 3, last, last - 3),
              last,
              ostream_iterator<string>(cout, " ")
          );
          cout << endl;

          return(0);
      }

### 10.3.7: count()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `size_t cout(InputIterator first, InputIterator last, Type const &value);`
- Description:
  - The number of times `value` occurs in the iterator range `first, last` is returned. To determine wheter `value` is equal to an element in the iterator range `Type::operator==()` is used.
- Example:

      #include<algorithm>
      #include<iostream>

      int main()
      {
          int
              ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};

          cout << "Number of times the value 3 is available: " <<
              count(ia, ia + sizeof(ia) / sizeof(int), 3) <<
              endl;

          return(0);
      }

### 10.3.8: count_if()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `size_t cout_if(InputIterator first, InputIterator last, Predicate predicate);`
- Description:
  - The number of times unary predicate `predicate` returns `true` when applied to the elements implied by the iterator range `first, last` is returned.
- Example:

      #include<algorithm>
      #include<iostream>

      class Odd
      {
          public:
              bool operator()(int value)
              {
                  return (value & 1);
              }
      };

      int main()
      {
          int
              ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};

          cout << "The number of odd values in the array is: " <<
              count_if(ia, ia + sizeof(ia) / sizeof(int), Odd()) <<
              endl;

          return(0);
      }

### 10.3.9: equal()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `bool equal(InputIterator first, InputIterator last, InputIterator otherFirst);`
  - `bool equal(InputIterator first, InputIterator last, InputIterator otherFirst, BinaryPredicate pred);`
- Description:
  - The first prototype: The elements in the range `[first, last)` are compared to a range of equal length starting at `otherFirst`. The function returns `true` if the visited elements in both ranges are equal pairwise. The ranges need not be of equal length, only the elements in the indicated range are considered (and must be available).
  - The second prototype: The elements in the range `[first, last)` are compared to a range of equal length starting at `otherFirst`. The function returns `true` if the binary predicate, applied to all corresponding elements in both ranges returns `true` for every pair of corresponsing elements. The ranges need not be of equal length, only the elements in the indicated range are considered (and must be available).
- Example:

      #include <algorithm>
      #include <string>
      #include <iostream>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (!strcasecmp(first.c_str(), second.c_str()));
              }
      };

      int main()
      {
          string
              first[] =
              {
                  "Alpha", "bravo", "Charley", "echo", "Delta",
                  "foxtrot", "Golf", "hotel"
              },
              second[] =
              {
                  "alpha", "bravo", "charley", "echo", "delta",
                  "foxtrot", "golf", "hotel"
              };
          string
              *last = first + sizeof(first) / sizeof(string);

          cout << "The elements of `first' and `second' are pairwise " <<
              (equal(first, last, second) ? "equal" : "not equal") <<
              endl <<
              "compared case-insensitively, they are " <<
              (equal(first, last, second, CaseString()) ? "equal" : "not equal") <<
              endl;

          return(0);
      }

### 10.3.10: equal_range()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Type const &value);`
  - `pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Type const &value, Compare comp);`
- Description:
  - The first prototype: Starting from a sorted sequence (where the `operator<()` of the underlying data type was used to sort the elements in the provided range), a pair of iterators representing the returnvalue of, respectively, lower_bound() and upper_bound()is returned.
  - The second prototype: Starting from a sorted sequence (where the `comp` function object was used to sort the elements in the provided range), a pair of iterators representing the returnvalue of, respectively, lower_bound() and upper_bound()is returned.
- Example:

      #include <algorithm>
      #include <functional>
      #include <iostream>
      #include <utility>
      #include <vector>

      int main()
      {
          int
              range[] = {1, 3, 5, 7, 7, 9, 9, 9};
          unsigned const
              size = sizeof(range) / sizeof(int);

          pair<int *, int *>
              pi;

          pi = equal_range(range, range + size, 7);

          cout << "Lower bound for 7: ";
          copy(pi.first, range + size, ostream_iterator<int>(cout, " "));
          cout << endl;

          cout << "Upper bound for 7: ";
          copy(pi.second, range + size, ostream_iterator<int>(cout, " "));
          cout << endl;

          sort(range, range + size, greater<int>());

          cout << "Sorted in descending order\n";

          copy(range, range + size, ostream_iterator<int>(cout, " "));
          cout << endl;

          pi = equal_range(range, range + size, 7, greater<int>());

          cout << "Lower bound for 7: ";
          copy(pi.first, range + size, ostream_iterator<int>(cout, " "));
          cout << endl;

          cout << "Upper bound for 7: ";
          copy(pi.second, range + size, ostream_iterator<int>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.11: fill()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `void fill(ForwardIterator first, ForwardIterator last, Type const &value);`
- Description:
  - all the elements implied by the interator range `[first, last)` are initialized to `value`, overwriting the previous values stored in the range.
- Example:

      #include<algorithm>
      #include<vector>
      #include<iostream>
      #include<iterator>

      int main()
      {
          vector<int>
              iv(8);

          fill(iv.begin(), iv.end(), 8);

          copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
          cout << endl;

          return(0);
      }

### 10.3.12: fill_n()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `void fill_n(ForwardIterator first, Size n, Type const &value);`
- Description:
  - `n` elements starting at the element pointed to by `first` are initialized to `value`, overwriting the previous values stored in the range.
- Example:

      #include<algorithm>
      #include<vector>
      #include<iostream>
      #include<iterator>

      int main()
      {
          vector<int>
              iv(8);

          fill_n(iv.begin(), 8, 8);

          copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
          cout << endl;

          return(0);
      }

### 10.3.13: find()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `InputIterator find(InputIterator first, InputIterator last, Type const &value);`
- Description:
  - Element `value` is searched for in the range of the elements implied by the interator range `[first, last)`. An iterator pointing to the first element found is returned. If the element was not found, `last` is returned. The `operator==()` of the underlying data type is used to compare the elements.
- Example:

      #include<algorithm>
      #include<string>
      #include<iostream>
      #include<iterator>

      int main()
      {
          string
              sarr[] =
              {
                  "alpha", "bravo", "charley", "echo", "delta",
                  "foxtrot", "golf", "hotel"
              };
          string
              *last = sarr + sizeof(sarr) / sizeof(string);

          copy
          (
              find(sarr, last, "echo"), last, ostream_iterator<string>(cout, " ")
          );
          cout << endl;

          if (find(sarr, last, "india") == last)
          {
              cout << "`india' was not found in the range\n";
              copy(sarr, last, ostream_iterator<string>(cout, " "));
              cout << endl;
          }

          return(0);
      }

### 10.3.14: find_if()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `InputIterator find_if(InputIterator first, InputIterator last, Prdicate pred);`
- Description:
  - An iterator pointing to the first element in the range implied by the interator range `[first, last)` for which the (unary) predicate `pred` returns `true` is returned. If the element was not found, `last` is returned.
- Example:

      #include<algorithm>
      #include<string>
      #include<iostream>
      #include<iterator>

      class CaseName
      {
          public:
              CaseName(char const *str): _string(str)
              {}
              bool operator()(string const &element)
              {
                  return (!strcasecmp(element.c_str(), _string.c_str()));
              }
          private:
              string
                  _string;
      };

      int main()
      {
          string
              sarr[] =
              {
                  "Alpha", "Bravo", "Charley", "Echo", "Delta",
                  "Foxtrot", "Golf", "Hotel"
              };
          string
              *last = sarr + sizeof(sarr) / sizeof(string);

          copy
          (
              find_if(sarr, last, CaseName("foxtrot")),
              last, ostream_iterator<string>(cout, " ")
          );
          cout << endl;

          if (find_if(sarr, last, CaseName("india")) == last)
          {
              cout << "`india' was not found in the range\n";
              copy(sarr, last, ostream_iterator<string>(cout, " "));
              cout << endl;
          }

          return(0);
      }

### 10.3.15: find_end()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)`
  - `ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)`
- Description:
  - The first prototype: The sequence of elements implied by `[first1, last1)` is searched for the last occurrence of the sequence of elements implied by `[first2, last2)`. If the sequence `[first2, last2)` is not found, `last1` is returned, otherwise an iterator pointing to the first element of the matching sequence is returned. The `operator==()` of the underlying data type is used to compare the elements in the two sequences.
  - The second prototype: The sequence of elements implied by `[first1, last1)` is searched for the last occurrence of the sequence of elements implied by `[first2, last2)`. If the sequence `[first2, last2)` is not found, `last1` is returned, otherwise an iterator pointing to the first element of the matching sequence is returned. The provided binary predicate is used to compare the elements in the two sequences.
- Example:

      #include<algorithm>
      #include<string>
      #include<iostream>
      #include<iterator>

      class Twice
      {
          public:
              bool operator()(unsigned first, unsigned second) const
              {
                  return (first == (second << 1));
              }
      };

      int main()
      {
          string
              sarr[] =
              {
                  "alpha", "bravo", "charley", "echo", "delta",
                  "foxtrot", "golf", "hotel",
                  "foxtrot", "golf", "hotel",
                  "india", "juliet", "kilo"
              },
              search[] =
              {
                  "foxtrot",
                  "golf",
                  "hotel"
              };
          string
              *last = sarr + sizeof(sarr) / sizeof(string);

          copy
          (
              find_end(sarr, last, search, search + 3),   // shows sequence starting
              last, ostream_iterator<string>(cout, " ")   // at 2nd 'foxtrot'
          );
          cout << endl;

          unsigned
              range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10},
              nrs[]   = {2, 3, 4};

          copy                // show sequence of values starting at last sequence
          (                   // of range[] that are twice the values in nrs[]
              find_end(range, range + 9, nrs, nrs + 3, Twice()),
              range + 9, ostream_iterator<unsigned>(cout, " ")
          );
          cout << endl;

          return(0);
      }

### 10.3.16: find_first_of()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)`
  - `ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)`
- Description:
  - The first prototype: The sequence of elements implied by `[first1, last1)` is searched for the first occurrence of an element in the sequence of elements implied by `[first2, last2)`. If no element in the sequence `[first2, last2)` is found, `last1` is returned, otherwise an iterator pointing to the first element in `[first1, last1)` that is equal to an element in `[first2, last2)` is returned. The `operator==()` of the underlying data type is used to compare the elements in the two sequences.
  - The second prototype: The sequence of elements implied by `[first1, first1)` is searched for the first occurrence of an element in the sequence of elements implied by `[first2, last2)`. Each element in the range `[first1, last1)` is compared to each element in the range `[first2, last2)`, and an iterator to the first element in `[first1, last1)` for which the binary predicate `pred` (receiving an the element out of the range `[first1, last1)` and an element from the range `[first2, last2)`) returns `true` is returned. Otherwise, `last1` is returned.
- Example:

      #include<algorithm>
      #include<string>
      #include<iostream>
      #include<iterator>

      class Twice
      {
          public:
              bool operator()(unsigned first, unsigned second) const
              {
                  return (first == (second << 1));
              }
      };

      int main()
      {
          string
              sarr[] =
              {
                  "alpha", "bravo", "charley", "echo", "delta",
                  "foxtrot", "golf", "hotel",
                  "foxtrot", "golf", "hotel",
                  "india", "juliet", "kilo"
              },
              search[] =
              {
                  "foxtrot",
                  "golf",
                  "hotel"
              };
          string
              *last = sarr + sizeof(sarr) / sizeof(string);

          copy
          (                                               // shows sequence starting
              find_first_of(sarr, last, search, search + 3),  // at 1st 'foxtrot'
              last, ostream_iterator<string>(cout, " ")
          );
          cout << endl;

          unsigned
              range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10},
              nrs[]   = {2, 3, 4};

          copy                // show sequence of values starting at first sequence
          (                   // of range[] that are twice the values in nrs[]
              find_first_of(range, range + 9, nrs, nrs + 3, Twice()),
              range + 9, ostream_iterator<unsigned>(cout, " ")
          );
          cout << endl;

          return(0);
      }

### 10.3.17: for_each()

- Header file:

      #include<algorithm>

- Function prototype:
  - `Function for_each(InputIterator first, InputIterator last, Function func);`
- Description:
  - Each of the elements implied by the iterator range `[first, last)` is passed in turn to the function `func`. The function may not modify the elements it receives (as the used iterator is an input iterator). If the elements are to be transformed, `transform()` (see section 10.3.63) should be used. The function object is returned: see the example below, in which an extra argument list is added to the `for_each()` call, which argument is eventually also passed to the function given to `for_each()`. Within `for_each()` the returnvalue of the function that is passed to it is ignored.
- Example:

      #include<algorithm>
      #include<string>
      #include<iostream>

      void capitalizedOutput(string const &str)
      {
          char
              *tmp = strcpy(new char[str.size() + 1], str.c_str());

                                  // can't use for_each here,
                                  // as 'tmp' is modified
          transform(tmp + 1, tmp + str.size(), tmp + 1, tolower);

          tmp[0] = toupper(*tmp);
          cout << tmp << " ";
          delete tmp;
      };

      int main()
      {
          string
              sarr[] =
              {
                  "alpha", "BRAVO", "charley", "ECHO", "delta",
                  "FOXTROT", "golf", "HOTEL",
              },
              *last = sarr + sizeof(sarr) / sizeof(string);

          for_each(sarr, last, capitalizedOutput)("that's all, folks");
          cout << endl;

          return(0);
      }

### 10.3.18: generate()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `void generate(ForwardIterator first, ForwardIterator last, Generator generator);`
- Description:
  - all the elements implied by the interator range `[first, last)` are initialized by the returnvalue of `generator`, which can be a function or function object.
- Example:

      #include<algorithm>
      #include<vector>
      #include<iostream>
      #include<iterator>

      class NaturalSquares
      {
          public:
              NaturalSquares(): newsqr(0), last(0)
              {}
              unsigned operator()()
              {                                       // (a + 1)^2 == a^2 + 2*a + 1
                  return (newsqr += (last++ << 1) + 1);
              }

          private:
              unsigned
                  newsqr,
                  last;
      };

      int main()
      {
          vector<unsigned>
              uv(10);

          generate(uv.begin(), uv.end(), NaturalSquares());

          copy(uv.begin(), uv.end(), ostream_iterator<int>(cout, " "));
          cout << endl;

          return(0);
      }

### 10.3.19: generate_n()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `void generate_n(ForwardIterator first, Size n, Generator generator);`
- Description:
  - `n` elements starting at the element pointed to by interator `first` are initialized by the returnvalue of `generator`, which can be a function or function object.
- Example:

      #include<algorithm>
      #include<vector>
      #include<iostream>
      #include<iterator>

      class NaturalSquares
      {
          public:
              NaturalSquares(): newsqr(0), last(0)
              {}
              unsigned operator()()
              {                                       // (a + 1)^2 == a^2 + 2*a + 1
                  return (newsqr += (last++ << 1) + 1);
              }

          private:
              unsigned
                  newsqr,
                  last;
      };

      int main()
      {
          vector<unsigned>
              uv(10);

          generate_n(uv.begin(), 10, NaturalSquares());

          copy(uv.begin(), uv.end(), ostream_iterator<int>(cout, " "));
          cout << endl;

          return(0);
      }

### 10.3.20: includes()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);`
  - `bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);`
- Description:
  - The first prototype: Both sequences of elements implied by the ranges `[first1, last1)` and `[first2, last2)` should be sorted, using the `operator<()` of the underlying datatype. The function returns `true` if every element in the second sequence (`[first2, second2)` is contained in the first sequence (`[first1, second1)`) (the second range is a subset of the first range).
  - The second prototype: Both sequences of elements implied by the ranges `[first1, last1)` and `[first2, last2)` should be sorted, using the `comp` function object. The function returns `true` if every element in the second sequence (`[first2, second2)` is contained in the first seqence (`[first1, second1)`) (the second range is a subset of the first range).
- Example:

      #include <algorithm>
      #include <string>
      #include <iostream>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (!strcasecmp(first.c_str(), second.c_str()));
              }
      };

      int main()
      {
          string
              first1[] =
              {
                  "alpha", "bravo", "charley", "echo", "delta",
                  "foxtrot", "golf", "hotel"
              },
              first2[] =
              {
                  "Alpha", "bravo", "Charley", "echo", "Delta",
                  "foxtrot", "Golf", "hotel"
              },
              second[] =
              {
                  "charley", "foxtrot", "hotel"
              };
          unsigned
              n = sizeof(first1) / sizeof(string);

          cout << "The elements of `second' are " <<
              (includes(first1, first1 + n, second, second + 3) ? "" : "not")
              << " contained in the first sequence: second is a subset of first1\n";

          cout << "The elements of `first1' are " <<
              (includes(second, second + 3, first1, first1 + n) ? "" : "not")
              << " contained in the second sequence\n";

          cout << "The elements of `second' are " <<
              (includes(first2, first2 + n, second, second + 3) ? "" : "not")
              << " contained in the first2 sequence\n";

          cout << "Using case-insensitive comparison,\n"
              "the elements of `second' are "
              <<
              (includes(first2, first2 + n, second, second + 3, CaseString()) ?
                  "" : "not")
              << " contained in the first2 sequence\n";

          return(0);
      }

### 10.3.21: inner_product()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `Type inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Type init);`
  - `Type inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Type init, BinaryOperator1 op1, BinaryOperator2 op2);`
- Description:
  - The first prototype: The sum of all pairwise products of the elements implied by the range `[first1, last1)` and the same number of elements starting at the element pointed to by `first2` are added to `init`, and this sum is returned. The function uses the `operator+()` and `operator*()` of the underlying datatype.
  - The second prototype: Binary operator `op2` instead of the default addition operator, and binary operator `op1` instead of the default multiplication operator are applied to all pairwise elements implied by the range `[first1, last1)` and the same number of elements starting at the element pointed to by `first2`. The final result is returned.
- Example:

      #include <numeric>
      #include <algorithm>
      #include <iostream>
      #include <string>

      class Cat
      {
          public:
              Cat(string const &sep): sep(sep)
              {}
              string operator()(string const &s1, string const &s2)
              {
                  return (s1 + sep + s2);
              }
          private:
              string
                  sep;
      };

      int main()
      {
          unsigned
              ia1[] = {1, 2, 3, 4, 5, 6, 7},
              ia2[] = {7, 6, 5, 4, 3, 2, 1},
              init = 0;

          cout << "The sum of all squares in ";
          copy(ia1, ia1 + 7, ostream_iterator<unsigned>(cout, " "));
          cout << "is " <<
              inner_product(ia1, ia1 + 7, ia1, init) << endl;

          cout << "The sum of all cross-products in ";
          copy(ia1, ia1 + 7, ostream_iterator<unsigned>(cout, " "));
          cout << " and ";
          copy(ia2, ia2 + 7, ostream_iterator<unsigned>(cout, " "));
          cout << "is " <<
              inner_product(ia1, ia1 + 7, ia2, init) << endl;

          string
              names1[] = {"Frank", "Karel", "Piet"},
              names2[] = {"Brokken", "Kubat", "Plomp"};

          cout << "A list of all combined names in ";
          copy(names1, names1 + 3, ostream_iterator<string>(cout, " "));
          cout << "and ";
          copy(names2, names2 + 3, ostream_iterator<string>(cout, " "));
          cout << "is:" <<
              inner_product(names1, names1 + 3, names2, string("\t"),
                  Cat("\n\t"), Cat(" ")) <<
              endl;

          return(0);
      }

### 10.3.22: inplace_merge()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);`
  - `void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);`
- Description:
  - The first prototype: The two (sorted) ranges `[first, middle)` and `[middle, last)` are merged, keeping a sorted list (using the `operator<()` of the underlying data type). The final series is stored in the range `[first, last)`.
  - The second prototype: The two (sorted) ranges `[first, middle)` and `[middle, last)` are merged, keeping a sorted list (using the boolean result of the binaray comparison operator `comp`). The final series is stored in the range `[first, last)`.
- Example:

      #include <algorithm>
      #include <string>
      #include <iostream>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (strcasecmp(first.c_str(), second.c_str()) < 0);
              }
      };

      int main()
      {
          string
              range[] =
              {
                  "alpha", "charley", "delta", "foxtrot", "hotel"
                  "bravo", "echo", "golf"
              };

          inplace_merge(range, range + 5, range + 8);
          copy(range, range + 8, ostream_iterator<string>(cout, " "));
          cout << endl;

          string
              range2[] =
              {
                  "ALFA", "CHARLEY", "DELTA", "foxtrot", "hotel"
                  "bravo", "ECHO", "GOLF"
              };

          inplace_merge(range2, range2 + 5, range2 + 8, CaseString());
          copy(range2, range2 + 8, ostream_iterator<string>(cout, " "));
          cout << endl;

          return(0);
      }

### 10.3.23: iter_swap()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `void iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2);`
- Description:
  - The elements pointed to by `iter1` and `iter2` are swapped.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      int main()
      {
          string
              first[] = {"alpha", "bravo", "charley", "delta", "echo", "delta"},
              second[] = {"echo", "foxtrot", "golf", "hotel", "india", "kilo"};
          unsigned
              n = sizeof(first) / sizeof(string);

          cout << "Before:\n";
          copy(first, first + n, ostream_iterator<string>(cout, " "));
          cout << endl;
          copy(second, second + n, ostream_iterator<string>(cout, " "));
          cout << endl;

          for (unsigned idx = 0; idx < n; ++idx)
              iter_swap(first + idx, second + idx);

          cout << "After:\n";
          copy(first, first + n, ostream_iterator<string>(cout, " "));
          cout << endl;
          copy(second, second + n, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.24: lexicographical_compare()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);`
  - `bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);`
- Description:
  - The first prototype: The corresponding pairs of elements in the ranges pointed to by `[first1, last1)` and `[first2, last2)` are compared. The function returns `true`
    - at the first element in the first range which is less than the corresponding element in the second range (using the `operator<()` of the underlying data type),
    - if `last1` is reached, but `last2` isn't reached yet.
    False is returned in the other cases, which indicates that the first sequence is not lexicographical less than the second sequence. I.e., `false` is returned
    - at the first element in the first range which is greater than the corresponding element in the second range (using the `operator<()` of the underlying data type),
    - if `last2` is reached, but `last1` isn't reached yet.
    - if `last1` and `last2` are reached.
  - The second prototype: With this function the binary comparison operation as defined by `comp` is used instead of the underlying `operator<()`.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (strcasecmp(first.c_str(), second.c_str()) < 0);
              }
      };

      int main()
      {
          char const
              word1[] = "help",
              word2[] = "hello";

          cout << word1 << " is " <<
              (
                  lexicographical_compare(word1, word1 + strlen(word1),
                                          word2, word2 + strlen(word2)) ?
                      "before "
                  :
                      "beyond or at "
              ) <<
              word2 << " in the alphabet\n";

          cout << word1 << " is " <<
              (
                  lexicographical_compare(word1, word1 + strlen(word1),
                                          word1, word1 + strlen(word1)) ?
                      "before "
                  :
                      "beyond or at "
              ) <<
              word1 << " in the alphabet\n";

          cout << word2 << " is " <<
              (
                  lexicographical_compare(word2, word2 + strlen(word2),
                                          word1, word1 + strlen(word1)) ?
                      "before "
                  :
                      "beyond or at "
              ) <<
              word1 << " in the alphabet\n";

          string
              one[] = {"alpha", "bravo", "charley"},
              two[] = {"ALPHA", "BRAVO", "DELTA"};

          copy(one, one + 3, ostream_iterator<string>(cout, " "));
          cout << " is ordered " <<
              (
                  lexicographical_compare(one, one + 3,
                                          two, two + 3, CaseString()) ?
                      "before "
                  :
                      "beyond or at "
              );
          copy(two, two + 3, ostream_iterator<string>(cout, " "));
          cout << endl <<
              "using case-insensitive comparisons.\n";

          return (0);
      }

### 10.3.25: lower_bound()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value);`
  - `ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value, Compare comp);`
- Description:
  - The first prototype: The sorted elements implied by the iterator range `[first, last)` are searched for the first element that that is not less than (i.e., greater than or equal to) `value`. The returned iterator marks the location in the sequence where `value` can be inserted without breaking the sorted order of the elements. The `operator<()` of the underlying datatype is used. If no such element is found, `last` is returned.
  - The second prototype: The elements implied by the iterator range `[first, last)` must have been sorted using the `comp` function (-object). Each element in the range is compared to `value` using the `comp` function. An iterator to the first element for which the binary predicate `comp`, applied to the elements of the range and `value`, returns `false` is returned. If no such element is found, `last` is returned.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <functional>

      int main()
      {
          int
              ia[] = {10, 20, 30};

          cout << "Sequence: ";
          copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
          cout << endl;

          cout << "15 can be inserted before " <<
                  *lower_bound(ia, ia + 3, 15) << endl;
          cout << "35 can be inserted after " <<
                  (lower_bound(ia, ia + 3, 35) == ia + 3 ?
                                      "the last element" : "???") << endl;

          iter_swap(ia, ia + 2);

          cout << "Sequence: ";
          copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
          cout << endl;

          cout << "15 can be inserted before " <<
                  *lower_bound(ia, ia + 3, 15, greater<int>()) << endl;
          cout << "35 can be inserted before " <<
                  (lower_bound(ia, ia + 3, 35, greater<int>()) == ia ?
                                      "the first element " : "???") << endl;

          return (0);
      }

### 10.3.26: max()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `Type const &max(Type const &one, Type const &two);`
  - `Type const &max(Type const &one, Type const &two, Comparator comp);`
- Description:
  - The first prototype: The larger of the two elements `one` and `two` is returned, using the `operator>()` of the underlying type.
  - The second prototype: `one` is returned if the binary predicate `comp(one, two)` returns `true`, otherwise `two` is returned.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (strcasecmp(second.c_str(), first.c_str()) > 0);
              }
      };

      int main()
      {
          cout << "Word '" << max(string("first"), string("second")) <<
                                      "' is lexicographically last\n";

          cout << "Word '" << max(string("first"), string("SECOND")) <<
                                      "' is lexicographically last\n";

          cout << "Word '" << max(string("first"), string("SECOND"),
                              CaseString()) << "' is lexicographically last\n";

          return (0);
      }

### 10.3.27: max_element()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator max_element(ForwardIterator first, ForwardIterator last);`
  - `ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Comparator comp);`
- Description:
  - The first prototype: An iterator pointing to the largest element in the range implied by `[first, last)` is returned. The `operator>()` of the underlying type is used.
  - The second prototype: rather than using `operator>()`, the binary predicate `comp` is used to make the comparisons between the elements implied by the iterator range `[first, last)`. The element with which `comp` returns most often `true` is returned.
- Example:

      #include <algorithm>
      #include <iostream>

      class AbsValue
      {
          public:
              bool operator()(int first, int second) const
              {
                  return (abs(second) > abs(first));
              }
      };

      int main()
      {
          int
              ia[] = {-4, 7, -2, 10, -12};

          cout << "The maximum int value is " << *max_element(ia, ia + 5) << endl;
          cout << "The maximum absolute int value is " <<
                  *max_element(ia, ia + 5, AbsValue()) << endl;

          return (0);
      }

### 10.3.28: merge()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: The two (sorted) ranges `[first, middle)` and `[middle, last)` are merged, keeping a sorted list (using the `operator<()` of the underlying data type). The final series is stored in the range starting at `result` and ending just before the OutputIterator that is returned by the function.
  - The second prototype: The two (sorted) ranges `[first, middle)` and `[middle, last)` are merged, keeping a sorted list (using the boolean result of the binaray comparison operator `comp`). The final series is stored in the range starting at `result` and ending just before the OutputIterator that is returned by the function.
- Example:

      #include <algorithm>
      #include <string>
      #include <iostream>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (strcasecmp(first.c_str(), second.c_str()) < 0);
              }
      };

      int main()
      {
          string
              range1[] =
              {
                  "alpha", "bravo", "foxtrot", "hotel", "zulu"
              },
              range2[] =
              {
                  "delta", "echo", "golf", "romeo"
              },
              result[5 + 4];

          copy(result,
              merge(range1, range1 + 5, range2, range2 + 4, result),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          string
              range3[] =
              {
                  "ALPHA", "bravo", "foxtrot", "HOTEL", "ZULU"
              },
              range4[] =
              {
                  "delta", "ECHO", "GOLF", "romeo"
              };

          copy(result,
              merge(range3, range3 + 5, range4, range4 + 4, result, CaseString()),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          return(0);
      }

### 10.3.29: min()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `Type const &min(Type const &one, Type const &two);`
  - `Type const &min(Type const &one, Type const &two, Comparator comp);`
- Description:
  - The first prototype: The smaller of the two elements `one` and `two` is returned, using the `operator<()` of the underlying type.
  - The second prototype: `one` is returned if the binary predicate `comp(one, two)` returns `false`, otherwise `two` is returned.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (strcasecmp(second.c_str(), first.c_str()) > 0);
              }
      };

      int main()
      {
          cout << "Word '" << min(string("first"), string("second")) <<
                                      "' is lexicographically first\n";

          cout << "Word '" << min(string("first"), string("SECOND")) <<
                                      "' is lexicographically first\n";

          cout << "Word '" << min(string("first"), string("SECOND"),
                              CaseString()) << "' is lexicographically first\n";

          return (0);
      }

### 10.3.30: min_element()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator min_element(ForwardIterator first, ForwardIterator last);`
  - `ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Comparator comp);`
- Description:
  - The first prototype: An iterator pointing to the smallest element in the range implied by `[first, last)` is returned. The `operator<()` of the underlying type is used.
  - The second prototype: rather than using `operator<()`, the binary predicate `comp` is used to make the comparisons between the elements implied by the iterator range `[first, last)`. The element with which `comp` returns most often `false` is returned.
- Example:

      #include <algorithm>
      #include <iostream>

      class AbsValue
      {
          public:
              bool operator()(int first, int second) const
              {
                  return (abs(second) > abs(first));
              }
      };

      int main()
      {
          int
              ia[] = {-4, 7, -2, 10, -12};

          cout << "The minimum int value is " << *min_element(ia, ia + 5) << endl;
          cout << "The minimum absolute int value is " <<
                  *min_element(ia, ia + 5, AbsValue()) << endl;

          return (0);
      }

### 10.3.31: mismatch()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);`
  - `pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Compare comp);`
- Description:
  - The first prototype: The two sequences of elements starting at `first1` and `first2` are compared using the equality operator of the underlying data type. Comparison stops if the compared elements differ (i.e., `operator==()` returns false) or `last1` is reached. A `pair` containing iterators pointing to the final positions is returned. The second sequence may contain more elements than the first sequence. The behavior of the algorithm is undefined if the second sequence contains less elements than the first sequence.
  - The second prototype: The two sequences of elements starting at `first1` and `first2` are compared using With this function the binary comparison operation as defined by `comp` is used instead of the underlying `operator==()`. Comparison stops if the `comp` function returns `false` or `last1` is reached. A `pair` containing iterators pointing to the final positions is returned. The second sequence may contain more elements than the first sequence. The behavior of the algorithm is undefined if the second sequence contains less elements than the first sequence.
- Example:

      #include <algorithm>
      #include <string>
      #include <iostream>
      #include <utility>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (strcasecmp(first.c_str(), second.c_str()) == 0);
              }
      };

      int main()
      {
          string
              range1[] =
              {
                  "alpha", "bravo", "foxtrot", "hotel", "zulu"
              },
              range2[] =
              {
                  "alpha", "bravo", "foxtrot", "Hotel", "zulu"
              };

          pair<string *, string *>
              pss = mismatch(range1, range1 + 5, range2);

          cout << "The elements " << *pss.first << " and " << *pss.second <<
                  " at offset " << (pss.first - range1) << " differ\n";
          if
          (
              mismatch(range1, range1 + 5, range2, CaseString()).first
              == range1 + 5
          )
              cout << "When compared case-insensitively they match\n";

          return(0);
      }

### 10.3.32: next_permutation()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);`
  - `bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);`
- Description:
  - The first prototype: The next permutation given the sequence of elements in the range `[first, last)` is determined. The elements in the range are reordered. The value `true` is returned if a reordering took place, the value `false` is returned if no reordering took place, which is the case if the resulting sequence would haven been ordered, according to the `operator<()` of the underlying data type.
  - The second prototype: The next permutation given the sequence of elements in the range `[first, last)` is determined. The elements in the range are reordered. The value `true` is returned if a reordering took place, the value `false` is returned if no reordering took place, which is the case if the resulting sequence would haven been ordered, using the binary predicate `comp` to compare two elements.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (strcasecmp(first.c_str(), second.c_str()) < 0);
              }
      };

      int main()
      {
          string
              saints[] = {"Oh", "when", "the", "saints"};

          cout << "All permutations of 'Oh when the saints':\n";

          cout << "Sequences:\n";
          do
          {
              copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
              cout << endl;
          }
          while (next_permutation(saints, saints + 4, CaseString()));

          cout << "After first sorting the sequence:\n";

          sort(saints, saints + 4, CaseString());

          cout << "Sequences:\n";
          do
          {
              copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
              cout << endl;
          }
          while (next_permutation(saints, saints + 4, CaseString()));

          return (0);
      }

### 10.3.33: nth_element()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);`
  - `void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: All elements in the range `[first, last)` are sorted relative to the element pointed to by `nth`: all elements in the range `[left, nth)` are smaller than the element pointed to by `nth`, and alle elements in the range `[nth + 1, last)` are greater than the element pointed to by `nth`. The two subsets themselves are not sorted. The `operator<()` of the underlying datatype is used.
  - The second prototype: All elements in the range `[first, last)` are sorted relative to the element pointed to by `nth`: all elements in the range `[left, nth)` are smaller than the element pointed to by `nth`, and alle elements in the range `[nth + 1, last)` are greater than the element pointed to by `nth`. The two subsets themselves are not sorted. The `comp` function object is used to compare the elements.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <functional>

      int main()
      {
          int
              ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};

          nth_element(ia, ia + 3, ia + 10);
          copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
          cout << endl;

          nth_element(ia, ia + 5, ia + 10, greater<int>());
          copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.34: partial_sort()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);`
  - `void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: The `middle - first` smallest elements are sorted and stored in the `[first, middle)`, using the `operator<()` of the underlying datatype. The remaining elements of the series remain unsorted.
  - The second prototype: The `middle - first` smallest elements (according to the provided binary predicate `comp` are sorted and stored in the `[first, middle)`. The remaining elements of the series remain unsorted.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <functional>

      int main()
      {
          int
              ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};

          partial_sort(ia, ia + 3, ia + 10);
          copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
          cout << endl;

          partial_sort(ia, ia + 5, ia + 10, greater<int>());
          copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.35: partial_sort_copy()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator dest_first, RandomAccessIterator dest_last);`
  - `void partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator dest_first, RandomAccessIterator dest_last, Compare comp);`
- Description:
  - The first prototype: The smallest elements in the range `[first, last)` are copied to the range `[dest_first, dest_last)`, using the `operator<()` of the underlying datatype. Only the number of elements in the smaller range are copied to the second range.
  - The second prototype: The elements in the range `[first, last)` are are sorted by the binary predicate `comp`. The elements for which the predicate returns most often `true` are copied to the range `[dest_first, dest_last)`. Only the number of elements in the smaller range are copied to the second range.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <functional>

      int main()
      {
          int
              ia[] = {1, 10, 3, 8, 5, 6, 7, 4, 9, 2},
              ia2[6];

          partial_sort_copy(ia, ia + 10, ia2, ia2 + 6);
          copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
          cout << endl;
          copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
          cout << endl;

          partial_sort_copy(ia, ia + 4, ia2, ia2 + 6);
          copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
          cout << endl;

          partial_sort_copy(ia, ia + 4, ia2, ia2 + 6, greater<int>());
          copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.36: partial_sum()

- Header files:

              #include<numeric>

- Function prototypes:
  - `OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);`
  - `OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation op);`
- Description:
  - The first prototype: the value of each element in the range `[result, <returned OutputIterator>)` is obtained by adding the elements in the corresponding range of the range `[first, last)`. The first element in the resulting range will be equal to the element pointed to by `first`.
  - The second prototype: the value of each element in the range `[result, <returned OutputIterator>)` is obtained by applying the binary operator `op` to the previous element in the resulting range and the corresponding element in the range `[first, last)`. The first element in the resulting range will be equal to the element pointed to by `first`.
- Example:

      #include <numeric>
      #include <algorithm>
      #include <iostream>
      #include <functional>

      int main()
      {
          int
              ia[] = {1, 2, 3, 4, 5},
              ia2[5];

          copy(ia2,
              partial_sum(ia, ia + 5, ia2),
              ostream_iterator<int>(cout, " "));
          cout << endl;

          copy(ia2,
              partial_sum(ia, ia + 5, ia2, multiplies<int>()),
              ostream_iterator<int>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.37: partition()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);`
- Description:
  - All elements in the range `[first, last)` for which the unary predicate `pred` evaluates as `true` are placed before the elements which evaluate as `false`. The returnvalue points just beyond the last element in the partitioned range for which `pred` evaluates as `true`.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class LessThan
      {
          public:
              LessThan(int x): x(x)
              {}
              bool operator()(int value)
              {
                  return (value <= x);
              }
          private:
              int
                  x;
      };

      int main()
      {
          int
              ia[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4},
              *split;

          split = partition(ia, ia + 10, LessThan(ia[9]));
          cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";

          copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
          cout << endl;
          return (0);
      }

### 10.3.38: prev_permutation()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);`
  - `bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);`
- Description:
  - The first prototype: The previous permutation given the sequence of elements in the range `[first, last)` is determined. The elements in the range are reordered. The value `true` is returned if a reordering took place, the value `false` is returned if no reordering took place, which is the case if the provided sequence was already ordered, according to the `operator<()` of the underlying data type.
  - The second prototype: The previous permutation given the sequence of elements in the range `[first, last)` is determined. The elements in the range are reordered. The value `true` is returned if a reordering took place, the value `false` is returned if no reordering took place, which is the case if the original sequence was already ordered, using the binary predicate `comp` to compare two elements.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (strcasecmp(first.c_str(), second.c_str()) < 0);
              }
      };

      int main()
      {
          string
              saints[] = {"Oh", "when", "the", "saints"};

          cout << "All previous permutations of 'Oh when the saints':\n";

          cout << "Sequences:\n";
          do
          {
              copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
              cout << endl;
          }
          while (prev_permutation(saints, saints + 4, CaseString()));

          cout << "After first sorting the sequence:\n";

          sort(saints, saints + 4, CaseString());

          cout << "Sequences:\n";
          while (prev_permutation(saints, saints + 4, CaseString()))
          {
              copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
              cout << endl;
          }

          cout << "No (more) previous permutations\n";

          return (0);
      }

### 10.3.39: random_shuffle()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);`
  - `void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator rand);`
- Description:
  - The first prototype: The elements in the range `[first, last)` are randomly reordered.
  - The second prototype: The elements in the range `[first, last)` are randomly reordered, using the `rand` random number generator, which should return an `int` in the range `[0, remaining)`, where `remaining` is passed as argument to the `operator()()` of the `rand` function object.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>
      #include <time.h>

      class randomGenerator
      {
          public:
              randomGenerator()
              {
                  srand(static_cast<int>(time(0)));
              }
              int operator()(int remaining) const
              {
                  return (rand() % remaining);
              }
      };

      int main()
      {
          string
              words[] =
              { "kilo", "lima", "mike", "november", "oscar", "papa", "quebec" };
          unsigned
              size = sizeof(words) / sizeof(string);

          random_shuffle(words, words + size);

          copy(words, words + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          cout << "sorting the words again\n";
          sort(words, words + size);

          randomGenerator
              rg;
          random_shuffle(words, words + size, rg);

          copy(words, words + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.40: remove()

- Header file:

      #include<algorithm>

- Function prototype:
  - `ForwardIterator remove(ForwardIterator first, ForwardIterator last, Type &value);`
- Description:
  - The elements in the range pointed to by `[first, last)` are reordered in such a way that all values unequal to `value` are placed at the beginning of the range. The returned forward iterator points to the first element, after reordering, that can be removed. The range `[returnvalue, last)` is called the leftover of the algorithm. The leftover may contain other values than `value`, but these can also safely be removed, as they are also present in the range `[first, returnvalue)`.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      int main()
      {
          string
              words[] =
              { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                  "oscar", "alpha", "alpha", "papa", "quebec" },
              *removed;
          unsigned
              size = sizeof(words) / sizeof(string);

          cout << "Removing all \"alpha\"s:\n";
          removed = remove(words, words + size, "alpha");
          copy(words, removed, ostream_iterator<string>(cout, " "));
          cout << endl
               << "Trailing elements are:\n";
          copy(removed, words + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.41: remove_copy()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, Type &value);`
- Description:
  - The elements in the range pointed to by `[first, last)` not matching `value` are copied to the range `[result, returnvalue)`, where `returnvalue` is the value returned by the function. The range `[first, last)` is not modified.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>
      #include <vector>
      #include <functional>

      class EqualAlpha
      {
          public:
              operator()(string const &word) const
              {
                  return (word == "alpha");
              }
      };

      int main()
      {
          string
              words[] =
              { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                  "oscar", "alpha", "alpha", "papa", "quebec" };
          unsigned
              size = sizeof(words) / sizeof(string);
          string
              remaining[size - count_if(words, words + size, EqualAlpha())],
              *returnvalue;

          returnvalue = remove_copy(words, words + size, remaining, "alpha");

          cout << "Removing all \"alpha\"s:\n";
          copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.42: remove_if()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, UnaryPredicate pred);`
- Description:
  - The elements in the range pointed to by `[first, last)` are reordered in such a way that all values for which the unary predicate `pred` evaluates as `false` are placed at the beginning of the range. The returned forward iterator points to the first element, after reordering, for which `pred` returns `true`. The range `[returnvalue, last)` is called the leftover of the algorithm. The leftover may contain other values than `value`, but these can also safely be removed, as they are also present in the range `[first, returnvalue)`.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class Remover
      {
          public:
              bool operator()(string const &str)
              {
                  return (str == "alpha");
              }
      };

      int main()
      {
          string
              words[] =
              { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                  "oscar", "alpha", "alpha", "papa", "quebec" },
              *removed;
          unsigned
              size = sizeof(words) / sizeof(string);

          cout << "Removing all \"alpha\"s:\n";
          removed = remove_if(words, words + size, Remover());
          copy(words, removed, ostream_iterator<string>(cout, " "));
          cout << endl
               << "Trailing elements are:\n";
          copy(removed, words + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.43: remove_copy_if()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate pred);`
- Description:
  - The elements in the range pointed to by `[first, last)` for which the unary predicate `pred` returns `true` are copied to the range `[result, returnvalue)`, where `returnvalue` is the value returned by the function. The range `[first, last)` is not modified.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>
      #include <vector>
      #include <functional>

      class EqualAlpha
      {
          public:
              bool operator()(string const &word) const
              {
                  return (word == "alpha");
              }
      };

      int main()
      {
          string
              words[] =
              { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                  "oscar", "alpha", "alpha", "papa", "quebec" };
          unsigned
              size = sizeof(words) / sizeof(string);
          string
              remaining[size - count_if(words, words + size, EqualAlpha())],
              *returnvalue;

          returnvalue = remove_copy_if(words, words + size, remaining, EqualAlpha());

          cout << "Removing all \"alpha\"s:\n";
          copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.44: replace()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator replace(ForwardIterator first, ForwardIterator last, Type &oldvalue, Type &newvalue);`
- Description:
  - All elements equal to `oldvalue` in the range pointed to by `[first, last)` are replaced by the value `newvalue`.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      int main()
      {
          string
              words[] =
              { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                  "oscar", "alpha", "alpha", "papa", "quebec" },
              *removed;
          unsigned
              size = sizeof(words) / sizeof(string);

          replace(words, words + size, string("alpha"), string("ALPHA"));
          copy(words, words + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.45: replace_copy()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, Type &oldvalue, Type &newvalue);`
- Description:
  - All elements equal to `oldvalue` in the range pointed to by `[first, last)` are replaced by the value `newvalue` in a new range `[result, returnvalue)`, where `returnvalue` is the returnvalue of the function.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>
      #include <vector>
      #include <functional>
      int main()
      {
          string
              words[] =
              { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                  "oscar", "alpha", "alpha", "papa", "quebec" };
          unsigned
              size = sizeof(words) / sizeof(string);
          string
              remaining[size],
              *returnvalue;

          returnvalue = replace_copy(words, words + size, remaining,
                                      string("alpha"), string("ALPHA"));

          copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.46: replace_if()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator replace_if(ForwardIterator first, ForwardIterator last, UnaryPredicate pred, Type const &value);`
- Description:
  - The elements in the range pointed to by `[first, last)` for which the unary predicate `pred` evaluates as `true` are replaced by `newvalue`.
  `` Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class Replacer
      {
          public:
              bool operator()(string const &str)
              {
                  return (str == "alpha");
              }
      };

      int main()
      {
          string
              words[] =
              { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                  "oscar", "alpha", "alpha", "papa", "quebec" };
          unsigned
              size = sizeof(words) / sizeof(string);

          replace_if(words, words + size, Replacer(), string("ALPHA"));
          copy(words, words + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.47: replace_copy_if()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `OutputIterator replace_copy_if(ForwardIterator first, ForwardIterator last, OutputIterator result, UnaryPredicate pred, Type const &value);`
- Description:
  - The elements in the range pointed to by `[first, last)` are copied to the range `[result, returnvalue)`, where `returnvalue` is the value returned by the function. The elements for which the unary predicate `pred` returns `true` are replaced by `newvalue`. The range `[first, last)` is not modified.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>
      #include <vector>
      #include <functional>

      class Replacer
      {
          public:
              bool operator()(string const &str) const
              {
                  return (str == "alpha");
              }
      };

      int main()
      {
          string
              words[] =
              { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                  "oscar", "alpha", "alpha", "papa", "quebec" };
          unsigned
              size = sizeof(words) / sizeof(string);
          string
              result[size];

          replace_copy_if(words, words + size, result, Replacer(), string("ALPHA"));
          copy (result, result + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.48: reverse()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void reverse(BidirectionalIterator first, BidirectionalIterator last);`
- Description:
  - The elements in the range pointed to by `[first, last)` are reversed.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      int main()
      {
          string
              line;

          while (getline(cin, line))
          {
              reverse(line.begin(), line.end());
              cout << line << endl;
          }

          return (0);
      }

### 10.3.49: reverse_copy()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);`
- Description:
  - The elements in the range pointed to by `[first, last)` are copied to the range `[result, returnvalue)` in reversed order. The value `returnvalue` is the value that is returned by the function.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      int main()
      {
          string
              line;

          while (getline(cin, line))
          {
              unsigned
                  size = line.size();
              char
                  copy[size + 1];

              cout << "line: " << line << endl <<
                      "reversed: ";
              reverse_copy(line.begin(), line.end(), copy);
              copy[size] = 0;     // 0 is not part of the reversed
                                  // line !
              cout << copy << endl;
          }

          return (0);
      }

### 10.3.50: rotate()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);`
- Description:
  - The elements implied by the range `[first, middle)` are moved to the end of the container, the elements implied by the range `[middle, last)` are moved to the beginning of the container.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      int main()
      {
          string
              words[] =
              { "kilo", "lima", "mike", "november", "oscar", "papa", "quebec",
                "echo", "foxtrot", "golf", "hotel", "india", "juliet" };
          unsigned const
              size = sizeof(words) / sizeof(string),
              midsize = 7;

          rotate(words, words + midsize, words + size);

          copy(words, words + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.51: rotate_copy()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);`
- Description:
  - The elements implied by the range `[middle, last)` and then the elements implied by the range `[first, middle)` are copied to the destination container having range `[result, returnvalue)`, where `returnvalue` is the iterator returned by the function.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      int main()
      {
          string
              words[] =
              { "kilo", "lima", "mike", "november", "oscar", "papa", "quebec",
                "echo", "foxtrot", "golf", "hotel", "india", "juliet" };
          unsigned const
              size = sizeof(words) / sizeof(string),
              midsize = 7;
          string
              out[size];

          copy(out,
              rotate_copy(words, words + midsize, words + size, out),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.52: search()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);`
  - `ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);`
- Description:
  - The first prototype: An iterator into the first range `[first1, last1)` is returned where the elements in the range `[first2, last2)` are found, using the `operator==()` operator of the underlying data type. If no such location exists, `last1` is returned.
  - The second prototype: An iterator into the first range `[first1, last1)` is returned where the elements in the range `[first2, last2)` are found, using the provided binary predicate `pred` to compare the elements in the two ranges. If no such location exists, `last1` is returned.
- Example:

      #include <algorithm>
      #include <iostream>

      class absInt
      {
          public:
              bool operator()(int i1, int i2)
              {
                  return (abs(i1) == abs(i2));
              }
      };

      int main()
      {
          int
              range1[] =
                  {-2, -4, -6, -8, 2, 4, 6, 8},
              range2[] =
                  {6, 8};

          copy
          (
              search(range1, range1 + 8, range2, range2 + 2),
              range1 + 8,
              ostream_iterator<int>(cout, " ")
          );
          cout << endl;

          copy
          (
              search(range1, range1 + 8, range2, range2 + 2, absInt()),
              range1 + 8,
              ostream_iterator<int>(cout, " ")
          );
          cout << endl;

          return (0);
      }

### 10.3.53: search_n()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1, Size count, Type const & value);`
  - `ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1, Size count, Type const & value, BinaryPredicate pred);`
- Description:
  - The first prototype: An iterator into the first range `[first1, last1)` is returned where `n` elements having value `value` are found, using the `operator==()` operator of the underlying data type to compare the elements. If no such location exists, `last1` is returned.
  - The second prototype: An iterator into the first range `[first1, last1)` is returned where `n` elements having value `value` are found, using the provided binary predicate `pred` to compare the elements. If no such location exists, `last1` is returned.
- Example:

      #include <algorithm>
      #include <iostream>

      class absInt
      {
          public:
              bool operator()(int i1, int i2)
              {
                  return (abs(i1) == abs(i2));
              }
      };

      int main()
      {
          int
              range1[] =
                  {-2, -4, -4, -6, -8, 2, 4, 4, 6, 8},
              range2[] =
                  {6, 8};

          copy
          (
              search_n(range1, range1 + 8, 2, 4),
              range1 + 8,
              ostream_iterator<int>(cout, " ")
          );
          cout << endl;

          copy
          (
              search_n(range1, range1 + 8, 2, 4, absInt()),
              range1 + 8,
              ostream_iterator<int>(cout, " ")
          );
          cout << endl;

          return (0);
      }

### 10.3.54: set_difference()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `OutputIterator set_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator set_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are not present in the range `[first2, last2)` is returned, starting at `[result)`, and ending at the outputiterator that is returned by the function. The elements in the two ranges must have been sorted using the `operator<()` of the underlying datatype.
  - The second prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are not present in the range `[first2, last2)` is returned, starting at `[result)`, and ending at the outputiterator that is returned by the function. The elements in the two ranges must have been sorted using the `comp` function object.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseLess
      {
          public:
              bool operator()(string const &left, string const &right)
              {
                  return (strcasecmp(left.c_str(), right.c_str()) < 0);
              }
      };

      int main()
      {
          string
              set1[] =
              { "kilo", "lima", "mike", "november",
                  "oscar", "papa", "quebec" },
              set2[] =
              { "papa", "quebec", "romeo"},
              result[7],
              *returned;

          copy(result,
              set_difference(set1, set1 + 7, set2, set2 + 3, result),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          string
              set3[] =
              { "PAPA", "QUEBEC", "ROMEO"};
          copy(result,
              set_difference(set1, set1 + 7, set3, set3 + 3, result,
              CaseLess()),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.55: set_intersection()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are also present in the ranges `[first2, last2)` is returned, starting at `[result)`, and ending at the outputiterator that is returned by the function. The elements in the two ranges must have been sorted using the `operator<()` of the underlying datatype.
  - The second prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are also present in the ranges `[first2, last2)` is returned, starting at `[result)`, and ending at the outputiterator that is returned by the function. The elements in the two ranges must have been sorted using the `comp` function object.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseLess
      {
          public:
              bool operator()(string const &left, string const &right)
              {
                  return (strcasecmp(left.c_str(), right.c_str()) < 0);
              }
      };

      int main()
      {
          string
              set1[] =
              { "kilo", "lima", "mike", "november",
                  "oscar", "papa", "quebec" },
              set2[] =
              { "papa", "quebec", "romeo"},
              result[7],
              *returned;

          copy(result,
              set_intersection(set1, set1 + 7, set2, set2 + 3, result),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          string
              set3[] =
              { "PAPA", "QUEBEC", "ROMEO"};
          copy(result,
              set_intersection(set1, set1 + 7, set3, set3 + 3, result,
              CaseLess()),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.56: set_symmetric_difference()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `OutputIterator set_symmetric_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator set_symmetric_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are not present in the range `[first2, last2)` and those in the range `[first2, last2)` that are not present in the range `[first1, last1)` is returned, starting at `[result)` and ending at the outputiterator that is returned by the function. The elements in the two ranges must have been sorted using the `operator<()` of the underlying datatype.
  - The second prototype: a sorted sequence of the elements a sorted sequence of the elements pointed to by the range `[first1, last1)` that are not present in the range `[first2, last2)` and those in the range `[first2, last2)` that are not present in the range `[first1, last1)` is returned, starting at `[result)` and ending at the outputiterator that is returned by the function. The elements in the two ranges must have been sorted using the `comp` function object.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseLess
      {
          public:
              bool operator()(string const &left, string const &right)
              {
                  return (strcasecmp(left.c_str(), right.c_str()) < 0);
              }
      };

      int main()
      {
          string
              set1[] =
              { "kilo", "lima", "mike", "november",
                  "oscar", "papa", "quebec" },
              set2[] =
              { "papa", "quebec", "romeo"},
              result[7],
              *returned;

          copy(result,
              set_symmetric_difference(set1, set1 + 7, set2, set2 + 3, result),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          string
              set3[] =
              { "PAPA", "QUEBEC", "ROMEO"};
          copy(result,
              set_symmetric_difference(set1, set1 + 7, set3, set3 + 3, result,
              CaseLess()),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.57: set_union()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are also present in the ranges `[first2, last2)` is returned, starting at `[result)`, and ending at the outputiterator that is returned by the function. The elements in the two ranges must have been sorted using the `operator<()` of the underlying datatype.
  - The second prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are also present in the ranges `[first2, last2)` is returned, starting at `[result)`, and ending at the outputiterator that is returned by the function. The elements in the two ranges must have been sorted using the `comp` function object.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseLess
      {
          public:
              bool operator()(string const &left, string const &right)
              {
                  return (strcasecmp(left.c_str(), right.c_str()) < 0);
              }
      };

      int main()
      {
          string
              set1[] =
              { "kilo", "lima", "mike", "november",
                  "oscar", "papa", "quebec" },
              set2[] =
              { "papa", "quebec", "romeo"},
              result[7],
              *returned;

          copy(result,
              set_intersection(set1, set1 + 7, set2, set2 + 3, result),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          string
              set3[] =
              { "PAPA", "QUEBEC", "ROMEO"};
          copy(result,
              set_intersection(set1, set1 + 7, set3, set3 + 3, result,
              CaseLess()),
              ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.58: sort()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void sort( RandomAccessIterator first, RandomAccessIterator last);`
  - `void sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: the elements in the range `[first, last)` are sorted in ascending order, using the `operator<()` of the underlying datatype.
  - The second prototype: the elements in the range `[first, last)` are sorted in ascending order, using the `comp` function object to compare the elements.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>
      #include <functional>

      int main()
      {
          string
              words[] =
              {"november", "kilo", "mike", "lima",
                  "oscar", "quebec", "papa"};

          sort(words, words + 7);
          copy(words, words + 7,
              ostream_iterator<string>(cout, " "));
          cout << endl;

          sort(words, words + 7, greater<string>());
          copy(words, words + 7,
              ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.59: stable_partition()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);`
- Description:
  - All elements in the range `[first, last)` for which the unary predicate `pred` evaluates as `true` are placed before the elements which evaluate as `false`. The relative order of the elements in the container is kept. The returnvalue points just beyond the last element in the partitioned range for which `pred` evaluates as `true`.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class LessThan
      {
          public:
              LessThan(int x): x(x)
              {}
              bool operator()(int value)
              {
                  return (value <= x);
              }
          private:
              int
                  x;
      };

      int main()
      {
          int
              org[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4},
              ia[10],
              *split;

          copy(org, org + 10, ia);
          split = partition(ia, ia + 10, LessThan(ia[9]));
          cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";

          copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
          cout << endl;

          copy(org, org + 10, ia);
          split = stable_partition(ia, ia + 10, LessThan(ia[9]));
          cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";

          copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
          cout << endl;
          return (0);
      }

### 10.3.60: stable_sort()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void stable_sort( RandomAccessIterator first, RandomAccessIterator last);`
  - `void stable_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: the elements in the range `[first, last)` are stable_sorted in ascending order, using the `operator<()` of the underlying datatype. The relative order of the equal elements is kept.
  - The second prototype: the elements in the range `[first, last)` are stable_sorted in ascending order, using the `comp` function object to compare the elements. The relative order of the equal elements is kept.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>
      #include <functional>

      class CmpFirst
      {
          public:
              bool operator()(string const &left, string const &right)
              {
                  return (left[0] < right[0]);
              }
      };

      int main()
      {
          string
              words[] =
              {"piper", "november", "kilo", "mooney", "mike", "lima",
                  "oscar", "quebec", "papa", "netherlands"};

          stable_sort(words, words + 10, CmpFirst());
          copy(words, words + 10,
              ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.61: swap()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `void swap(Type &object1, Type &object2);`
- Description:
  - The elements `object1` and `object2` change values.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      int main()
      {
          string
              first[] = {"alpha", "bravo", "charley", "delta", "echo", "delta"},
              second[] = {"echo", "foxtrot", "golf", "hotel", "india", "kilo"};
          unsigned
              n = sizeof(first) / sizeof(string);

          cout << "Before:\n";
          copy(first, first + n, ostream_iterator<string>(cout, " "));
          cout << endl;
          copy(second, second + n, ostream_iterator<string>(cout, " "));
          cout << endl;

          for (unsigned idx = 0; idx < n; ++idx)
              swap(first[idx], second[idx]);

          cout << "After:\n";
          copy(first, first + n, ostream_iterator<string>(cout, " "));
          cout << endl;
          copy(second, second + n, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.62: swap_ranges()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 result);`
- Description:
  - The elements in the ranges pointed to by `[first1, last1)` are swapped with the elements in the ranges `[result, returnvalue)`, where `returnvalue` is the value returned by the function. The two ranges must be disjoint.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      int main()
      {
          string
              first[] = {"alpha", "bravo", "charley", "delta", "echo", "delta"},
              second[] = {"echo", "foxtrot", "golf", "hotel", "india", "kilo"};
          unsigned
              n = sizeof(first) / sizeof(string);

          cout << "Before:\n";
          copy(first, first + n, ostream_iterator<string>(cout, " "));
          cout << endl;
          copy(second, second + n, ostream_iterator<string>(cout, " "));
          cout << endl;

          swap_ranges(first, first + n, second);

          cout << "After:\n";
          copy(first, first + n, ostream_iterator<string>(cout, " "));
          cout << endl;
          copy(second, second + n, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.63: transform()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperator op);`
  - `OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperator op);`
- Description:
  - The first prototype: the unary operator `op` is applied to each of the elements in the range `[first, last)`, and the resulting values are stored in the range starting at `result`. The returnvalue points just beyond the last generated element.
  - The second prototype: the binary operator `op` is applied to each of the elements in the range `[first, last)` and the corresponding element in the second range starting at `first2`. The resulting values are stored in the range starting at `result`. The returnvalue points just beyond the last generated element.
- Example:

      #include <functional>
      #include <vector>
      #include <algorithm>
      #include <iostream>
      #include <string>
      #include <ctype.h>

      class Caps
      {
          public:
              string operator()(string const &src)
              {
                  string
                      tmp = src;

                  transform(&tmp[0], &tmp[tmp.size()], &tmp[0], toupper);
                  return (tmp);
              }
      };

      int main()
      {
          string
              words[] = {"alpha", "bravo", "charley"};

          copy(words, transform(words, words + 3, words, Caps()),
                  ostream_iterator<string>(cout, " "));
          cout << endl;

          int
              values[] = {1, 2, 3, 4, 5};
          vector<int>
              squares;

          transform(values, values + 5, values,
                      back_inserter(squares), multiplies<int>());

          copy(squares.begin(), squares.end(),
                  ostream_iterator<int>(cout, " "));
          cout << endl;
          return (0);
      }

### 10.3.64: unique()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `ForwardIterator unique(ForwardIterator first, ForwardIterator last);`
  - `ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);`
- Description:
  - The first prototype: Consecutively equal elements (according to the `operator==()` of the underlying data type) in the range pointed to by `[first, last)` are collapsed into a single element. The returned forward iterator marks the leftover of the algorithm, and contains (unique) elements appearing earlier in the range.
  - The second prototype: Consecutive elements in the range pointed to by `[first, last)` for which the binary predicate `pred` returns `true` are collapsed into a single element. The returned forward iterator marks the leftover of the algorithm, and contains (unique) elements appearing earlier in the range.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (!strcasecmp(first.c_str(), second.c_str()));
              }
      };

      int main()
      {
          string
              words[] =
              {"alpha", "alpha", "Alpha", "papa", "quebec" },
              *removed;
          unsigned
              size = sizeof(words) / sizeof(string);

          removed = unique(words, words + size);
          copy(words, removed, ostream_iterator<string>(cout, " "));
          cout << endl
               << "Trailing elements are:\n";
          copy(removed, words + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          removed = unique(words, words + size, CaseString());
          copy(words, removed, ostream_iterator<string>(cout, " "));
          cout << endl
               << "Trailing elements are:\n";
          copy(removed, words + size, ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.65: unique_copy()

- Header file:

      #include<algorithm>

- Function prototypes:
  - `OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);`
  - `OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator Result, BinaryPredicate pred);`
- Description:
  - The first prototype: The elements in the range `[first, last)` are copied to the resulting container, starting at `result`. Consecutively equal elements (according to the `operator==()` of the underlying data type) are copied only once. The returned output iterator points just beyond the last element that was copied.
  - The second prototype: The elements in the range `[first, last)` are copied to the resulting container, starting at `result`. Consecutive elements in the range pointed to by `[first, last)` for which the binary predicate `pred` returns `true` are copied only once. The returned output iterator points just beyond the last element that was copied.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <string>
      #include <vector>
      #include <functional>

      class CaseString
      {
          public:
              bool operator()(string const &first, string const &second) const
              {
                  return (!strcasecmp(first.c_str(), second.c_str()));
              }
      };

      int main()
      {
          string
              words[] = {"oscar", "Alpha", "alpha", "alpha", "papa", "quebec" };
          unsigned
              size = sizeof(words) / sizeof(string);
          vector<string>
              remaining;

          unique_copy(words, words + size,
                                  back_inserter(remaining));

          copy(remaining.begin(), remaining.end(),
                  ostream_iterator<string>(cout, " "));
          cout << endl;

          vector<string>
              remaining2;

          unique_copy(words, words + size,
                                  back_inserter(remaining2), CaseString());

          copy(remaining2.begin(), remaining2.end(),
                  ostream_iterator<string>(cout, " "));
          cout << endl;

          return (0);
      }

### 10.3.66: upper_bound()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const Type &value);`
  - `ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const Type &value, Compare comp);`
- Description:
  - The first prototype: The sorted elements implied by the iterator range `[first, last)` are searched for the first element that that is greater than `value`. The returned iterator marks the location in the sequence where `value` can be inserted without breaking the sorted order of the elements. The `operator<()` of the underlying datatype is used. If no such element is found, `last` is returned.
  - The second prototype: The elements implied by the iterator range `[first, last)` must have been sorted using the `comp` function (-object). Each element in the range is compared to `value` using the `comp` function. An iterator to the first element for which the binary predicate `comp`, applied to the elements of the range and `value`, returns `true` is returned. If no such element is found, `last` is returned.
- Example:

      #include <algorithm>
      #include <iostream>
      #include <functional>

      int main()
      {
          int
              ia[] = {10, 20, 30};

          cout << "Sequence: ";
          copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
          cout << endl;

          cout << "15 can be inserted before " <<
                  *upper_bound(ia, ia + 3, 15) << endl;
          cout << "35 can be inserted after " <<
                  (upper_bound(ia, ia + 3, 35) == ia + 3 ?
                                      "the last element" : "???") << endl;

          iter_swap(ia, ia + 2);

          cout << "Sequence: ";
          copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
          cout << endl;

          cout << "15 can be inserted before " <<
                  *upper_bound(ia, ia + 3, 15, greater<int>()) << endl;
          cout << "35 can be inserted before " <<
                  (upper_bound(ia, ia + 3, 35, greater<int>()) == ia ?
                                      "the first element " : "???") << endl;

          return (0);
      }

### 10.3.67: Heap algorithms

A heap is a form of binary tree represented as an array. In the standard heap, the key of an element is greater or equal to the key of its children. This kind of heap is called a max heap.

A tree in which numbers are keys could be organized as follows:

figure 11: A binary tree representation of a heap

This tree can be organized in an array as follows:

`12, 11, 10, 8, 9, 7, 6, 1, 2, 4, 3, 5`

Here, 12 is the top node. its children are 11 and 10, both less than 12. 11, in turn, has 8 and 9 as its children, while the children of 10 are 7 and 6. 8 has 1 and 2 as its children, 9 has 4 and 3, and finally, 7 has left child 5. 7 doesn't have a right child, and 6 has no children.

Note that the left and right branches are not ordered: 8 is less than 9, but 7 is larger than 6.

The heap is formed by traversing a binary tree level-wise, starting from the top node. The top node is 12, at the zeroth level. At the first level we find 11 and 10. At the second level 6, 7, 8 and 9 are found, etc.

Heaps can be created in containers supporting random access. So, a heap is not, for example, constructed in a list. Heaps can be constructed from an (unsorted) array (using make_heap()). The top-element can be pruned from a heap, followed by reordering the heap (using pop_heap()), a new element can be added to the heap, followed by reordering the heap (using push_heap()), and the elements in a heap can be sorted (using sort_heap(), which invalidates the heap, though).

The following subsections introduce the prototypes of the heap-algorithms, the final subsection provides a small example in which the heap algorithms are used.

10.3.67.1: make_heap()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void make_heap(RandomAccessIterator first, RandomAccessIterator last);`
  - `void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: The elements in the range `[first, last)` are reordered to form a max-heap, using the `operator<()` of the underlying data type.
  - The second prototype: The elements in the range `[first, last)` are reordered to form a heap, using the binary comparison function object `comp` to compare elements.
- Follow this link for a small example of a program using `make_heap()`.

10.3.67.2: pop_heap()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void pop_heap(RandomAccessIterator first, RandomAccessIterator last);`
  - `void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: The first element in the range `[first, last)` is moved to `last - 1`. Then, the elements in the range `[first, last - 1)` are reordered to form a max-heap, using the `operator<()` of the underlying data type.
  - The second prototype: The first element in the range `[first, last)` is moved to `last - 1`. Then, the elements in the range `[first, last - 1)` are reordered to form a heap, using the binary comparison function object `comp` to compare elements.
- Follow this link for a small example of a program using `pop_heap()`.

10.3.67.3: push_heap()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void push_heap(RandomAccessIterator first, RandomAccessIterator last);`
  - `void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: Assuming that the range `[first, last - 2)` contains a valid heap, and the element at `last - 1` contains an element to be added to the heap, the elements in the range `[first, last - 1)` are reordered to form a max-heap, using the `operator<()` of the underlying data type.
  - The second prototype: Assuming that the range `[first, last - 2)` contains a valid heap, and the element at `last - 1` contains an element to be added to the heap, the elements in the range `[first, last - 1)` are reordered to form a heap, using the binary comparison function object `comp` to compare elements.
- Follow this link for a small example of a program using `push_heap()`.

10.3.67.4: sort_heap()

- Header files:

              #include<algorithm>

- Function prototypes:
  - `void sort_heap(RandomAccessIterator first, RandomAccessIterator last);`
  - `void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: Assuming the elements in the range `[first, last)` form a valid max-heap, the elements in the range `[first, last)` are sorted, using the `operator<()` of the underlying data type.
  - The second prototype: Assuming the elements in the range `[first, last)` form a valid heap, the elements in the range `[first, last)` are sorted, using the binary comparison function object `comp` to compare elements.
- Follow this link for a small example of a program using `sort_heap()`.

10.3.67.5: A small example using the heap algorithms

    #include <algorithm>
    #include <iostream>
    #include <functional>

    void show(int *ia, char const *header)
    {
        cout << header << ":\n";
        copy(ia, ia + 20, ostream_iterator<int>(cout, " "));
        cout << endl;
    }

    int main()
    {
        int
            ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
                    11, 12, 13, 14, 15, 16, 17, 18, 19, 20};

        make_heap(ia, ia + 20);
        show(ia, "The values 1-20 in a max-heap");

        pop_heap(ia, ia + 20);
        show(ia, "Removing the first element (now at the end)");

        push_heap(ia, ia + 20);
        show(ia, "Adding 20 (at the end) to the heap again");

        sort_heap(ia, ia + 20);
        show(ia, "Sorting the elements in the heap");

        make_heap(ia, ia + 20, greater<int>());
        show(ia, "The values 1-20 in a heap, using > (and beyond too)");

        pop_heap(ia, ia + 20, greater<int>());
        show(ia, "Removing the first element (now at the end)");

        push_heap(ia, ia + 20, greater<int>());
        show(ia, "Adding 20 (at the end) to the heap again");

        sort_heap(ia, ia + 20, greater<int>());
        show(ia, "Sorting the elements in the heap");

        return (0);
    }

- Next chapter
- Previous chapter
- Table of contents