13.1 Overview

In this chapter and in Chapter 14 we examine and illustrate each of the generic algorithms provided by the Standard C++ Library. The names and a short description of each of the algorithms in this chapter are given in Table 18. We have divided the algorithms into several categories, based on how they are typically used. This division differs from the categories used in the Standard C++ Library definition, which is based upon whether or not the algorithms modify their arguments.

Table 18 -- Generic algorithms of the Standard C++ Library

Algorithm Purpose
Algorithms initializing a sequence
fill
Fills a sequence with an initial value
fill_n
Fills n positions with an initial value
copy
Copies a sequence into another sequence
copy_backward
Copies a sequence into another sequence
generate
Initializes a sequence using a generator
generate_n
Initializes n positions using a generator
swap_ranges
Swaps values from two parallel sequences
Searching algorithms
find
Finds an element matching the argument
find_if
Finds an element satisfying a condition
Finds consecutive duplicate elements
find_first_of
Finds the first occurrence of one member of a sequence in another sequence
find_end
Finds the last occurrence of a sub-sequence in a sequence
search
Matches a sub-sequence within a sequence
max_element
Finds the maximum value in a sequence
min_element
Finds the minimum value in a sequence
mismatch
Finds first mismatch in parallel sequences
Algorithms for in-place transformations
reverse
Reverses the elements in a sequence
replace
Replaces specific values with new value
replace_if
Replaces elements matching predicate
rotate
Rotates elements in a sequence around a point
partition
Partitions elements into two groups
stable_partition
Partitions preserving original ordering
next_permutation
Generates permutations in sequence
prev_permutation
Generates permutations in reverse sequence
inplace_merge
Merges two adjacent sequences into one
random_shuffle
Randomly rearranges elements in a sequence
Removal algorithms
remove
Removes elements that match condition
unique
Removes all but first of duplicate values in sequences
Scalar generating algorithms
count
Counts number of elements matching value
count_if
Counts elements matching predicate
accumulate
Reduces sequence to a scalar value
inner_product
Gives inner product of two parallel sequences
equal
Checks two sequences for equality
lexicographical_compare
Compares two sequences
Sequence generating algorithms
transform
Transforms each element
partial_sum
Generates sequence of partial sums
Miscellaneous operations
for_each
Applies a function to each element of a collection

In this chapter, we illustrate the use of each algorithm with a series of short examples. Many of the algorithms are also used in the sample programs provided in the chapters on the various container classes. These cross references have been noted where appropriate.

All the short example programs described in this section are contained in a number of files, named alg1.cpp through alg6.cpp. In the files, the example programs are augmented with output statements describing the test programs and illustrating the results of executing the algorithms. So as not confuse the reader with unnecessary detail, we have generally omitted these output statements from the descriptions here. If you wish to see the text programs complete with output statements, you can compile and execute the test files. The expected output from these programs is also included in the distribution.

13.1.1 Include Files

To use any of the generic algorithms, you must first include the appropriate header file. The majority of the functions are defined in the header file algorithm. The functions accumulate(), inner_product(), partial_sum(), and adjacent_difference() are defined in the header file numeric.

```# include <algorithm>
# include <numeric>```