CONTENTS

Chapter 9. STL Algorithms

This chapter describes all of the algorithms of the C++ standard library. It begins with an overview of all algorithms and some general remarks about the algorithms. It then presents the exact signature of each algorithm and one or more examples of its use.

9.1 Algorithm Header Files

To use the algorithms of the C++ standard library you must include the header file <algorithm>[1]:

   #include <algorithm>

This header file also includes some auxiliary functions. min(), max(). and swap() were presented in Section 4.4.1, and Section 4.4.2. The iter_swap() iterator function was discussed in Section 7.3.3.

Some of the STL algorithms are provided for numeric processing. Thus, they are defined in <numeric>[1]:

   #include <numeric>

In general, Chapter 12 discusses the numeric components of the C++ standard library. However, I decided to discuss the numeric algorithms here because, in my opinion, the fact that they are STL algorithms is more important than the fact that they are used for numeric processing.

When you use algorithms, you often also need function objects and function adapters. These were described in Chapter 8 and are defined in <functional>[2]:

   #include <functional>

9.2 Algorithm Overview

This section presents an overview of all of the C++ standard library algorithms. From it you can get an idea of their abilities and be better able to find the best algorithm to solve a certain problem.

9.2.1 A Brief Introduction

Algorithms were introduced in Chapter 5 along with the STL. In particular, Section 5.4, and Section 5.6, discuss the role of algorithms and some important constraints regarding their use. All STL algorithms process one or more iterator ranges. The first range is usually specified by its beginning and its end. For additional ranges, in most cases you need to pass only the beginning because the end follows from the number of elements of the first range. The caller must ensure that the ranges are valid. That is, the beginning must refer to a previous or the same element of the same container as the end. Additional ranges must have enough elements.

Algorithms work in overwrite mode rather than in insert mode. Thus, the caller must ensure that destination ranges have enough elements. You can use special insert iterators (see Section 7.4.2) to switch from overwrite to insert mode.

To increase their flexibility and power, several algorithms allow the user to pass user-defined operations, which they call internally. These operations might be ordinary functions or function objects. If these functions return a Boolean value they are called predicates. You can use predicates for the following tasks:

Note that predicates should not modify their state due to a function call (see Section 8.1.4).

See Section 5.8, Section 5.9, and Chapter 8 for examples and details about functions and function objects that are used as algorithm parameters.

9.2.2 C1assification of Algorithms

Different algorithms meet different needs. Thus, they can be c1assified by their main purposes. For example, some algorithms operate as read only, some modify elements, and some change the order of elements. This subsection gives you a brief idea of the functionality of each algorithm and in which aspect it differs from similar algorithms.

The name of an algorithm gives you a first impression of its purpose. The designers of the STL introduced two special suffixes:

  1. The _if suffix

    The _if suffix is used when you can call two forms of an algorithm that have the same number of parameters either by passing a value or by passing a function or function object. In this case, the version without the suffix is used for values, and the version with the _if suffix is used for functions and function objects. For example, find() searches for an element that has a certain value, whereas find_if() searches for an element that meets the criterion passed as a function or function object.

    However, not all algorithms that have a parameter for functions and function objects have the _if suffix. When the function or function object version of an algorithm has an additional argument, it has the same name. For example, min_element() called with two arguments returns the minimum element in the range according to a comparison with operator <. If you pass a third element, it is used as comparison criterion.

  2. The _copy suffix

    The _copy suffix is used as an indication that elements are not only manipulated but also copied into a destination range. For example, reverse() reverses the order of elements inside a range, whereas reverse_copy() copies the elements into another range in reverse order.

The following subsections and sections describe the algorithms according to the following c1assification:

If algorithms belong to more than one category I describe them in the category that I consider to be the most important.

Nonmodifying Algorithms

Nonmodifying algorithms neither change the order nor the value of the elements they process. They operate with input and forward iterators; therefore, you can call them for all standard containers. Table 9.1 lists the nonmodifying algorithms of the C++ standard library. See page 330 for nonmodifying algorithms that are provided especially for sorted input ranges.

Table 9.1. Nonmodifying Algorithms
Name Effect Page
for_each() Performs an operation for each element 334
count() Returns the number of elements 338
count()_if() Returns the number of elements that match a criterion 338
min_element() Returns the element with the smallest value 340
max_element() Returns the element with the largest value 340
find() Searches for the first element with the passed value 341
find_if() Searches for the first element that matches a criterion 341
search_n() Searches for the first n consecutive elements with certain properties 344
search() Searches for the first occurrence of a subrange 347
find_end() Searches for the last occurrence of a subrange 350
find_first_of() Searches the first of several possible elements 352
adjacent_find() Searches for two adjacent elements that are equal(by some criterion) 354
equal() Returns whether two ranges are equal 356
mismatch() Returns the first elements of two sequences that differ 358
lexicographical_compare() Returns whether a range is lexicographically less than another range 360

One of the most important algorithms is for_each(). for_each() calls an operation provided by the caller for each element. That operation is usually used to process each element of the range individually. For example, you can pass for_each() a function that prints each element. However, for_each() can also call a modifying operation for the elements. So for_each() can be used as both a nonmodifying and a modifying algorithm. However, you should avoid using for_each() when possible, and use other algorithms to meet your needs because the other algorithms are implemented specifically for that purpose.

Several of the nonmodifying algorithms perform searching. Unfortunately, the naming scheme of searching algorithms is a mess. In addition, the naming schemes of searching algorithms and searching string functions differ (Table 9.2). As is often the case, there are historical reasons for this. First, the STL and string c1asses were designed independently. Second, the find_end(), find_first_of(), and search_n() algorithms were not part of the original STL. So, for example, by accident the name find_end() instead of search_end() was chosen (it is easy to forget aspects of the whole picture, such as consistency, when you are caught up in the details). Also by accident, a form of search_n() breaks the general concept of the original STL. See page 346 for a description of this problem.

Table 9.2. Comparison of Searching String Operations and Algorithms
Search for String Function STL Algorithm
First occurrence of one element find() find()
Last occurrence of one element rfind() find() with reverse iterators
First occurrence of a subrange find() search()
Last occurrence of a subrange rfind() find_end()
First occurrence of several elements find_first_of() find_first_of()
Last occurrence of several elements find_last_of() find_ first_of() with reverse iterators
First occurrence of n consecutive Elements   search_n()
Modifying Algorithms

Modifying algorithms change the value of elements. They might modify the elements of a range directly or modify them while they are being copied into another range. If elements are copied into a destination range, the source range is not changed. Table 9.3 lists the modifying algorithms of the C++ standard library.

The fundamental modifying algorithms are for_each() (again) and transform(). You can use both to modify elements of a sequence. However, their behavior differs as follows:

Table 9.3. Modifying Algorithms
Name Effect Page
for_each() Performs an operation for each element 334
copy() Copies a range starting with the first element 363
copy _backward() Copies a range starting with the last element 363
transform() Modifies (and copies) elements; combines elements of two ranges 367
merge() Merges two ranges 416
swap_ranges() Swaps elements of two ranges 370
fill() Replaces each element with a given value 372
fill_n() Replaces n elements with a given value 372
generate() Replaces each element with the result of an operation 373
generate_n() Replaces n elements with the result of an operation 373
replace() Replaces elements that have a special value with another value 375
replace()_if() Replaces elements that match a criterion with another value 375
replace_copy() Replaces elements that have a special value while copying the whole range 376
replace_copy_if() Replaces elements that match a criterion while copying the whole range 376

The approach of transform() is a bit slower because it returns and assigns the result instead of modifying the element directly. However, it is more flexible because it can also be used to modify elements while they are being copied into a different destination sequence, transform() also has another version, one that can process and combine elements of two source ranges.

Strictly speaking, merge() does not necessarily have to be part of the list of modifying algorithms. This is because it requires that its input ranges must be sorted. So it should be part of the algorithms for sorted ranges (see page 330). However, in practice, merge() also merges the elements of unsorted ranges. Of course, then the result is unsorted. Nevertheless, to be safe you should call merge() only for sorted ranges.

Note that elements of associative algorithms are constant to ensure that you can't compromise the sorted order of the elements due to an element modification. Therefore, you can't use associative containers as a destination for modifying algorithms.

In addition to these modifying algorithms, the C++ standard library provides modifying algorithms for sorted ranges. See page 330 for details.

Removing Algorithms

Removing algorithms are a special form of modifying algorithms. They can remove the elements either in a single range or while they are being copied into another range. As with modifying algorithms, you can't use an associative container as a destination because the elements of the associative container are considered to be constant. Table 9.4 lists the removing algorithms of the C++ standard library.

Table 9.4. Removing Algorithms
Name Effect Page
remove() Removes elements with a given value 378
remove_if() Removes elements that match a given criterion 378
remove_copy() Copies elements that do not match a given value 380
remove_copy()_if() Copies elements that do not match a given criterion 380
unique() Removes adjacent duplicates (elements that are equal to their predecessor) 381
unique_copy() Copies elements while removing adjacent duplicates 384

Note that removing algorithms remove elements logically only by overwriting them with the following elements that were not removed. Thus, they do not change the number of elements in the ranges on which they operate. Instead, they return the position of the new "end" of the range. It's up to the caller to use that new end, such as to remove the elements physically. See Section 5.6.1, for a detailed discussion of this behavior.

Mutating Algorithms

Mutating algorithms are algorithms that change the order of elements (and not their values) by assigning and swapping their values. Table 9.5 lists the mutating algorithms of the C++ standard library. As with modifying algorithms, you can't use an associative container as a destination because the elements of the associative container are considered to be constant.

Table 9.5. Mutating Algorithms
Name Effect Page
reverse() Reverses the order of the elements 386
reverse_copy() Copies the elements while reversing their order 386
rotate() Rotates the order of the elements 388
rotate_copy() Copies the elements while rotating their order 389
next_permutation() Permutates the order of the elements 391
prev_permutation() Permutates the order of the elements 391
random_shuffle() Brings the elements into a random order 393
partition() Changes the order of the elements so that elements that match a criterion are at the front 395
stable_partition() Same as partition() but preserves the relative order of matching and nonmatching elements 395
Sorting Algorithms

Sorting algorithms are a special kind of mutating algorithm because they also change the order of the elements. However, sorting is more complicated and therefore usually takes more time than simple mutating operations. In fact, these algorithms usually have worse than linear complexity[3] and require random access iterators (for the destination). Table 9.6 lists the sorting algorithms.

Table 9.6. Sorting Algorithms
Name Effect Page
sort() Sorts all elements 397
stable_sort() Sorts while preserving order of equal elements 397
partial_sort() Sorts until the first n elements are correct 400
partial_sort_copy() Copies elements in sorted order 402
nth_element() Sorts according to the nth position 404
partition() Changes the order of the elements so that elements that match a criterion are at the front 395
stable_partition() Same as partition() but preserves the relative order of matching and nonmatching elements 395
make_heap() Converts a range into a heap 406
push_heap() Adds an element to a heap 406
pop_heap() Removes an element from a heap 407
sort_heap() Sorts the heap (it is no longer a heap after the call) 407

Time often is critical for sorting algorithms. Therefore, the C++ standard library provides more than one sorting algorithm. The algorithms use different ways of sorting, and some algorithms don't sort all elements. For example, nth_element() stops when the nth element of the sequence is correct according to the sorting criterion. For the other elements it guarantees only that the previous elements have a lesser or equal value and that the following elements have a greater or equal value. To sort all elements of a sequence, you should consider the following algorithms:

Now you have a brief idea of which sorting algorithm might best meet your needs. But the story doesn't end here. The standard guarantees complexity, but not how it is implemented. This is an advantage in that an implementation could benefit from algorithm innovations and use a better way of sorting without breaking the standard. For example, the sort() algorithm in the SGI implementation of the STL is implemented by using introsort. Introsort is a new algorithm that, by default, operates like quicksort, but switches to heapsort when it is going to have quadratic complexity. The disadvantage of the fact that the standard does not guarantee exact complexity is that an implementation could use a standard-conforming but very bad algorithm. For example, using heapsort to implement sort() would be standard conforming. Of course, you simply could test which algorithm fits best, but be aware that measurements might not be portable.

There are even more algorithms to sort elements. For example, the heap algorithms are provided to call the functions that implement a heap directly (a heap is a binary tree, which is used internally by heapsort). The heap algorithms are provided and used as the base for efficient implementations of priority queues (see Section 10.3). You can use them to sort all elements of a collection by calling them as follows:

   /*sort all elements
    *-n+n*log(n) complexity
    */
   make_heap (coll.begin(), coll.end());
   sort_heap (coll.begin(), coll.end());

See Section 9.9.4, for details about heaps and heap algorithms.

The nth_element() algorithms are provided if you need only the nth sorted element or the set of the n highest or n lowest elements (not sorted). Thus, nth_element() is a way to split elements into two subsets according to a sorting criterion. However, you could also use partition() or stable_partition() to do this. The difference is as follows:

You can always pass the sorting criterion to all sorting algorithms as an optional argument. The default sorting argument is the function object less<>, so that elements are sorted in ascending order of their values.

As with modifying algorithms, you can't use an associative container as a destination because the elements of the associative containers are considered to be constant.

Lists do not provide random access iterators, so you can't call sorting algorithms for them either. However, lists provide a member function sort() to sort their elements; see page 245.

Sorted Range Algorithms

Sorted range algorithms require that the ranges on which they operate are sorted according to their sorting criterion. Table 9.7 lists all algorithms of the C++ standard library that are especially written for sorted ranges. Like associative containers, these algorithms have the advantage of a better complexity.

Table 9.7. Algorithms for Sorted Ranges
Name Effect Page
binary_search() Returns whether the range contains an element 410
includes() Returns whether each element of a range is also an element of another range 411
lower_bound() Finds the first element greater than or equal to a given value 413
upper _bound() Finds the first element greater than a given value 413
equal_range() Returns the range of elements equal to a given value 415
merge() Merges the elements of two ranges 416
set_union() Processes the sorted union of two ranges 418
set.intersection() Processes the sorted intersection of two ranges 419
set_difference() Processes a sorted range that contains all elements of a range that are not part of another 420
set_symmetric_difference() Processes a sorted range that contains all elements that are in exactly one of two ranges 421
inplace_merge() Merges two consecutive sorted ranges 423

The first five sorted range algorithms in Table 9.7 are nonmodifying because they search only according to their purpose. The other algorithms combine two sorted input ranges and write the result to a destination range. In general, the result of these algorithms is also sorted.

Numeric Algorithms

These algorithms combine numeric elements in different ways. Table 9.8 lists the numeric algorithms of the C++ standard library. If you understand the names, you get an idea of the purpose of the algorithms. However, these algorithms are more flexible and more powerful than they may seem at first. For example, by default, accumulate() processes the sum of all elements. When you use strings as elements, you concatenate them using this algorithm. When you switch from operator + to operator *, you get the product of all elements. As another example, you should know that adjacent_difference() and partial_sum() transfer a range of absolute values into a range of relative values and vice versa.

accumulate() and inner_product() process and return a single value without modifying the ranges. The other algorithms write the results to a destination range that has the same number of elements as the source range.

Table 9.8. Numeric Algorithms
Name Effect Page
accumulate() Combines all element values (processes sum, product, and so forth) 425
inner_product() Combines all elements of two ranges 427
adjacent_difference() Combines each element with its predecessor 431
partial_sum() Combines each element with all of its predecessors 429

9.3 Auxiliary Functions

The rest of this chapter discusses the algorithms in detail. It includes at least one example of each algorithm. To simplify the examples, I use some auxiliary functions so that you can concentrate on the essence of the examples:

   // algo/algostuff.hpp

    #ifndef ALGOSTUFF_HPP
    #define ALGOSTUFF_HPP


    #include <iostream>
    #include <vector>
    #include <deque>
    #include <list>
    #include <set>
    #include <map>
    #include <string>
    #include <algorithm>
    #include <functional>
    #include <numeric>


    /*PRINT_ELEMENTS()
     *-prints optional C-string optcstr followed by
     *-all elements of the collection coll
     *-separated by spaces
     */
    template <c1ass T>
    inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
    {
        typename T::const_iterator pos;
        std::cout << optcstr;
        for (pos=coll.begin(); pos!=coll.end(); ++pos) {
            std::cout << *pos << ' ';
        }
        std::cout << std::endl;
    }

    /*INSERT_ELEMENTS (collection, first, last)
     *-fill values from first to last into the collection
     *-NOTE: NO half-open range
     */
    template <c1ass T>
    inline void INSERT_ELEMENTS (T& coll, int first, int last)
    {
        for (int i=first; i<=last; ++i) {
            coll.insert(coll.end(),i);
        }
    }

    #endif /*ALGOSTUFF_HPP*/

First, algostuff.hpp includes all header files that may be necessary to implement the examples, thus the program doesn't have to do it. Second, it defines two auxiliary functions:

  1. PRINT_ELEMENTS() prints all elements of the container that is passed as the first argument separated by spaces. You can pass a second argument optionally for a string that is used as a prefix in front of the elements (see page 118).

  2. INSERT_ELEMENTS() inserts elements into the container that is passed as the first argument. These elements get the values from the value passed as the second argument up to the value passed as the third argument. Both argument values are included (so this is not a half-open range).

9.4 The for_each() Algorithm

The for_each() algorithm is very flexible because it allows you to access, process, and modify each element in many different ways.

UnaryProc

for_each (InputIterator beg, InputIterator end, UnaryProc op)

The following example of for_each() calls the print() function, which is passed as the operation for each element. Thus, the call prints each element:

   // algo/foreach1.cpp

    #include "algostuff.hpp"
    using namespace std;


    // function called for each element
    void print (int elem)
    {
        cout << elem << ' ';
    }


    int main()
    {

        vector<int> coll;


        INSERT_ELEMENTS(coll,1,9);


        // call print() for each element
        for_each (coll.begin(), coll.end(),  // range
                  print);                    // operation
        cout << endl;
    }

The program has the following output:

   1 2 3 4 5 6 7 8 9

To call a member function of the elements you can use the mem_fun adapters. See Section 8.2.2, for details and an example.

The following example demonstrates how to modify each element using a function object:

   // algo/foreach2.cpp

    #include "algostuff.hpp"
    using namespace std;


    // function object that adds the value with which it is initialized
    template <c1ass T>
    c1ass AddValue {
      private:
        T theValue;    // value to add
      public:
        // constructor initializes the value to add
        AddValue (const T& v) : theValue(v) {
        }

        // the function call for the element adds the value
        void operator() (T& elem) const {
            elem += theValue;
        }
    };

    int main()
    {

        vector<int> coll;

        INSERT_ELEMENTS(coll,1,9);

        // add ten to each element
        for_each (coll.begin(), coll.end(),         // range
                  AddValue<int>(10));               // operation
        PRINT_ELEMENTS(coll);

        // add value of first element to each element
        for_each (coll.begin(), coll.end(),         // range
                  AddValue<int>(*coll.begin()));    // operation
        PRINT_ELEMENTS(coll);
    }

The AddValue<> c1ass defines function objects that add a value to each element that is passed to the constructor. Using the function object has the advantage that you can process the added value at runtime. The program has the following output:

   11 12 13 14 15 16 17 18 19
   22 23 24 25 26 27 28 29 30

See page 128 for more details regarding this example. Note also that you can do the same by using the transform() algorithm (see page 367) in the following way:

   transform (coll.begin(), coll.end(),               // source range
               coll.begin(),                           // destination range
               bind2nd(plus<int>(), 10));              // operation

    ...
    transform (coll.begin(), coll.end(),               // source range
               coll.begin(),                           // destination range
               bind2nd(plus<int>(),*coll.begin()));    // operation

See page 325 for a general comparison between for_each() and transform().

A third example demonstrates how to use the return value of the for_each() algorithm. Because for_each() has the special property that it returns its operation, you can process and return a result inside the operation:

   // algo/foreach3.cpp

    #include "algostuff.hpp"
    using namespace std;

    // function object to process the mean value
    c1ass MeanValue {
      private:
        long num;     // number of elements
        long sum;     // sum of all element values
      public:
        // constructor
        MeanValue () : num(0), sum(0) {
        }

        // function call
        // - process one more element of the sequence
        void operator() (int elem) {
            num++;         // increment count
            sum += elem;   // add value
        }

        // return mean value (implicit type conversion)
        operator double() {
            return static_cast<double>(sum) / static_cast<double>(num);
        }

    };

    int main()
    {

        vector<int> coll;

        INSERT_ELEMENTS(coll,1,8);

        // process and print mean value
        double mv = for_each (coll.begin(), coll.end(),  // range
                              MeanValue());              // operation
        cout << "mean value: " << mv << endl;
    }

The program has the following output:

   mean value: 4.5

This example, in a slightly different form, is discussed in detail on page 300.

9.5 Nonmodifying Algorithms

The algorithms presented in this section enable you to access elements without modifying their values or changing their order.

9.5.1 Counting Elements

difference _type

count (InputIterator beg, InputIterator end, const T& value)

difference _type

count_if (InputIterator beg, InputIterator end, UnaryPredicate op)

The following example counts elements according to different criteria:

   // algo/count1.cpp

    #include "algostuff.hpp"
    using namespace std;

    bool isEven (int elem)
    {

        return elem % 2 == 0;
    }

    int main()
    {

        vector<int> coll;
        int num;

        INSERT_ELEMENTS(coll,1,9);
        PRINT_ELEMENTS(coll,"coll: ");

        // count and print elements with value 4
        num = count (coll.begin(), coll.end(),           // range
                     4);                                 // value
        cout << "number of elements equal to 4:          " << num << endl;

        // count elements with even value
        num = count_if (coll.begin(), coll.end(),        // range
                        isEven);                         // criterion
        cout << "number of elements with even value:     " num << endl;

        // count elements that are greater than value 4
        num = count_if (coll.begin(), coll.end(),        // range
                        bind2nd(greater<int>(),4));      // criterion
        cout << "number of elements greater than 4:      " << num << endl;
    }

The program has the following output:

   coll: 1 2 3 4 5 6 7 8 9
   number of elements equal to 4:      1
   number of elements with even value: 4
   number of elements greater than 4:  5

Instead of using the self-written isEven() function, you could use the following expression:

   not1(bind2nd(modulus<int>(),2))

See page 306 for more details regarding this expression.

9.5.2 Minimum and Maximum

InputIterator

min_element (InputIterator beg, InputIterator end)

InputIterator

min_element (InputIterator beg, InputIterator end, CompFunc op)

InputIterator

max_element (InputIterator beg, InputIterator end)

InputIterator

max_element (InputIterator beg, InputIterator end, CompFunc op)

The following program prints the minimum and the maximum of the elements in coll and, by using absLess(), prints the minimum and the maximum of the absolute values:

   // algo/minmax1.cpp

    #include <cstdlib>
    #include "algostuff.hpp"
    using namespace std;

    bool absLess (int elem1, int elem2)
    {

        return abs(elem1) < abs (elem2);
    }

    int main()
    {

        deque<int> coll;

        INSERT_ELEMENTS(coll,2,8);
        INSERT_ELEMENTS(coll,-3,5);

        PRINT_ELEMENTS(coll);

        // process and print minimum and maximum
        cout << "minimum: "
             << *min_element(coll.begin(),coll.end())
             << endl;
        cout << "maximum: "
             << *max_element(coll.begin(),coll.end())
             << endl;

        // process and print minimum and maximum of absolute values
        cout << "minimum of absolute values: "
             << *min_element(coll.begin(),coll.end(),
                             absLess)
             << endl;
        cout << "maximum of absolute values: "
             << *max_element(coll.begin(),coll.end(),
                             absLess)
             << endl;
    }

The program has the following output:

   2 3 4 5 6 7 8 -3 -2 -1 0 1 2 3 4 5
    minimum: -3
    maximum: 8
    minimum of absolute values: 0
    maximum of absolute values: 8

Note that the algorithms return the, position of the maximum or minimum element respectively. Thus, you must use the unary operator * to print their values.

9.5.3 Searching Elements

Search First Matching Element

InputIterator

find (InputIterator beg, InputIterator end, const T& value)

InputIterator

find_if (InputIterator beg, InputIterator end, UnaryPredicate op)

The following example demonstrates how to use find() to find a subrange starting with the first element with value 4 and ending after the second 4, if any:

   // algo/find1.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {

        list<int> coll;

        INSERT_ELEMENTS(coll,1,9);
        INSERT_ELEMENTS(coll,1,9);

        PRINT_ELEMENTS(coll,"coll: ");

        // find first element with value 4
        list<int>::iterator pos1;
        pos1 = find (coll.begin(), coll.end(),    // range
                     4);                          // value

        /*find second element with value 4
         *- note: continue the search behind the first 4 (if any)
         */
        list<int>::iterator pos2;
        if (pos1 != coll.end()) {
            pos2 = find (++pos1, coll.end(),      // range
                         4);                      // value
        }

        /*print all elements from first to second 4 (both included)
         *- note: now we need the position of the first 4 again (if any)
         *- note: we have to pass the position behind the second 4 (if any)
         */
        if (pos1!=coll.end() && pos2!=coll.end()) {
            copy (--pos1, ++pos2,
                  ostream_iterator<int>(cout," "));
            cout << endl;
        }
    }

To find the second 4 you must increment the position of the first 4. However, incrementing the end() of a collection results in undefined behavior. Thus, if you are not sure, you should check the return value of find() before you increment it. The program has the following output:

   coll: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
    4 5 6 7 8 9 1 2 3 4

You can call find() twice for the same range but with two different values. However, you have to be careful to use the results as the beginning and the end of a subrange of elements; otherwise, the subrange might not be valid. See page 97 for a discussion of possible problems and for an example.

The following example demonstrates how to use find_if() to find elements according to very different search criteria:

   // algo/find2.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {

        vector<int> coll;
        vector<int>::iterator pos;

        INSERT_ELEMENTS(coll,1,9);

        PRINT_ELEMENTS(coll,"coll: ");

        // find first element greater than 3
        pos = find_if (coll.begin(), coll.end(),        // range
                       bind2nd(greater<int>(),3));      // criterion

        // print its position

        cout << "the "
             << distance(coll.begin(),pos) + 1
             << ". element is the first greater than 3" << endl;

        // find first element divisible by 3
        pos = find_if (coll.begin(), coll.end(),
                       not1(bind2nd(modulus<int>(),3)));

        // print its position
        cout << "the "
             << distance(coll.begin(),pos) + 1
             << ". element is the first divisible by 3" << endl;
    }

The first call of find() uses a simple function object combined with the bind2nd adapter to search for the first element that is greater than 3. The second call uses a more complicated combination to find the first element that is divisible by 3 without rest.

The program has the following output:

   coll: 1 2 3 4 5 6 7 8 9
    the 4. element is the first greater than 3
    the 3. element is the first divisible by 3

See page 121 for an example that lets find() find the first prime number.

Search First n Matching Consecutive Elements

InputIterator

search_n (InputIterator beg, InputIterator end, Size count, const T& value)

InputIterator

search_n (InputIterator beg, InputIterator end, Size count, const T& value, BinaryPredicate op)

The following example searches for three consecutive elements that have a value equal to or greater than 3:

   // algo/searchn1.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {

        deque<int> coll;

        INSERT_ELEMENTS(coll,1,9);
        PRINT_ELEMENTS(coll);

        // find three consecutive elements with value 4
        deque<int>::iterator pos;
        pos = search_n (coll.begin(), coll.end(),   // range
                        4,                          // count
                        3);                         // value

        // print result
        if (pos != coll.end()) {
            cout << "four consecutive elements with value 3 "
                 << "start with " << distance(coll.begin(),pos) +1
                 << ". element" << endl;
        }
        else {
            cout << "no four consecutive elements with value 3 found"
                 << endl;
        }

        // find three consecutive elements with value greater than 4
        pos = search_n (coll.begin(), coll.end(),                   // range
                        4,                                          // count
                        3,                                          // value
                        greater<int>());                            // criterion

        // print result
        if (pos != coll.end()) {
            cout << "four consecutive elements with value > 3 "
                 << "start with " << distance(coll.begin(),pos) +1
                 << ". element" << endl;

        }
        else {
            cout << "no four consecutive elements with value > 3 found"
                 << endl;
        }
    }

The program has the following output:

   1 2 3 4 5 6 7 8 9
    no four consecutive elements with value 3 found
    four consecutive elements with value > 3 start with 4. element

There is a nasty problem with the second form of search_n(). Consider the second call of search_n():

   pos = search_n (coll.begin(), coll.end(),   // range
                    4,                          // count
                    3,                          // value
                    greater<int>());            // criterion

This kind of searching for elements that matches a special criterion does not conform with the rest of the STL. Following the usual concepts of the STL, the call should be as follows:

   pos = search_n_if (coll.begin(), coll.end(),       // range
                       4,                              // count
                       bind2nd(greater<int>(),3));     // criterion

Unfortunately, nobody noticed this inconsistency when these new algorithms were introduced to the standard (they were not part of the original STL). You might argue that the version with four arguments is more convenient. However, it requires a binary predicate even if you only need a unary predicate. For example, to use a self-written unary predicate function, normally you would write:

   bool isPrime (int elem);
    ...
    pos = search_n_if (coll.begin(), coll.end(),   // range
                       4,                          // count
                       isPrime);                   //criterion

However, with the actual definition you must use a binary predicate. So, either you change the signature of your function or you write a simple wrapper:

   bool binaryIsPrime (int elem1, int) {
        return isPrime(elem1);
    }
    ...
    pos = search_n (coll.begin(), coll.end(),     // range
                    4,                            // count
                    0,                            // required dummy value
                    binaryIsPrime);               // binary criterion
Search First Subrange

ForwardIterator1

search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)

ForwardIterator1

search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)

The following example demonstrates how to find a sequence as the first subrange of another sequence (compare with the example of find_end() on page 351):

   // algo/search1.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {

        deque<int> coll;
        list<int> subcoll;

        INSERT_ELEMENTS(coll,1,7);
        INSERT.ELEMENTS(coll,1,7);

        INSERT_ELEMENTS(subcoll,3,6);

        PRINT_ELEMENTS(coll, "coll: ");
        PRINT_ELEMENTS(subcoll,"subcoll: ");

        // search first occurrence of subcoll in coll
        deque<int>::iterator pos;
        pos = search (coll.begin(), coll.end(),            // range
                      subcoll.begin(), subcoll.end());     //subrange

        // loop while subcoll found as subrange of coll
        while (pos != coll.end()) {
            // print position of first element
            cout << "subcoll found starting with element "
                 << distance (coll.begin(),pos) + 1
                 << endl;

            // search next occurrence of subcoll
            ++pos;
            pos = search (pos, coll.end(),                  // range
                          subcoll.begin(), subcoll.end());  // subrange
        }
    }

The program has the following output:

   coll: 1 2 3 4 5 6 7 1 2 3 4 5 6 7
    subcoll: 3 4 5 6
    subcoll found starting with element 3
    subcoll found starting with element 10

The next example demonstrates how to use the second form of the search() algorithm to find a subsequence that matches a more complicated criterion. Here, the subsequence even, odd, and even value is searched:

   // algo/search2.cpp

    #include "algostuff.hpp"
    using namespace std;

    // checks whether an element is even or odd
    bool checkEven (int elem, bool even)
    {

        if (even) {
            return elem % 2 == 0;
        }
        else {
            return elem % 2 == 1;
        }
    }

    int main()
    {

        vector<int> coll;

        INSERT_ELEMENTS(coll,1,9);
        PRINT_ELEMENTS(coll,"coll: ");

        /* arguments for checkEven()
         * - check for: "even odd even"
         */
        bool checkEvenArgs[3] = { true, false, true };

        // search first subrange in coll
        vector<int>::iterator pos;
        pos = search (coll.begin(), coll.end(),       // range
                      checkEvenArgs, checkEvenArgs+3, // subrange values
                      checkEven);                     // subrange criterion

        // loop while subrange found
        while (pos != coll.end()) {
            // print position of first element
            cout << "subrange found starting with element "
                 << distance(coll.begin(),pos) + 1
                 << endl;

            // search next subrange in coll
            pos = search (++pos, coll.end(),               // range
                          checkEvenArgs, checkEvenArgs+3,  // subr. values
                          checkEven);                      // subr. criterion
        }
    }

The program has the following output:

   coll: 1 2 3 4 5 6 7 8 9
    subrange found starting with element 2
    subrange found starting with element 4
    subrange found starting with element 6
Search Last Subrange

ForwardIterator

find_end (ForwardIterator beg, ForwardIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd)

ForwardIterator

find_end (ForwardIterator beg, ForwardIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd, BinaryPredicate op)

The following example demonstrates how to find a sequence as the last subrange of another sequence (compare with the example of search() on page 348):

   // algo/findend1.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {

        deque<int> coll;
        list<int> subcoll;

        INSERT_ELEMENTS(coll,1,7);
        INSERT_ELEMENTS(coll,1,7);

        INSERT_ELEMENTS(subcoll,3,6);

        PRINT_ELEMENTS(coll,   "coll:    ");
        PRINT_ELEMENTS(subcoll,"subcoll: ");

        // search last occurrence of subcoll in coll
        deque<int>::iterator pos;
        pos = find_end (coll.begin(), coll.end(),         // range
                        subcoll.begin(), subcoll.end());  // subrange

        // loop while subcoll found as subrange of coll
        deque<int>::iterator end(coll.end());
        while (pos != end) {
            // print position of first element
            cout << "subcoll found starting with element "
                 << distance(coll.begin(),pos) + 1
                 << endl;

            // search next occurrence of subcoll
            end = pos;
            pos = find_end (coll.begin(), end,                // range
                            subcoll.begin(), subcoll.end());  // subrange
        }
    }

The program has the following output:

   coll:    1 2 3 4 5 6 7 1 2 3 4 5 6 7
    subcoll: 3 4 5 6
    subcoll found starting with element 10
    subcoll found starting with element 3

For the second form of this algorithm, see the second example of search() on page 349. You can use find_end() in a similar manner.

Search First of Several Possible Elements

ForwardIterator

find_first_of (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)

ForwardIterator

find_first_of (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)

The following example demonstrates the use of find_first_of():

   // algo/findof1.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {

        vector<int> coll;
        list<int> searchcoll;

        INSERT_ELEMENTS(coll,1,11);
        INSERT_ELEMENTS(searchcoll,3,5);

        PRINT_ELEMENTS(coll,      "coll:       ");
        PRINT_ELEMENTS(searchcoll,"searchcoll: ");

        // search first occurrence of an element of searchcoll in coll
        vector<int>::iterator pos;
        pos = find_first_of (coll.begin(), coll.end(),     // range
                             searchcoll.begin(),  // beginning of search set
                             searchcoll.end());   // end of search set
        cout << "first element of searchcoll in coll is element "
             << distance(coll.begin(),pos) + 1
             << endl;

        // search last occurrence of an element of searchcoll in coll
        vector<int>::reverse_iterator rpos;
        rpos = find_first_of (coll.rbegin(), coll.rend(),   // range
                              searchcoll.begin(),  // beginning of search set
                              searchcoll.end());   // end of search set
        cout << "last element of searchcoll in coll is element "
             << distance (coll.begin(),rpos.base())
             << endl;
    }

The second call uses reverse iterators to find the last element that has a value equal to one element in searchcoll. To print the position of the element, base() is called to transform the reverse iterator into an iterator. Thus, you can process the distance from the beginning. Normally you would have to add 1 to the result of distance() because the first element has distance 0 but actually is element 1. However, because base() moves the position of the value to which it refers, you have the same effect (see Section 7.4.1, for the description of base()).

The program has the following output:

   coll:       1 2 3 4 5 6 7 8 9 10 11
    searchcoll: 3 4 5
    first element of searchcoll in coll is element 3
    last element of searchcoll in coll is element 5
Search Two Adjacent, Equal Elements

InputIterator

adjacent_find (InputIterator beg, InputIterator end)

InputIterator

adjacent_find_if (InputIterator beg, InputIterator end, BinaryPredicate op)

The following program demonstrates both forms of adjacent_find():

   // algo/adjfindl.cpp

    #include "algostuff.hpp"
    using namespace std;

    // return whether the second object has double the value of the first
    bool doubled (int elem1, int elem2)
    {
        return elem1 * 2 == elem2;
    }

    int main()
    {

        vector<int> coll;

        coll.push_back(l);
        coll.push_back(3);
        coll.push_back(2);
        coll.push_back(4);
        coll.push_back(5);
        coll.push_back(5);
        coll.push_back(0);

        PRINT_ELEMENTS(coll,"coll: ");

        // search first two elements with equal value
        vector<int>::iterator pos;
        pos = adjacent_find (coll.begin(), coll.end());

        if (pos != coll.end()) {
            cout << "first two elements with equal value have position "
                 << distance(coll.begin(),pos) + 1
                 << endl;
        }

        //search first two elements for which the second has double the value of the first
        pos = adjacent_find (coll.begin(), coll.end(),   // range
                             doubled);                   // criterion

        if (pos != coll.end()) {
            cout << "first two elements with second value twice the "
                 << "first have pos. "
                 << distance (coll.begin(),pos) + 1
                 << endl;
        }
    }

The first call of adjacent_find() searches for equal values. The second form uses doubled() to find the first element for which the successor has the double value. The program has the following output:

   coll: 1 3 2 4 5 5 0
    first two elements with equal value have position 5
    first two elements with second value twice the first have pos. 3

9.5.4 Comparing Ranges

Testing Equality

bool

equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)

bool

equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg, BinaryPredicate op)

The following example demonstrates both forms of equal(). The first call checks whether the elements have values with equal elements. The second call uses an auxiliary predicate function to check whether the elements of both collections have corresponding even and odd elements:

   // algo/equal1.cpp

    #include "algostuff.hpp"
    using namespace std;
    bool bothEvenOrOdd (int elem1, int elem2)
    {
        return elem1 % 2 == elem2 % 2;
    }


    int main()
    {

        vector<int> coll1;
        list<int> coll2;


        INSERT_ELEMENTS(coll1,1,7);
        INSERT_ELEMENTS(coll2,3,9);


        PRINT_ELEMENTS(coll1,"coll1: ");
        PRINT_ELEMENTS(col12,"col12: ");


        //check whether both collections are equal
        if (equal (coll1. begin(), coll1. end(),  //first range
                   coll2.begin())) {              //second range
            cout << "coll1 == col12" << endl;
        }
        else {
            cout << "coll1 != coll2" << endl;
        }


        //check for corresponding even and odd elements
        if (equal (coll1.begin(), coll1.end(),   //first range
                   coll2. begin(),               //second range
                   bothEvenOrOdd)) {             //comparison criterion
            cout << "even and odd elements correspond" << endl;
        }
        else {
            cout << "even and odd elements do not correspond" << endl;
        }
    }

The program has the following output:

   coll1: 1 2 3 4 5 6 7
    coll2: 3 4 5 6 7 8 9
    coll1 != coll2
    even and odd elements correspond
Search the First Difference

pair<InputIterator1,InputIterator2>

mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)

pair<InputIterator1,InputIterator2>

mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg, BinaryPredicate op)

The following example demonstrates both forms of mismatch():

   // algo/misma1.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {

        vector<int> coll1;
        list<int> coll2;

        INSERT_ELEMENTS(coll1,1,6);

        for (int i=1; i<=16; i*=2) {
            col12.push_back(i);
        }
        coll2.push_back(3);

        PRINT_ELEMENTS(coll1,"coll1: ");
        PRINT_ELEMENTS(coll2,"coll2: ");

        //find first mismatch
        pair<vector<int>::iterator,list<int>::iterator> values;
        values = mismatch (coll1.begin(), coll1.end(),  //first range
                           coll2.begin());              //second range
        if (values.first == coll1.end()) {
            cout << "no mismatch" << endl;
        }
        else {
            cout << "first mismatch: "
                 << *values.first << " and "
                 << *values.second << endl;
        }

        /*find first position where the element of coll1 is not
         *less than the corresponding element of coll2
         */
        values = mismatch (coll1.begin(), coll1.end(),   //first range
                           col12. begin(),               //second range
                           less_equal<int>() )           //criterion
        if (values.first == coll1.end()) {
            cout << "always less-or-equal" << endl;
        }
        else {
            cout << "not less-or-equal: "
                 << *values.first << " and "
                 << *values.second << endl;
        }
    }

The first call of mismatch() searches for the first corresponding elements that are not equal. If such elements exist, their values are written to standard output. The second call searches for the first pair of elements in which the element of the first collection is greater than the corresponding element of the second collection, and returns these elements. The program has the following output:

   coll1: 1 2 3 4 5 6
    coll2: 1 2 4 8 16 3
    first mismatch: 3 and 4
    not less-or-equal: 6 and 3
Testing for "Less Than"

bool

lexicographical_compare (InputIterator1 beg1, Input Iterator1 end1, InputIterator2 beg2, InputIterator2 end2)

bool

lexicographical_compare (InputIterator1 begl, InputIterator1 end1, InputIterator2 beg2, InputIterator2 end2, CompFunc op)

The following example demonstrates the use of a lexicographical sorting of collections:

   // algo/lexico1.cpp

   #include "algostuff.hpp"
   using namespace std;
   void printCollection (const list<int>& l)
   {
       PRINT_ELEMENTS(l);
   }

   bool lessForCollection (const list<int>& l1, const list<int>& 12)
   {
      return lexicographical_compare
                  (l1.begin(), l1.end(),    // first range
                   12.begin(), 12.end());   // second range
   }

   int main()
   {
       list<int> c1, c2, c3, c4;

       //fill all collections with the same starting values
       INSERT_ELEMENTS(c1,1,5);
       c4 = c3 = c2 = c1;

       //and now some differences
       c1.push_back(7);
       c3.push_back(2);
       c3.push_back(0);
       c4.push_back(2);

       //create collection of collections
       vector<list<int> > cc;

       cc.push_back(c1);
       cc.push_back(c2);
       cc.push_back(c3);
       cc.push_back(c4);
       cc.push_back(c3);
       cc.push_back(c1);
       cc.push_back(c4);
       cc.push_back(c2);

       //print all collections
       for_each (cc.begin(), cc.end(),
                 printCollection);
       cout << endl;

       //sort collection lexicographically
       sort (cc.begin(), cc.end(),       //range
             lessForCollection) ;        //sorting criterion

       //print all collections again
       for_each (cc.begin(), cc.end(),
                 printCollection);
   }

The vector cc is initialized with several collections (all lists). The call of sort() uses the binary predicate lessForCollection() to compare two collections (see page 397 for a description of sort()). In lessForCollection(), the lexicographical_compare() algorithm is used to compare the collections lexicographically. The program has the following output:

   1 2 3 4 5 7
   1 2 3 4 5
   1 2 3 4 5 2 0
   1 2 3 4 5 2
   1 2 3 4 5 2 0
   1 2 3 4 5 7
   1 2 3 4 5 2
   1 2 3 4 5

   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5 2
   1 2 3 4 5 2
   1 2 3 4 5 2 0
   1 2 3 4 5 2 0
   1 2 3 4 5 7
   1 2 3 4 5 7

9.6 Modifying Algorithms

This section describes algorithms that modify the elements of a range. There are two ways to modify elements:

  1. Modify them directly while iterating through a sequence.

  2. Modify them while copying them from a source range to a destination range.

Several modifying algorithms provide both ways of modifying the elements of a range. In this case, the name of the latter uses the _copy suffix.

You can't use an associative container as a destination range because the elements in an associative container are constant. If you could, it would be possible to compromise the automatic sorting.

All algorithms that have a separate destination range return the position after the last copied element of that range.

9.6.1 Copying Elements

OutputIterator

copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)

BidirectionalIteratorl

copy_backward (BidirectionalIterator1 sourceBeg, BidirectionalIterator1 source End, BidirectionalIterator2 destEnd)

The following example shows some simple calls of copy():

   // algo/copy1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       vector<int> coll1;
       list<int> coll2;

       INSERT_ELEMENTS(coll1,1,9);

       /*copy elements of coll1 into coll2
        *-use back inserter to insert instead of overwrite
        */
       copy (coll1.begin(), coll1.end(),              //source range
             back_inserter(coll2)) ;                  //destination range


       /*print elements of coll2
        *-copy elements to cout using an ostream iterator
        */
       copy (coll2.begin(), coll2.end(),              //source range
             ostream_iterator<int>(cout," "));        //destination range
       cout << endl;

       /*copy elements of coll1 into coll2 in reverse order
        *-now overwriting
        */
       copy (coll1.rbegin(), coll1.rend(),            //source range
             coll2.begin());                          //destination range

       //print elements of coll2 again
       copy (coll2.begin(), coll2.end(),              //source range
             ostream_iterator<int>(cout, " "));       //destination range
       cout << endl;
   }

In this example, back inserters (see Section 7.4.2,) are used to insert the elements in the destination range. Without using inserters, copy() would overwrite the empty collection coll2, which results in undefined behavior. Similarly, the example uses ostream iterators (see Section 7.4.3,) to use standard output as the destination.

The program has the following output:

   1 2 3 4 5 6 7 8 9
   9 8 7 6 5 4 3 2 1

The following example demonstrates the difference between copy() and copy_backward():

   // algo/copy2.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       /*initialize source collection with ".......... abcdef.........."
        */
       vector<char> source(10,'.');
       for (int c='a'; c<='f'; C++) {
           source.push_back(c);
       }
       source.insert(source.end(),10,'.');
       PRINT_ELEMENTS(source,"source: ");

       //copy all letters three elements in front of the 'a'
       vector<char> c1(source.begin(),source.end());
       copy (c1.begin()+10, c1.begin()+16,   //source range
             c1.begin()+7);                  //destination range
       PRINT_ELEMENTS(c1,"c1: ");

       //copy all letters three elements behind the 'f'
       vector<char> c2(source.begin(),source.end());
       copy_backward (c2.begin()+10, c2.begin()+16,   //source range
                      c2.begin()+19);                 //destination range
       PRINT_ELEMENTS(c2,"c2: ");
   }

Note that in both calls of copy() and copy_backward(), the third argument is not part of the source range. The program has the following output:

   source: . . . . . . . . . . a b c d e f . . . . . . . . . .
   c1:     . . . . . . . a b c d e f d e f . . . . . . . . . .
   c2:     . . . . . . . . . . a b c a b c d e f . . . . . . .

A third example demonstrates how to use copy() as a data filter between standard input and standard output. he program reads strings and prints them, each on one line:

   // algo/copy3.cpp

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

   int main()
   {

       copy (istream_iterator<string>(cin),             //beginning of source 
             istream_iterator<string>(),                //end of source
             ostream_iterator<string>(cout, "\n"));     //destination
   }

9.6.2 Transforming and Combining Elements

The transform() algorithms provide two abilities:

  1. The first form has four arguments. It transforms elements from a source to a destination range. Thus, it copies and modifies elements in one step.

  2. The second form has five arguments. It combines elements from two source sequences and writes the result to a destination range.

Transforming Elements

OutputIterator

transform (InputIterator sourceBeg, InputIterator sourceEnd, Output Iterator destEeg, UnaryFunc op)

The following program demonstrates how to use this kind of transform():

   // algo/transf1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       vector<int> coll1;
       list<int> coll2;

       INSERT_ELEMENTS(coll1,1,9);
       PRINT_ELEMENTS(coll1,"coll1: ");

       //negate all elements in coll1
       transform (coll1.begin(), coll1.end(),           //source range
                  coll1.begin(),                        //destination range
                  negate<int>());                       //operation


       PRINT_ELEMENTS(coll1,"negated: ");


       //transform elements of coll1 into coll2 with ten times their value
       transform (coll1.begin(), coll1.end(),            //source range
                  back_inserter(coll2),                  //destination range
                  bind2nd(multiplies<int>(),10));        //operation
       PRINT_ELEMENTS(coll2,"coll2: ");


       //print coll2 negatively and in reverse order
       transform (coll2.rbegin(), coll2.rend(),          //source range
                  ostream_iterator<int>(cout," "),       //destination range
                  negate<int>());                        //operation
       cout << endl;
   }

The program has the following output:

   coll1:    1  2 3 4 5 6 7 8 9
   negated: -1 -2 -3 -4 -5 -6 -7 -8 -9
   coll2:   -10 -20 -30 -40 -50 -60 -70 -80 -90
   90 80 70 60 50 40 30 20 10

See the example on page 315 of how to combine two different operations while processing the elements.

Combining Elements of Two Sequences

OutputIterator

transform (InputIterator1 source1Beg, InputIterator1 source1End, InputIterator2 source2Beg, OutputIterator destBeg, BinaryFunc op)

The following program demonstrates how to use this form of transform():

   // algo/transf2.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       vector<int> coll1;
       list<int> coll2;

       INSERT_ELEMENTS(coll1,1,9);
       PRINT_ELEMENTS(coll1,"coll1:    ");

       //square each element
       transform (coll1.begin(), coll1.end(),           //first source range
                  coll1.begin(),                        //second source range
                  coll1.begin(),                        //destination range
                  multiplies<int>() );                  //operation
       PRINT_ELEMENTS(coll1,"squared: ");

       /*add each element traversed forward with each element traversed backward
        *and insert result into coll2
        */
       transform (coll1. begin(), coll1. end(),         //first source range
                  coll1.rbegin(),                       //second source range
                  back_inserter(coll2),                 //destination range
                  plus<int>());                         //operation
       PRINT_ELEMENTS(coll2,"coll2: ");

       // print differences of two corresponding elements
       cout << "diff: ";
       transform (coll1.begin(), coll1.end(),           //first source range
                  coll2.begin(),                        //second source range
                  ostream_iterator<int>(cout, " "),     //destination range
                  minus<int>());                        //operation
       cout << endl;
   }

The program has the following output:

   coll1:    1 2 3 4 5 6 7 8 9
   squared:  1 4 9 16 25 36 49 64 81
   coll2:    82 68 58 52 50 52 58 68 82
   diff:     -81 -64 -49 -36 -25 -16 -9 -4 -1

9.6.3 Swapping Elements

ForwardIterator2

swap_ranges (ForwardIterator1 beg1, ForwardIterator1 end1, ForwardIterator2 beg2)

The following example demonstrates how to use swap_ranges():

   // algo/swap1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       vector<int> coll1;
       deque<int> coll2;

       INSERT_ELEMENTS(coll1,1,9) ;
       INSERT_ELEMENTS(col12,11,23);

       PRINT_ELEMENTS(coll1,"coll1: ");
       PRINT_ELEMENTS(coll2,"coll2: ");

       //swap first four elements
       deque<int>::iterator pos;
       pos = swap_ranges (coll1.begin(), coll1.end(),   //first range
                          coll2.begin());               //second range

       PRINT_ELEMENTS(coll1,"\ncoll1: ");
       PRINT_ELEMENTS(coll2,"col12: ");
       if (pos != coll2.end()) {
           cout << "first element not modified: "
                << *pos << endl;
       }


       //mirror first three with last three elements in coll2
       swap_ranges (coll2.begin(), coll2.begin()+3,     //first range
                    coll2.rbegin());                    //second range
       PRINT_ELEMENTS(coll2,"\ncoll2: ") ;
   }

The first call of swap_ranges() swaps the elements of coll1 with the corresponding elements of coll2. The remaining elements of coll2 are not modified. The swap_ranges() algorithm returns the position of the first element not modified. The second call swaps the first and the last three elements of coll2. One of the iterators is a reverse iterator, so the elements are mirrored (swapped from outside to inside). The program has the following output:

   coll1: 1 2 3 4 5 6 7 8 9
   coll2: 11 12 13 14 15 16 17 18 19 20 21 22 23

   coll1: 11 12 13 14 15 16 17 18 19
   coll2: 1 2 3 4 5 6 7 8 9 20 21 22 23
   first element not modified: 20

   coll2: 23 22 21 4 5 6 7 8 9 20 3 2 1

9.6.4 Assigning New Values

Assigning the Same Value

void

fill (ForwardIterator beg, ForwardIterator end, const T& newValue)

void

fill_n (OutputIterator beg, Size num, const T& newValue)

The following program demonstrates the use of fill() and fill_n():

   // algo/fill1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       //print ten times 7.7
       fill_n(ostream_iterator<float>(cout, " "), //beginning of destination
              10,                                 //count
              7.7);                               //new value
       cout << endl;

       list<string> coll;

       //insert "hello" nine times
       fill_n(back_inserter(coll),         //beginning of destination
              9,                           //count
              "hello");                    //new value 
       PRINT_ELEMENTS(coll,"coll: ");


       //overwrite all elements with "again"
       fill(coll.begin(), coll.end(),      //destination
            "again");                      //new value
       PRINT_ELEMENTS(coll,"coll: ");


       //replace all but two elements with "hi"
       fill_n(coll.begin(),                //beginning of destination
              coll.size()-2,            //count
              "hi");                       //new value
       PRINT_ELEMENTS(coll,"coll: ");


       //replace the second and up to the last element but one with "hmmm"
       list<string>:: iterator posl, pos2;
       posl = coll.begin();
       pos2 = coll.end();
       fill (++pos1, --pos2,               //destination
             "hmmm");                      //new value
       PRINT_ELEMENTS(coll,"coll: ");
   }

The first call shows how to use fill_n() to print a certain number of values. The other calls of fill() and fill_n() insert and replace values in a list of strings. The program has the following output:

   7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7
   coll: hello hello hello hello hello hello hello hello hello
   coll: again again again again again again again again again
   coll: hi hi hi hi hi hi hi again again
   coll: hi hmmm hmmm hmmm hmmm hmmm hmmm hmmm again
Assigning Generated Values

void

generate (ForwardIterator beg, ForwardIterator end, Func op)

void

generate_n (OutputIterator beg, Size num, Func op)

The following program demonstrates how to use generate() and generate_n() to insert or assign some random numbers:

   // algo/generate.cpp

   #include <cstdlib>
   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       list<int> coll;

       //insert five random numbers
       generate_n (back_inserter(coll),       //beginning of destination range
                   5,                         //count
                   rand);                     //new value generator
       PRINT_ELEMENTS(coll);

       //overwrite with five new random numbers
       generate (coll.begin(), coll.end(),    //destination range
                 rand);                       //new value generator
       PRINT_ELEMENTS(coll);
   }

The rand() function is described in Section 12.3. The program might have the following output:

   41 18467 6334 26500 19169
   15724 11478 29358 26962 24464

The output is platform dependent because the random number sequence that rand() generates is not standardized.

See Section 8.1.2, for an example that demonstrates how to use generate() with function objects so that it generates a sequence of numbers.

9.6.5 Replacing Elements

Replacing Values Inside a Sequence

void

replace (Forwardlterator beg, ForwardIterator end, const T& oldValue, const T& newValue)

void

replace_if (ForwardIterator beg, ForwardIterator end, UnaryPredicate op, const T& newValue)

The following program demonstrates some examples of the use of replace() and replace_if():

   // algo/replace1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       list<int> coll;

       INSERT_ELEMENTS(coll,2,7);
       INSERT_ELEMENTS(coll,4,9);
       PRINT_ELEMENTS(coll,"coll: ");

       //replace all elements with value 6 with 42
       replace (coll.begin(), coll.end(),      //range
                6,                             //old value
                42);                           //new value
       PRINT_ELEMENTS(coll,"coll: ");

       //replace all elements with value less than 5 with 0
       replace_if (coll.begin(), coll.end(),   //range
                   bind2nd(less<int>(),5),     //criterion for replacement
                   0);                         //new value
       PRINT_ELEMENTS(coll,"coll: ");
   }

The program has the following output:

   coll: 2 3 4 5 6 7 4 5 6 7 8 9
   coll: 2 3 4 5 42 7 4 5 42 7 8 9
   coll: 0 0 0 5 42 7 0 5 42 7 8 9
Copying and Replacing Elements

OutputIterator

replace_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, const T& oldValue, const T& newValue)

OutputIterator

replace_copy_if (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryPredicate op, const T& newValue)

The following program demonstrates how to use replace_copy() and replace_copy_if():

   // algo/replace2.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       list<int> coll;

       INSERT_ELEMENTS(coll,2,6);
       INSERT_ELEMENTS(coll,4,9);
       PRINT_ELEMENTS(coll);

       //print all elements with value 5 replaced with 55
       replace_copy(coll.begin(), coll.end(),                //source
                    ostream_iterator<int>(cout," "),         //destination
                    5,                                       //old value
                    55);                                     //new value
       cout << endl;

       //print all elements with a value less than 5 replaced with 42
       replace_copy_if (coll.begin(), coll.end(),           //source
                        ostream_iterator<int>(cout," "),    //destination
                        bind2nd(less<int>(),5),    //replacement criterion
                        42);                       //new value
       cout << endl;

       //print each element while each odd element is replaced with 0
       replace_copy_if (coll.begin(), coll.end(),           //source
                        ostream_iterator<int>(cout," "),    //destination
                        bind2nd (modulus<int>(),2), //replacement criterion
                        0);                         //new value
                        cout << endl; >
   }

The program has the following output:

   2 3 4 5 6 4 5 6 7 8 9
   2 3 4 55 6 4 55 6 7 8 9
   42 42 42 5 6 42 5 6 7 8 9
   2 0 4 0 6 4 0 6 0 8 0

9.7 Removing Algorithms

The following algorithms remove elements from a range according to their value or to a criterion. These algorithms, however, cannot change the number of elements. They only move logically by overwriting "removed" elements with the following elements that were not removed. They return the new logical end of the range (the position after the last element not removed). See Section 5.6.1, for details.

9.7.1 Removing Certain Values

Removing Elements in a Sequence

ForwardIterator

remove (ForwardIterator beg, ForwardIterator end, const T& value)

ForwardIterator

remove_if (ForwardIterator beg, ForwardIterator end, UnaryPredicate op)

The following program demonstrates how to use remove() and remove_if():

   // algo/remove1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       vector<int> coll;

       INSERT_ELEMENTS(coll,2,6);
       INSERT_ELEMENTS(coll,4,9);
       INSERT_ELEMENTS(coll,1,7);
       PRINT_ELEMENTS(coll,"coll:                  ");

       //remove all elements with value 5
       vector<int>::iterator pos;
       pos = remove (coll. begin(), coll.end(),    //range
                     5);                           //value to remove

       PRINT_ELEMENTS(coll,"size not changed:      ");

       //erase the "removed" elements in the container
       coll. erase (pos, coll.end());
       PRINT_ELEMENTS(coll,"size changed:          ");

       //remove all elements less than 4
       coll.erase(remove_if (coll.begin(), coll.end(),       //range
                             bind2nd(less<int>(),4)),        //remove criterion
                  coll.end());
       PRINT_ELEMENTS(coll,"<4 removed: : ");
   }

The program has the following output:

   coll:                  2 3 4 5 6 4 5 6 7 8 9 1 2 3 4 5 6 7
   size not changed:      2 3 4 6 4 6 7 8 9 1 2 3 4 6 7 5 6 7
   size changed:          2 3 4 6 4 6 7 8 9 1 2 3 4 6 7
   <4 removed: :          4 6 4 6 7 8 9 4 6 7
Removing Elements While Copying

OutputIterator

remove_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, const T& value)

OutputIterator

remove_copy_if (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryPredicate op)

The following program demonstrates how to use remove_copy() and remove_copy_if():

   // algo/remove2.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       list<int> coll1;

       INSERT_ELEMENTS(coll1,1,6);
       INSERT_ELEMENTS(coll1,l,9);
       PRINT_ELEMENTS(coll1);

       //print elements without those having the value 3
       remove_copy(coll1.begin(), coll 1.end(),         //source
                   ostream_iterator<int>(cout," "),     //destination
                   3);                                  //removed value
       cout << endl;

       //print elements without those having a value greater than 4
       remove_copy_if (coll1.begin(), coll1.end(),         //source
                       ostream_iterator<int>(cout," "),    //destination
                       bind2nd(greater<int>(),4));         //removed elements
       cout << endl;

       //copy all elements greater than 3 into a multiset
       multiset<int> coll2;
       remove_copy_if (coll1.begin(), coll1.end(),      //source
                       inserter(coll2,coll2.end()),     //destination
                       bind2nd(less<int>(),4));         //elements not copied
       PRINT_ELEMENTS(coll2);
   }

The program has the following output:

   1 2 3 4 5 6 1 2 3 4 5 6 7 8 9
   1 2 4 5 6 1 2 4 5 6 7 8 9
   1 2 3 4 1 2 3 4
   4 4 5 5 6 6 7 8 9

9.7.2 Removing Duplicates

Removing Consecutive Duplicates

void

unique (ForwardIterator beg, ForwardIterator end)

void

unique (Forwardlterator beg, ForwardIterator end, BinaryPredicate op)

The following program demonstrates how to use unique():

   // algo/unique1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       //source data
       int source[] = { 1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7,
                         5, 4, 4 };
       int sourceNum = sizeof(source)/sizeof(source[0]);

       list<int> coll;.

       //initialize coll with elements from source
       copy (source, source+sourceNum,               //source
             back_inserter(coll)) ;                  //destination
       PRINT_ELEMENTS(coll);

       //remove consecutive duplicates
       list<int> :: iterator pos;

       pos = unique (coll.begin(), coll.end());

       /*print elements not removed
        *-use new logical end
        */
       copy (coll.begin(), pos,                      //source
             ostream_iterator<int>(cout," "));       //destination
       cout << "\n\n";

       //reinitialize coll with elements from source
       copy (source, source+sourceNum,               //source
             coll.begin());                          //destination
       PRINT_ELEMENTS(coll);

       //remove elements if there was a previous greater element
       coll.erase (unique (coll.begin(), coll.end(),
                           greater<int>()), 
                   coll.end()); 
       PRINT_ELEMENTS(coll);
   }

The program has the following output:

   1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4
   1 4 6 1 2 3 1 6 5 7 5 4

   1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4
   1 4 4 6 6 6 6 7

The first call of unique() removes consecutive duplicates. The second call shows the behavior of the second form. It removes all the consecutive following elements of an element for which the comparison with greater yields true. For example, the first 6 is greater than the following 1, 2, 2, 3, and 1, so all these elements are removed. In other words, the predicate is not used to compare an element with its predecessor; the element is compared with the previous element that was not removed (see the following description of unique_copy() for another example).

Removing Duplicates While Copying

OutputIterator

unique_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)

OutputIterator

unique_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryPredicate op)

The following program demonstrates how to useunique_copy():

   // algo/unique2.cpp

   #include "algostuff.hpp"
   using namespace std;


   bool differenceOne (int elem1, int elem2)
   {

       return elem1 + 1 == elem2 || elem1 - 1 == elem2;

   }


   int main()
   {

       // source data
       int source[] = { 1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7, 
                         5, 4, 4 };
       int sourceNum = sizeof(source)/sizeof(source[0]);


       // initialize coll with elements from source
       list<int> coll;
       copy(source, source+sourceNum,                  // source
            back_inserter(coll));                      // destination
       PRINT_ELEMENTS(coll);


       // print element with consecutive duplicates removed
       unique_copy(coll.begin(), coll.end(),              // source
                   ostream_iterator<int>(cout," "));      // destination
       cout << endl;


       // print element without consecutive duplicates that differ by one
       unique_copy(coll.begin(), coll.end(),              // source
                   ostream_iterator<int>(cout," "),       // destination
                   differenceOne);                        // duplicate criterion
       cout << endl;
   }

The program has the following output:

   1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4
   1 4 6 1 2 3 1 6 5 7 5 4
   1 4 4 6 1 3 1 6 6 6 4 4

Note that the second call of unique_copy() does not remove the elements that differ from their predecessor by one. Instead it removes all elements that differ from their previous element that is not removed by one. For example, after the three occurrences of 6, the following 5, 7, and 5 differ by one compared with 6, so they are removed. However, the following two occurrences of 4 remain in the sequence because compared with 6 the difference is not one.

Another example compresses sequences of spaces:

   // algo/unique3.cpp

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


    bool bothSpaces (char elem1, char elem2)
    {

        return elem1 == ' ' && elem2 == ' ';

    }


    int main()
    {

        // don't skip leading whitespaces by default
        cin.unsetf(ios :: skipws);
        / * copy standard input to standard output
          *-while compressing spaces
          */
        unique_copy(istream_iterator<char>(cin),      // beginning of source:cin
                    istream_iterator<char>(),         // end of source: end-of-file
                    ostream_iterator<char>(cout),     // destination: cout
                    bothSpaces);                      // duplicate criterion
   }

With the input of

   Hello, here are sometimes more and sometimes fewer spaces.

this example produces the following output:

   Hello, here are sometimes more and sometimes fewer spaces.

9.8 Mutating Algorithms

Mutating algorithms change the order of elements (but not their values). Because elements of associative containers have a fixed order, you can't use them as a destination for mutating algorithms.

9.8.1 Reversing the Order of Elements

void

reverse (BidirectionalIterator beg, BidirectionalIterator end)

OutputIterator

reverse_copy (BidirectionalIterator sourceBeg, BidirectionalIterator sourceEnd, Output Iterator destBeg)

The following program demonstrates how to use reverse() and reverse,copy():

   // algo/reverse1.cpp

   #include "algostuff.hpp"
   using namespace std;


   int main()
   {

       vector<int> coll;


       INSERT_ELEMENTS(coll,1,9);
       PRINT_ELEMENTS(coll,"coll: ");


       // reverse order of elements
       reverse (coll.begin(), coll.end());
       PRINT_ELEMENTS(coll,"coll: ");


       // reverse order from second to last element but one
       reverse (coll.begin()+l,      coll.end()-l);
       PRINT_ELEMENTS(coll,"coll: ");


       //print all of them in reverse order
       reverse_copy (coll.begin(), coll.end(),              // source
                     ostream_iterator<int>(cout," "));      // destination
       cout << endl;
   }

The program has the following output:

   coll: 1 2 3 4 5 6 7 8 9
   coll: 9 8 7 6 5 4 3 2 1
   coll: 9 2 3 4 5 6 7 8 1
   1 8 7 6 5 4 3 2 9

9.8.2 Rotating Elements

Rotating Elements Inside a Sequence

void

rotate (ForwardIterator beg, ForwardIterator newBeg, ForwardIterator end)

The following program demonstrates how to use rotate():

   // algo/rotate1.cpp

   #include "algostuff.hpp"
   using namespace std;


   int main()
   {

       vector<int> coll;


       INSERT_ELEMENTS(coll,1,9);
       PRINT_ELEMENTS(coll,"coll:           ");


       // rotate one element to the left
       rotate (coll.begin(),        // beginning of range
               coll.begin() + 1,    // new first element
               coll.end());         // end of range
       PRINT_ELEMENTS(coll,"one left: ");


       // rotate two elements to the right
       rotate (coll.begin(),        // beginning of range
               coll.end() - 2,   // new first element
               coll.end());         // end of range
       PRINT_ELEMENTS(coll,"two right: ");


       // rotate so that element with value 4 is the beginning
       rotate (coll.begin(),                         // beginning of range
               find (coll.begin(), coll.end(),4),    // new first element
               coll.end());                          // end of range
       PRINT_ELEMENTS(coll,"4 first: ");
   }

As the example shows, you can rotate to the left with a positive offset for the beginning and rotate to the right with a negative offset to the end. However, adding the offset to the iterator is possible only when you have random access iterators, as you have for vectors. Without such iterators, you must use advance() (see the example of rotate_copy() on page 389).

The program has the following output:

   coll:      1 2 3 4 5 6 7 8 9
   one left:  2 3 4 5 6 7 8 9 1
   two right: 9 1 2 3 4 5 6 7 8
   4 first:   4 5 6 7 8 9 1 2 3
Rotating Elements While Copying

OutputIterator

rotate_copy (ForwardIterator sourceBeg, ForwardIterator newBeg, ForwardIterator ourceEnd, OutputIterator destBeg)

The following program demonstrates how to use rotate_copy():

   // algo/rotate2.cpp

   #include "algostuff.hpp"
   using namespace std;


   int main()
   {

      set<int> coll;


      INSERT_ELEMENTS(coll,1,9);
      PRINT_ELEMENTS(coll);


      // print elements rotated one element to the left
      set<int>::iterator pos = coll.begin();
      advance(pos,1);
      rotate_copy (coll.begin(),                        // beginning of source
                   pos,                                 // new first element
                   coll.end(),                          // end of source
                   ostream_iterator<int>(cout," "));    // destination
      cout << endl;


      // print elements rotated two elements to the right
      pos = coll.end();
      advance(pos,-2);
      rotate_copy(coll.begin(),                        // beginning of source
                  pos,                                 // new first element
                  coll.end(),                          // end of source
                  ostream_iterator<int>(cout," "));    // destination
      cout << endl;


      // print elements rotated so that element with value 4 is the beginning
      rotate_copy (coll.begin(),                        // beginning of source
                   coll.find(4),                        // new first element
                   coll.end(),                          // end of source
                   ostreamIiterator<int>(cout," "));    // destination
      cout << endl; 
   }

Unlike the previous example of rotate() (see page 388), here a set is used instead of a vector. This has two consequences:

  1. You must use advance() (see Section 7.3.1,) to change the value of the iterator because bidirectional iterators do not provide operator +.

  2. You should use the find() member function instead of the find() algorithm because the former has better performance.

The program has the following output:

   1 2 3 4 5 6 7 8 9
   2 3 4 5 6 7 8 9 1
   8 9 1 2 3 4 5 6 7
   4 5 6 7 8 9 1 2 3

9.8.3 Permuting Elements

bool

next_permutation (BidirectionalIterator beg, BidirectionalIterator end)

bool

prev_permutation (BidirectionalIterator beg, BidirectionalIterator end)

The following example demonstrates how next_permutation() and prev_permutation() run through all permutations of the elements:

   // algo/perm1.cpp

   #include "algostuff.hpp"
   using namespace std;


   int main()
   {

       vector<int> coll;


       INSERT_ELEMENTS(coll,1,3);
       PRINT_ELEMENTS(coll,"on entry: ");


       /*permute elements until they are sorted
        *-runs through all permutations because the elements are sorted now
        */
       while (next_permutation(coll.begin(),coll.end())) {
           PRINTIELEMENTS(coll," ");
       }
       PRINT_ELEMENTS(coll."afterward: ");


       /*permute until descending sorted
        *-this is the next permutation after ascending sorting
        *-so the loop ends immediately
        */
       while (prev_permutation(coll.begin(),coll.end())) {
           PRINT_ELEMENTS(coll," ");
       }
       PRINT_ELEMENTS(coll,"now: ");

       /*permute elements until they are sorted in descending order
        *-runs through all permutations because the elements are sorted
        * in descending order now
        */
       while (prev_permutation(coll.begin(), coll.end()) {
           PRINT_ELEMENTS(coll," ");
       }
       PRINT_ELEMENTS(coll,"afterward: ");
   }

The program has the following output:

   on entry:   1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1
   afterward:  1 2 3
   now:        3 2 1
    3 1 2
    2 3 1
    2 1 3
    1 3 2
    1 2 3
   afterward:  3 2 1

9.8.4 Shuffling Elements

void

random_shuffle (RandomAccessIterator beg, RandomAccessIterator end)

void

random_shuffle (RandomAccessIterator beg, RandomAccessIterator end, RandomFunc& op)

You might wonder why random_shuffle() uses its optional operation as a nonconstant reference. It does so because random number generators typically have a local state. Old global C functions such as rand() store their local state in a static variable. However, this has some disadvantages: For example, the random number generator is inherently thread unsafe, and you can't have two independent streams of random numbers. Therefore, function objects provide a better solution by encapsulating their local state as one or more member variables. Thus, the random number generator can't be constant because it has to change its local state while generating a new random number. However, to have the random number generator nonconstant, you could still pass it by value instead of passing it by nonconstant reference. In this case each call would copy the random number generator and its state so that you get the same random sequence each time you pass the generator to the algorithm. Thus the generator is passed as a nonconstant reference. [6]

If you need the same random number sequence twice, you can simply copy it. However, if the generator is implemented in a way that uses a global state, you would still get different sequences.

The following example demonstrates how to shuffle elements by calling random_shuffle():

   // algo/random1.cpp

   #include <cstdlib>
   #include "algostuff.hpp"
   using namespace std;

   c1ass MyRandom {
     public:
      ptrdiff_t operator() (ptrdiff_t max) {
          double tmp;
          tmp = static_cast<double>(rand())
                  / static_cast<double>(RAND_MAX);
          return static_cast<ptrdiff_t>(tmp * max);
      }
   };

   int Main()
   {

       vector<int> coll;

       INSERT_ELEMENTS(coll,1,9);
       PRINT_ELEMENTS(coll,"coll: ");

       // shuffle all elements randomly
       random_shuffle (coll.begin(), coll.end());

       PRINT_ELEMENTS(coll."shuffled: ");

       // sort them again
       sort (coll.begin(), coll.end());
       PRINT_ELEMENTS(coll,"sorted: ");

       /*shuffle elements with self-written random number generator
        *-to pass an lvalue we have to use a temporary object
        */
       MyRandom rd;
       random_shuffle (coll.begin(), coll.end(),   // range
                       rd);                // random number generator
       PRINT_ELEMENTS(coll,"shuffled: ");
   }

The second call of random() uses the self-written random number generator rd(). It is an object of the auxiliary function object c1ass MyRandom, which uses an algorithm for random numbers that often is better than the usual direct call of rand().[7]

A possible (but not portable) output of the program is as follows:

   coll:      1 2 3 4 5 6 7 8 9
   shuffled:  2 6 9 5 4 3 1 7 8
   sorted:    1 2 3 4 5 6 7 8 9
   shuffled:  2 6 9 3 1 8 7 4 5

9.8.5 Moving Elements to the Front

BidirectionalIterator

partition (BidirectionalIterator beg, BidirectionalIterator end. UnaryPredicate op)

BidirectionalIterator

stable_partition (BidirectionalIterator beg, BidirectionalIterator end, UnaryPredicate op)

The following program demonstrates the use of and the difference between partition() and stable_partition():

   // algo/part1.cpp

   #include "algostuff.hpp"
   using namespace std;


   int main()
   {

       vector<int> coll1;
       vector<int> coll2;


       INSERT_ELEMENTS(coll1,1,9);
       INSERT_ELEMENTS(coll2,1,9);
       PRINT_ELEMENTS(coll1,"coll1: ");
       PRINTIELEMENTS(coll2,"coll2: ");
       cout << endl;


       // move all even elements to the front
       vector<int>::iterator pos1, pos2;
       pos1 = partition(coll1.begin(), coll1.end(),        // range
                        not1(bind2nd(modulus<int>(),2)));  // criterion
       pos2 = stable_partition(coll2.begin(), coll2.end(),        // range
                               not1(bind2nd(modulus<It>(),2)));   // crit


       // print collections and first odd element
       PRINT_ELEMENTS(coll1,"coll1: ");
       cout << "first odd element: " << *pos1 << endl;
       PRINT_ELEMENTS(coll2,"coll2: ");
       cout << "first odd element: " << *pos2 << endl;
   }

The program has the following output:

   coll1: 1 2 3 4 5 6 7 8 9
   coll2: 1 2 3 4 5 6 7 8 9

   coll1: 8 2 6 4 5 3 7 1 9
   first odd element: 5
   coll2: 2 4 6 8 1 3 5 7 9
   first odd element: 1

As this example shows, stable_partition(), unlike partition(), preserves the relative order of the even and the odd elements.

9.9 Sorting Algorithms

The STL provides several algorithms to sort elements of a range. In addition to full sorting, it provides different variants of partial sorting. If their result is enough, you should prefer them because they usually have better performance.

You might also use associative containers to have elements sorted automatically. However, note that sorting all elements once is usually faster than keeping them sorted always (see page 228 for details).

9.9.1 Sorting All Elements

void

sort (RandomAccessIterator beg, RandomAccessIterator end)

void

sort (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)

void

stable_sort (RandomAccessIterator beg, RandomAccessIterator end)

void

stable_sort (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)

The following example demonstrates the use of sort():

   // algo/sort1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       deque<int> coll;

       INSERT_ELEMENTS(coll,1,9);
       INSERT_ELEMENTS(coll,1,9);

       PRINT_ELEMENTS(coll,"on entry: ");

       // sort elements
       sort (coll.begin(), coll.end());

       PRINT_ELEMENTS(coll,"sorted: ");

       // sorted reverse
       sort (coll.begin(), coll.end(), // range
             greater<int>());          // sorting criterion

       PRINT_ELEMENTS(coll,"sorted >: ");
   }

The program has the following output:

   on entry: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
   sorted:   1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
   sorted >: 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1

See page 123 for an example that demonstrates how to sort according to a member of a c1ass.

The following program demonstrates how sort() and stable_sort() differ. The program uses both algorithms to sort strings only according to their number of characters by using the sorting criterion lessLength():

   // algo/sort2.cpp

   #include "algostuff.hpp"
   using namespace std;

   bool lessLength (const string& s1, const string& s2)
   {
       return s1.length() < s2.length();
   }

   int Main()
   {
       vector<string> coll1;
       vector<string> coll2;

       // fill both collections with the same elements
       coll1.push_back ("1xxx");
       coll1.push_back ("2x");
       coll1.push_back ("3x");
       coll1.push_back ("4x");
       coll1.push_back ("5xx");
       coll1.push_back ("6xxxx");
       coll1.push_back ("7xx");
       coll1.push_back ("8xxx");
       coll1.push_back ("9xx");
       coll1.push_back ("l0xxx");
       coll1.push_back ("11");
       coll1.push_back ("12");
       coll1.push_back ("13");
       coll1.push_back ("14xx");
       coll1.push_back ("15");
       coll1.push_back ("16");
       coll1.push_back ("17");
       col12 = coll1;

       PRINT_ELEMENTS (coll1,"on entry:\n ");

       // sort (according to the length of the strings)
       sort (coll1.begin(), coll1.end(),            // range
           lessLength);                             // criterion
       stable_sort (coll2.begin(), coll2.end(),     // range
                    lessLength);                    //criterion

       PRINT_ELEMENTS(coll1,"\nwith sort():\n ");
       PRINT_ELEMENTS(coll2,"\nwith stable_sort():\n ");
   }

The program has the following output:

   on entry:
    1xxx 2x 3x 4x 5xx 6xxxx 7xx 8xxx 9xx lOxxx 11 12 13 14xx 15 16 17

   with sort():
    17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx lOxxx 6xxxx

   with stable_sort():
    2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx lOxxx

Only stable_sort() preserves the relative order of the elements (the leading numbers tag the order of the elements on entry).

9.9.2 Partial Sorting

void

partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end)

void

partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end, BinaryPredicate op)

The following program demonstrates how to use partial_sort():

   // algo/psort1.cpp

    #include "algostuff.hpp"
    using namespace std;

    int Main()
    {
        deque<int> coll;

        INSERT_ELEMENTS(coll,3,7);
        INSERT_ELEMENTS(coll,2,6);
        INSERT_ELEMENTS(coll,1,5);
        PRINT_ELEMENTS(coll);

        // sort until the first five elements are sorted
        partial_sort (coll.begin(),        // beginning of the range
                      coll.begin()+5,      // end of sorted range
                      coll.end());         // end of full range
        PRINT_ELEMENTS(coll);

        // sort inversely until the first five elements are sorted
        partial_sort(coll.begin(),         // beginning of the range
                     coll.begin()+5,       // end of sorted range
                     coll.end(),           // end of full range
                     greater<int>());      // sorting criterion
        PRINT_ELEMENTS(coll);

        // sort all elements
        partial_sort (coll.begin(),         // beginning of the range
                      coll.end(),           // end of sorted range
                      coll.end());          // end of full range
        PRINT_ELEMENTS(coll);
   }

The program has the following output:

   3 4 5 6 7 2 3 4 5 6 1 2 3 4 5
   1 2 2 3 3 7 6 5 5 6 4 4 3 4 5
   7 6 6 5 5 1 2 2 3 3 4 4 3 4 5
   1 2 2 3 3 3 4 4 4 5 5 5 6 6 7

RandomAccessIterator

partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd, RandomAccessIterator destbeg, RandomAccessIterator destEnd)

partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd, RandomAccessIterator destbeg, RandomAccessIterator destEnd) BinaryPredicate op)

The following program demonstrates some examples of partial_sort_copy():

   // algo/psort2.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {

        deque<int> coll1;
        vector<int> coll6(6);      // initialize with 6 elements
        vector<int> coll30(30);    // initialize with 30 elements

        INSERT_ELEMENTS(coll1,3,7);
        INSERTIELEMEMTS(coll1,2,6);

        INSERT_ELEMENTS(coll1,1,5);
        PRINT_ELEMENTS(coll1);

        // copy elements of coll1 sorted into coll6
        vector<int>::iterator pos6;
        pos6 = partial_sort_copy (coll1.begin(), coll1.end(),
                                  coll6.begin(), coll6.end());

        // print all copied elements
        copy (coll6.begin(), pos6,
              ostream_iterator<int>(cout," "));
        cout << endl;

        // copy elements of coll1 sorted into coll30
        vector<int>::iterator pos30;
        pos30 = partial_sort_copy (coll1.begin(), coll1.end(),
                                   coll30.begin(), coll30.end(),
                                   greater<int>());

        // print all copied elements
        copy (coll30.begin(), pos30,
              ostream_iterator<int>(cout," "));
        cout << endl;
   }

The program has the following output:

   3 4 5 6 7 2 3 4 5 6 1 2 3 4 5
   1 2 2 3 3 3
   7 6 6 5 5 5 4 4 4 3 3 3 2 2 1

The destination of the first call of partial_sort_copy() has only six elements, so the algorithm copies only six elements and returns the end of coll6. The second call of partial_sort_copy() copies all elements of coll1 into coll30, which has enough room for them, and thus all elements are copied and sorted.

9.9.3 Sorting According to the nth Element

void

nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end)

void

nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end, BinaryPredicate op)

The following program demonstrates how to use nth_element():

   // algo/nth1.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main() 
    {

        deque<int> coll;

        INSERT_ELEMENTS(coll,3,7);
        INSERT_ELEMENTS(coll,2,6);
        INSERT_ELEMENTS(coll,1,5);
        PRINT_ELEMENTS(coll);

        // extract the four lowest elements
        nth_element (coll.begin(),     // beginning of range
                     coll.begin()+3,   // element that should be sorted correctly
                     coll.end());      // end of range

        // print them
        cout << "the four lowest elements are:  ";
        copy (coll.begin(), coll.begin()+4,
              ostream_iterator<int>(cout," ")); 
        cout << endl;

        // extract the four highest elements
        nth_element (coll.begin(),      // beginning of range
                     coll.end()-4,   // element that should be sorted correctly
                     coll.end());       // end of range

        // print them
        cout << "the four highest elements are: ";
        copy (coll.end()-4, coll.end(),
              ostream_iterator<int>(cout," "));
        cout << endl;

        // extract the four highest elements (second version)
        nth_element (coll.begin(),      // beginning of range
                     coll.begin()+3,    // element that should be sorted correctly
                     coll.end(),        // end of range
                     greater<int>());   // sorting criterion

        // print them
        cout << "the four highest elements are: ";
        copy (coll.begin(), coll.begin()+4,
              ostream_iterator<int>(cout," "));
        cout << endl;
    }

The program has the following output:

   3 4 5 6 7 2 3 4 5 6 1 2 3 4 5
    the four lowest elements are: 2 1 2 3
    the four highest elements are: 5 6 7 6
    the four highest elements are: 6 7 6 5

9.9.4 Heap Algorithms

A heap, in the context of sorting, is used as a particular way to sort elements. It is used by heapsort. A heap can be considered a binary tree that is implemented as a sequential collection. Heaps have two properties:

  1. The first element is always the largest element.

  2. You can add or remove an element in logarithmic time.

A heap is the ideal way to implement a priority queue (a queue that sorts its elements automatically). Therefore, the heap algorithms are used by the priority_queue container (see Section 10.3). The STL provides four algorithms to handle a heap:

  1. make_heap() converts a range of elements into a heap.

  2. push_heap() adds one element to the heap.

  3. pop_heap() removes the next element from the heap.

  4. sort_heap() converts the heap into a sorted collection (after that, it is no longer a heap).

As usual, you can pass a binary predicate as the sorting criterion. The default sorting criterion is operator <.

Heap Algorithms in Detail

void

make_heap (RandomAccesIterator beg, RandomAccesIterator end)

void

make_heap (RandomAccesIterator beg, RandomAccesIterator end, BinaryPredicate op)

void

push_heap (RandomAccesIterator beg, RandomAccesIterator end)

void

push_heap (RandomAccesIterator beg, RandomAccesIterator end, BinaryPredicate op)

void

pop_heap (RandomAccesIterator beg, RandomAccesIterator end)

void

pop_heap (RandomAccesIterator beg, RandomAccesIterator end, BinaryPredicate op)

void

sort_heap (RandomAccesIterator beg, RandomAccesIterator end)

void

sort_heap (RandomAccesIterator beg, RandomAccesIterator end, BinaryPredicate op)

Example Using Heaps

The following program demonstrates how to use the different heap algorithms:

   // algo/heap1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {

       vector<int> coll;

       INSERT_ELEMENTS(coll,3,7);
       INSERT_ELEMENTS(coll,5,9); 
       INSERT_ELEMENTS(coll,1,4);

       PRINT_ELEMENTS (coll, "on entry:          ");

       // convert collection into a heap
       make_heap (coll.begin(), coll.end());

       PRINT_ELEMENTS (coll, "after make_heap(): ");

       // pop next element out of the heap
       pop_heap (coll.begin(), coll.end());
       coll.pop_back();

       PRINT_ELEMENTS (coll, "after pop_heap():  ");

       // push new element into the heap
       coll.push_back (17);
       push_heap (coll.begin(), coll.end());

       PRINT_ELEMENTS (coll, "after push_heap(): ");

       /*convert heap into a sorted collection
        * - NOTE: after the call it is no longer a heap
        */
       sort_heap (coll.begin(), coll.end());

       PRINT_ELEMENTS (coll, "after sort_heap(): ");
   }

The program has the following output:

   on entry:           3 4 5 6 7 5 6 7 8 9 1 2 3 4
   after make_heap():  9 8 6 7 7 5 5 3 6 4 1 2 3 4
   after pop_heap():   8 7 6 7 4 5 5 3 6 4 1 2 3
   after push_heap():  17 7 8 7 4 5 6 3 6 4 1 2 3 5
   after sort_heap():  1 2 3 3 4 4 5 5 6 6 7 7 8 17

After make_heap(), the elements are sorted as a heap:

   9 8 6 7 7 5 5 3 6 4 1 2 3 4

Transform the elements into a binary tree, and you'll see that the value of each node is less than or equal to its parent node (Figure 9.1). Both push_heap() and pop_heap() change the elements so that the invariant of this binary tree structure (each node not greater than its parent node) remains stable.

Figure 9.1. Elements of a Heap as a Binary Tree

graphics/09fig01.gif

9.10 Sorted Range Algorithms

Sorted range algorithms require that the source ranges have the elements sorted according to their sorting criterion. They may have significant better performance than similar algorithms for unsorted ranges (usually logarithmic instead of linear complexity). You can use these algorithms with iterators that are not random access iterators. However, in this case, the algorithms have linear complexity because they have to step through the sequence element-b-element. Nevertheless, the number of comparisons may still have logarithmic complexity.

According to the standard, calling these algorithms for sequences that are not sorted on entry results in undefined behavior. However, for most implementations calling these algorithms also works for unsorted sequences. Nevertheless, to rely on this fact is not portable.

Associative containers provide special member functions for the searching algorithms presented here. When searching for a special value or key, you should use them.

9.10.1 Searching Elements

The following algorithms search certain values in sorted ranges.

Checking Whether One Element Is Present

bool

binary_search (ForwardIterator beg, ForwardIterator end, const T& value)

bool

binary_search (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)

The following program demonstrates how to use binary_search():

   // algo/bsearch1.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {

       list<int> coll;

       INSERT_ELEMENTS(coll,1,9);
       PRINT_ELEMENTS(coll) ;

       // check existence of element with value 5
       if (binary_search(coll.begin(), coll end(), 5)) {
           cout << "5 is present" << endl;
       }
       else {
           cout << "5 is not present" << endl;
       }

       // check existence of element with value 42
       if (binary_search(coll.begin(), coll.end(), 42)) {
           cout << "42 is present" << endl;
       }
       else {
           cout << "42 is not present" << endl;
       }
  }

The program has the following output:

   1 2 3 4 5 6 7 8 9
   5 is present
   42 is not present
Checking Whether Several Elements Are Present

bool

includes (InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg, InputIterator2 searchEnd)

bool

includes (InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg, InputIterator2 searchEnd, BinaryPredicate op)

The following program demonstrates the usage of includes():

   // algo/includes.cpp

    #include "algostuff.hpp"
    using namespace std;

    int main()
    {
        list<int> coll;
        vector<int> search;

        INSERT_ELEMENTS(coll,1,9);
        PRINT_ELEMENTS(coll,"coll: ");

        search.push_back(3);
        search.push_back(4);
        search.push_back(7);
        PRINT_ELEMENTS(search,"search: ");

        // check whether all elements in search are also in coll
        if (includes (coll.begin(), coll.end(),
                      search.begin(), search.end())) {
            cout << "all elements of search are also in coll"
                 << endl;
        }
        else {
            cout << "not all elements of search are also in coll"
                 << endl;
        }
    }

The program has the following output:

   coll:   1 2 3 4 5 6 7 8 9
   search: 3 4 7
   all elements of search are also in coll
Searching First or Last Possible Position

ForwardIterator

lower_bound (ForwardIterator beg, ForwardIterator end, const T& value)

ForwardIterator

lower_bound (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)

ForwardIterator

upper_bound (ForwardIterator beg, ForwardIterator end, const T& value)

ForwardIterator

upper_bound (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)

The following program demonstrates how to use lower_bound() and upper_bound()[8]:

   // algo/bounds1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {

       list<int> coll;

       INSERT_ELEMENTS(coll,1,9);
       INSERT_ELEMENTS(coll,1,9);
       coll.sort();
       PRINT_ELEMENTS(coll);

       // print first and last position 5 could get inserted
       list<int> :: iterator pos1, pos2;

       pos1 = lower_bound (coll.begin(), coll.end(),
                           5);
       pos2 = upper_bound (coll.begin(), coll.end(),
                           5);

       cout << "5 could get position "
            << distance(coll.begin(),pos1) + 1
            << " up to "
            << distance(coll.begin(),pos2) + 1
            << " without breaking the sorting" << endl;

       // insert 3 at the first possible position without breaking the sorting
       coll.insert (lower_bound(coll.begin(), coll.end(),
                                 3),
                    3);

       // insert 7 at the last possible position without breaking the sorting
       coll.insert (upper_bound(coll.begin(),coll.end(),
                                7),
                    7);

       PRINT_ELEMENTS(coll);
   }

The program has the following output:

   1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
   5 could get position 9 up to 11 without breaking the sorting
   1 1 2 2 3 3 3 4 4 5 5 6 6 7 7 7 8 8 9 9
Searching First and Last Possible Positions

pair<ForwardIterator,ForwardIterator>

equal_range (ForwardIterator beg, ForwardIterator end, const T& value)

pair<ForwardIterator,ForwardIterator>

equal_range (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)

The following program demonstrates how to use equal_range()[9]:

   // algo/eqrange1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       list<int> coll;

       INSERT_ELEMENTS(coll,1,9);
       INSERT_ELEMENTS(coll,1,9);
       coll.sort();
       PRINT_ELEMENTS(coll);

       // print first and last position 5 could get inserted
       pair<list<int>::iterator,list<int>::iterator> range;
       range = equal_range (coll.begin(), coll.end(),
                            5);

       cout << "5 could get position "
            << distance (coll.begin(),range, first) + 1
            << " up to "
            << distance(coll.begin().range.second) + 1
            << " without breaking the sorting" << endl;
   }

The program has the following output:

   1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
   5 could get position 9 up to 11 without breaking the sorting

9.10.2 Merging Elements

The following algorithms merge elements of two ranges. They process the sum, the union, the intersection, and so on.

Processing the Sum of Two Sorted Sets

OutputIterator

merge (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, Output Iterator destBeg)

OutputIterator

merge (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)

The following example demonstrates how to use merge():

   // algo/merge1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       list<int> coll1;
       set<int> coll2;

       // fill both collections with some sorted elements
       INSERT_ELEMENTS(coll1,l,6);
       INSERT_ELEMENTS(coll2,3,8);

       PRINT_ELEMENTS(coll1,"coll1: ");
       PRINT_ELEMENTS(coll2,"coll2: ");

       // print merged sequence
       cout << "merged: ";
       merge (coll1.begin(), coll1.end(),
              coll2.begin(), coll2.end(),
              ostream_iterator<int>(cout," "));
       cout << endl;
   }

The program has the following output:

   coll1:  1 2 3 4 5 6
   coll2:  3 4 5 6 7 8
   merged: 1 2 3 3 4 4 5 5 6 6 7 8

See page 421 for another example. It demonstrates how the different algorithms that are provided to combine sorted sequences differ.

Processing the Union of Two Sorted Sets

OutputIterator

set_union (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)

OutputIterator

set_union (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)

See page 421 for an example of the use of set_union(). This example also demonstrates how it differs from other algorithms that combine elements of two sorted sequences.

Processing the Intersection of Two Sorted Sets

OutputIterator

set_intersection (InputIterator source1Beg, InputIterator source1End. InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)

OutputIterator

set_intersection (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator sotirce2End, OutputIterator destBeg, BinaryPredicate op)

See page 421 for an example of the use of set_intersection(). This example also demonstrates how it differs from other algorithms that combine elements of two sorted sequences.

Processing the Difference of Two Sorted Sets

OutputIterator

set_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)

OutputIterator

set_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)

See page 421 for an example of the use of set_difference(). This example also demonstrates how it differs from other algorithms that combine elements of two sorted sequences.

OutputIterator

set_symmetric_difference (InputIterator source1 Beg, InputIterator source1 End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)

OutputIterator

set_symmetric_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)

See the following subsection for an example of the use of set_symmetric_difference(). This example also demonstrates how it differs from other algorithms that combine elements of two sorted sequences.

Example of All Merging Algorithms

The following example compares the different algorithms that combine elements of two sorted source ranges, demonstrating how they work and differ:

   // algo/setalgos.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       int c1[] = { 1, 2, 2, 4, 6, 7, 7, 9 };
       int num1 = sizeof(c1) / sizeof(int);

       int c2[] = { 2, 2, 2, 3, 6, 6, 8, 9 >;
       int num2 = sizeof(c2) / sizeof(int);

       // print source ranges
       cout << "c1:                         " ;
       copy (c1, c1+num1,
             ostream_iterator<int>(cout," ")) ;
       cout << endl;
       cout << "c2:                         " ;
       copy (c2, c2+num2,
             ostream_iterator<int>(cout," "));
       cout << '\n' << endl;

       // sum the ranges by using merge()
       cout << "merge():                    ";
       merge (c1, c1+num1,
              c2, c2+num2,
              ostream_iterator<int>(cout," "));
       cout << endl;

       // unite the ranges by using set_union()
       cout << "set_union():                ";
       set_union (c1, c1+num1,
                  c2, c2+num2,
                  ostream_iterator<int>(cout," "));
       cout << endl;

       // intersect the ranges by using set_intersection()
       cout << "set_intersection():         ";
       set_intersection (c1, c1+num1,
                         c2, c2+num2,
                         ostream_iterator<int>(cout," "));
       cout << endl;


       // determine elements of first range without elements of second range
       // by using set_difference()
       cout << "set_difference(): ";
       set_difference (c1, c1+num1,
                       c2, c2+num2,
                       ostream_iterator<int>(cout," "));
       cout << endl;


       // determine difference the ranges with set_symmetric_difference()
       cout << "set_symmetric_difference(): ";
       set_symmetric_difference (c1, c1+num1,
                                 c2, c2+num2,
                                 ostream_iterator<int>(cout," "));
       cout << endl;
   }

The program has the following output:

   c1:                          1 2 2 4 6 7 7 9
   c2:                          2 2 2 3 6 6 8 9

   merge():                     1 2 2 2 2 2 3 4 6 6 6 7 7 8 9 9
   set_union():                 1 2 2 2 3 4 6 6 7 7 8 9
   set_intersection():          2 2 6 9
   set_difference():            1 4 7 7
   set_symmetric_difference():  1 2 3 4 6 7 7 8
Merging Consecutive Sorted Ranges

void

inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, BidirectionalIterator end2)

void

inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, BidirectionalIterator end2, BinaryPredicate op)

The following program demonstrates the use of inplace_merge():

   // algo/imerge1.cpp

   #include "algostuff.hpp"
   using namespace std;


   int main()
   {

       list<int> coll;


       // insert two sorted sequences
       INSERT_ELEMENTS(coll,1,7);
       INSERT_ELEMENTS(coll,1,8);
       PRINT_ELEMENTS(coll);


       // find beginning of second part (element after 7)
       list<int>::iterator pos;
       pos = find (coll.begin(), coll.end(),    // range
                   7) ;                         // value
       ++pos;


       // merge into one sorted range
       inplace_merge (coll.begin(), pos, coll.end());


       PRINT_ELEMENTS(coll);
   }

The program has the following output:

   1 2 3 4 5 6 7 1 2 3 4 5 6 7 8
   1 1 2 2 3 3 4 4 5 5 6 6 7 7 8

9.11 Numeric Algorithms

This section presents the STL algorithms that are provided for numeric processing. However, you can process other than numeric values. For example, you can use accumulate() to process the sum of several strings. To use the numeric algorithms you have to include the header file <numeric>[10]:

   #include <numeric>

9.11.1 Processing Results

Computing the Result of One Sequence

T

accumulate (InputIterator beg, InputIterator end, T initValue)

T

accumulate (InputIterator beg. InputIterator end, T initValue, BinaryFunc op)

The following program demonstrates how to use accumulate() to process the sum and the product of all elements of a range:

   // algo/accu1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       vector<int> coll;

       INSERT_ELEMENTS(coll,1,9);
       PRINT_ELEMENTS(coll);

       // process sum of elements
       cout << "sum: "
            << accumulate (coll.begin(), coll.end(),     // range
                           0)                            // initial value
            << endl;

       // process sum of elements less 100
       cout << "sum: "
            << accumulate (coll.begin(), coll.end(),     // range
                           -100)                      // initial value
            << endl;

       // process product of elements
       cout << "product: "
            << accumulate (coll.begin(), coll.end(),     // range
                           1,                            // initial value
                           multiplies<int>())            // operation
            << endl;

       // process product of elements (use 0 as initial value)
       cout << "product: "
            << accumulate (coll.begin(), coll.end(),     // range
                           0,                            // initial value
                           multiplies<int>())            // operation
            << endl;
   }

The program has the following output:

   1 2 3 4 5 6 7 8 9
   sum: 45
   sum: -55
   product: 362880
   product: 0

The last output is 0 because any value multiplied by zero is zero.

Computing the Inner Product of Two Sequences

T

inner_product (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, T initValue)

T

inner_product (InputIterator1 beg1. InputIterator1 end1, InputIterator2 beg2, T initValue, BinaryFunc op1. BinaryFunc op2)

The program has the following output:

   1 2 3 4 5 6
   inner product: 91
   inner reverse product: 56
   product of sums: 46080

9.11.2 Converting Relative and Absolute Values

The following two algorithms provide the ability to convert a sequence of relative values into a sequence of absolute values, and vice versa.

Converting Relative Values into Absolute Values

OutputIterator

partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)

OutputIterator

partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryFunc op)

The following program demonstrates some examples of using partial_sum():

   // algo/partsum1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       vector<int> coll;

       INSERT_ELEMENTS(coll,1,6);
       PRINT_ELEMENTS(coll);

       // print all partial sums
       partial_sum (coll.begin(), coll.end(),           // source range
                    ostream_iterator<int>(cout," "));   // destination
       cout << end1;

       // print all partial products
       partial_sum (coll.begin(), coll.end(),           // source range
                    ostream_iterator<int>(cout," "),    // destination
                    multiplies<int>()) ;                // operation
       cout << endl;
   }

The program has the following output:

   1 2 3 4 5 6
   1 3 6 10 15 21
   1 2 6 24 120 720

See also the example of converting relative values into absolute values, and vice versa, on page 432.

Converting Absolute Values into Relative Values

OutputIterator

adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)

OutputIterator

adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryFunc op)

The following program demonstrates some examples of using adjacent_difference():

   // algo/adjdiff1.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       deque<int> coll;

       INSERT_ELEMENTS(coll,1,6);
       PRINT_ELEMENTS(coll);

       // print all differences between elements
       adjacent_difference (coll.begin(), coll.end(),          // source
                            ostream_iterator<int>(cout, " ")); // dest.
       cout << end1;

       // print all sums with the predecessors
       adjacent_difference (coll.begin(), coll.end(),          // source
                            ostream_iterator<int>(cout," "),   // dest.
                            plus <int>());                     // operation
       cout << endl;

       // print all products between elements
       adjacent_difference (coll.begin(), coll.end(),          // source
                            ostream_iterator<int>(cout," "),   // dest.
                            multiplies<int>());                // operation
       cout << endl;
   }

The program has the following output:

   1 2 3 4 5 6
   1 1 1 1 1 1
   1 3 5 7 9 1 1
   1 2 6   12 20 30

See also the example of converting relative values into absolute values, and vice versa, in the next subsection.

Example of Converting Relative Values into Absolute Values

The following example demonstrates how to use partial_sum() and adjacent_difference() to convert a sequence of relative values into a sequence of absolute values, and vice versa:

   // algo/relabs.cpp

   #include "algostuff.hpp"
   using namespace std;

   int main()
   {
       vector<int> coll;

       coll.push_back(17);
       coll.push_back(-3);
       coll.push_back(22);
       coll.push_back(13);
       coll.push_back(13);
       coll.push_back(-9);
       PRINT_ELEMENTS(coll,"coll: ")       ;

       // convert into relative values
       adjacent_difference (coll.begin(), coll.end(),     // source
                            coll.begin());                // destination

       PRINT_ELEMENTS (coll,"relative: ") ;

       // convert into absolute values
       partial_sum (coll.begin(), coll.end(),            // source
                    coll.begin());                       // destination
       PRINT_ELEMENTS(coll,"absolute: ");
   }

The program has the following output:

   coll:     17 -3 22 13 13 -9 
relative: 17 -20 25 -9 0 -22
absolute: 17 -3 22 13 13 -9

[1]  In the original STL the header file for all algorithms was <algo.h>.

[2]  In the original STL the header file for function objects and function adapters was <function.h>

[3]  See Section 2.3, for an introduction to and a discussion of complexity.

[4]  In the original STL the count() and count_if() had a fourth input/output parameter that was used as a counter and the return type was void.

[5]   next_permutation() and prev_permutation() could also be used to sort elements in a range. You just call them for a range as long as they return false. However, doing so would produce really bad performance.

[6]  Thanks to Matt Austern for this explanation.

[7]  The way MyRandom generates random numbers is introduced and described in Bjarne Stroustrup's The C++ Programming Language, 3rd edition.

[8]  Older STL versions might need the file distance.hpp from page 263.

[9]  Older STL versions might need the file distance.hpp from page 263.

[10]  In the original STL the numeric algorithms were defined in <algo.h>.

CONTENTS
Browser Based Help. Published by chm2web software.