13.1 <algorithm>

The <algorithm> header declares the generic algorithm function templates for operating on iterators and other objects. Refer to Chapter 10 for more information about using and writing generic algorithms and about the iterators they use. See Chapter 8 for a discussion of iterator traits.

If you are at all confused by the removal algorithms (such as pop_heap, remove, and unique), be sure to read Chapter 10 first.

This section uses a number of abbreviations and conventions. First, each algorithm is described using plain English. Then, a more mathematical description of the algorithm, which tends to be harder to read, is given in a "Technical Notes" section.

The names of the template parameters tell you which category of iterator is expected. The iterator category is the minimal functionality needed, so you can, for example, use a random access iterator where at least a forward iterator is needed. (See Chapter 10 for more information on iterators and iterator categories.) To keep the syntax summaries short and readable, the iterator categories are abbreviated, as shown in Table 13-1.

Table 13-1. Template parameter names for iterator categories
Parameter name	Iterator category
`BidiIter`	Bidirectional iterator
`FwdIter`	Forward iterator
`InIter`	Input iterator
`OutIter`	Output iterator
`RandIter`	Random access iterator

Other template parameter names are chosen to be self-explanatory. For example, any name that ends in Predicate is a function that returns a Boolean result (which can be type bool or any other type that is convertible to bool) or a Boolean functional object (an object that has a function call operator that returns a Boolean result).

A number of algorithms require sorted ranges or otherwise use a comparison function to test the less-than relationship. The library overloads each algorithm: the first function uses operator<, and the second accepts a function pointer or function object to perform the comparison. The comparison function takes two arguments and returns a Boolean result. In the "Technical Notes" sections, the < relationship signifies operator< or the caller-supplied function, depending on the version of the algorithm you are using. If you overload operator< or provide your own comparison function, make sure it correctly implements a less-than relationship. In particular, a < a must be false for any a.

In this section, the following conventions are used:

Iterators are usually used in ranges that represent all the elements in the range or sequence. A range is written using standard mathematical notation: a square bracket denotes an inclusive endpoint of a range, and a parenthesis denotes an exclusive endpoint of a range. Thus, [x, y) is a range that starts at x, including x, and ends at y, excluding y. Chapter 10 also discusses this aspect of iterators.
Arithmetic expressions that involve iterators work as though each iterator were a random access iterator, even if the iterator is from a different category. For example, i - 1 for an input iterator is not allowed in C++ code, but in this section, it means the input iterator that points to one position before i.
The names used for input ranges are typically first and last, in which first is an iterator that points to first the element of the range, and last is an iterator that points to one past the end of the range. Thus, the range is written as [first, last).
An iterator that advances from first to last is typically called iter.
Output iterators are typically named result. Most algorithms specify only the start of the output range. It is your responsibility to ensure that the output range has room to accommodate the entire output. The behavior is undefined if the output range overflows.

In each "Technical Notes" section, conventional mathematical notation is used with some aspects of C++ notation, such as *, which dereferences an iterator. Also, a single equal sign (=) means assignment, and a double equal sign (==) means comparison for equality. The following conventions are used for names:

i, j, k: Denote iterators, and *i, *j, and *k denote the values that the iterators point to.
n, m: Denote integers.
a, b, c: Denote values, which are usually of types that can be assigned to or from a dereferenced iterator (e.g., *i = a).

adjacent_find function template

Searches for a pair of adjacent, equal items

template<typename FwdIter>

  FwdIter adjacent_find(FwdIter first, FwdIter last);

template<typename FwdIter, typename BinaryPredicate>

  FwdIter adjacent_find(FwdIter first, FwdIter last, BinaryPredicate pred);

The adjacent_find function template looks for the first set of adjacent items in the range [first, last) that are equal (first version) or in which pred(*iter, (*iter+1)) is true (second version). Items are "adjacent" when their iterators differ by one position.

The return value is an iterator that points to the first of the adjacent items, or last if no matching items are found. See Figure 13-1 for an example.

Figure 13-1. Using adjacent_find to find two adjacent, equivalent items

Technical Notes

The adjacent_find function template returns i, in which i = first + n, and n is the smallest value such that *(first + n) == *(first + n + 1) and first + n + 1 < last, or, if there is no such n, i = last.

Complexity is linear: the standard is muddled, but any reasonable implementation calls the predicate (operator== or pred) exactly n + 1 times.

Technical Notes

Precondition: !(*(i + 1) < *i) for all i in [first, last - 1).

The binary_search function template returns true if there is an i in [first, last) such that !(*i < value) and !(value < *i). It returns false if there is no such i.

Complexity is logarithmic. The number of comparisons is at most log(last - first) + 2. Although the iterator can be a forward iterator, the best performance is obtained with a random access iterator. With a forward or bidirectional iterator, the iterator is advanced a linear number of times, even though the number of comparisons is logarithmic.

Technical Notes

The copy function template assigns *(result + n) = *(first + n) for all n in the range [0, last - first).

Complexity is linear: exactly last - first assignments are performed.

Technical Notes

The copy_backward function template assigns *(result - n) = *(last - n) for all n in the range [1, last - first].

Complexity is linear: exactly last - first assignments are performed.

Technical Notes

Complexity is linear: exactly last - first comparisons are performed.

Technical Notes

Complexity is linear: pred is called exactly last - first times.

Technical Notes

The equal function template returns true if *(first1 + n) == *(first2 + n) for all n in the range [0, last1 - first1).

Complexity is linear: at most last1 - first1 comparisons are performed.

Technical Notes

Precondition: !(*(i + 1) < *i) for all i in [first, last - 1).

The equal_range function template returns the equivalent of calling the following, although the actual implementation might be different:

std::make_pair(std::lower_bound(first, last, value),

               std::upper_bound(first, last, value))

or:

std::make_pair(std::lower_bound(first, last, value, comp),

               std::upper_bound(first, last, value, comp))

Complexity is logarithmic. The number of comparisons is at most 2 x log(last - first) + 1. Although the iterator can be a forward iterator, the best performance is obtained with a random access iterator. With a forward or bidirectional iterator, the iterator is advanced a linear number of times, even though the number of comparisons is logarithmic.

Technical Notes

The fill function template assigns *i = value for all i in the range [first, last).

Complexity is linear: exactly last - first assignments are performed.

Technical Notes

The fill_n function template assigns *(first + n) = value for all n in the range [0, n).

Complexity is linear: exactly n assignments are performed.

Technical Notes

The find function template returns i = first + n, in which n is the smallest value such that *(first + n) == value. If there is no such n, i = last.

Complexity is linear: at most last - first comparisons are performed.

Technical Notes

Let length1 = last1 - first1 and length2 = last2 - first2.

The find_end function template returns first1 + n, in which n is the highest value in the range [0, length1 - length2) such that *(i + n + m) == (first2 + m) for all i in the range [first1, last1) and m in the range [0, length2). It returns last1 if no such n can be found.

Complexity: at most length1 x length2 comparisons are performed.

Technical Notes

Let length1 = last1 - first1 and length2 = last2 - first2.

The find_first_of function template returns first1 + n where n is the smallest value in the range [0, length1) such that *(first1 + n) == (first2 + m) for some m in the range [0, length2). It returns last1 if no such n and m can be found.

Complexity: at most length1 x length2 comparisons are performed.

Technical Notes

The find_if function template returns i = first + n, in which n is the smallest value such that pred(*(first + n), value) is true. If there is no such n, i = last.

Complexity is linear: pred is called at most last - first times.

Example

Example 13-1 shows how the use for_each to test whether a sequence is sorted. The is_sorted object remembers the previous item in the sequence, which it compares with the current item. The overloaded bool operator returns true if the sequence is sorted so far or false if the sequence is out of order. The example takes advantage of the fact that for_each returns the f parameter as its result.

Example 13-1. Using for_each to test whether a list is sorted

#include <iostream>

#include <algorithm>

#include <list>

  

template<typename T>

class is_sorted

{

public:

  is_sorted(  ) : first_time(true), sorted(true) {}

  void operator(  )(const T& item) {

    // for_each calls operator(  ) for each item.

    if (first_time)

      first_time = false;

    else if (item < prev_item)

      sorted = false;

    prev_item = item;

  }

  operator bool(  ) { return sorted; }

private:

  bool first_time;

  bool sorted;

  T prev_item;

};

  

int main(  )

{

  std::list<int> l;

  l.push_back(10);

  l.push_back(20);

  ...

  if (std::for_each(l.begin(  ), l.end(  ), is_sorted<int>(  )))

    std::cout << "list is sorted" << '\n';

}

Technical Notes

Complexity is linear: f is called exactly last - first times.

Example

Example 13-2 shows a simple way to fill a sequence with successive integers.

Example 13-2. Using generate to fill a vector with integers

#include <algorithm>

#include <iostream>

#include <iterator>

#include <vector>

  

// Generate a series of objects, starting with "start".

template <typename T>

class series {

public:

  series(const T& start) : next(start) {}

  T operator(  )(  ) { return next++; }

private:

  T next;

};

  

int main(  )

{

  std::vector<int> v;

  v.resize(10);

  // Generate integers from 1 to 10.

  std::generate(v.begin(  ), v.end(  ), series<int>(1));

  // Print the integers, one per line.

  std::copy(v.begin(  ), v.end(  ),

            std::ostream_iterator<int>(std::cout, "\n"));

}

Technical Notes

Complexity is linear: gen is called exactly last - first times.

Example

Example 13-3 shows a simple way to print a sequence of integers.

Example 13-3. Using generate_n to print a series of integers

#include <algorithm>

#include <iostream>

#include <iterator>

  

// Use the same series template from Example 13-2.

  

int main(  )

{

  // Print integers from 1 to 10.

  std::generate_n(std::ostream_iterator<int>(std::cout,"\n"),

                  10, series<int>(1));

}

Technical Notes

Complexity is linear: gen is called exactly n times.

Technical Notes

Precondition: !(*(i + 1) < *i) for all i in [first1, last1 - 1) and !(*(j + 1) < *j) for all j in [first2, last2 - 1).

The includes function template returns true if there is an i in [first1, last1) such that *(i + n) = *(first2 + n) for all n in [0, (last2 - first2)). It returns last1 if there is no such i.

Complexity is linear: at most, 2 x ((last1 - first1) + (last2 - first2)) - 1 comparisons are performed.

Technical Notes

Precondition: !(*(i + 1) < *i) for all i in [first, middle - 1) and !(*(j + 1) < *j) for all j in [middle, last - 1).

Postcondition: !(*(i + 1) < *i) for all i in [first, last - 1).

Complexity is usually linear with n + 1 comparisons, but if enough temporary memory is not available, the complexity might be n log n, in which n is last - first.

Technical Notes

Complexity is constant.

Technical Notes

Let length1 = last1 - first1, length2 = last2 - first2, and minlength = min(length1, length2).

The lexicographical_compare function template returns true if either of the following conditions is true:

There is an n in [0, minlength) such that *(first1 + m) == *(first2 + m) for all m in [0, n - 1), and *(first1 + n) < *(first2 + n).
*(first1 + n) == *(first2 + n) for all n in [0, length2) and length2 < length1.

Complexity is linear: at most, minlength comparisons are performed.

Example

#include <algorithm>

#include <iostream>

#include <ostream>

  

int main(  )

{

  using namespace std;

  

  int a[] = { 1, 10, 3, 42 };

  int b[] = { 1, 10, 42, 3 };

  int c[] = { 1, 10 };

  

  cout << boolalpha;

  cout << lexicographical_compare(a, a+4, b, b+4); // true

  cout << lexicographical_compare(a, a+4, c, c+2); // false

  cout << lexicographical_compare(a, a+4, a, a+4); // false

  cout << lexicographical_compare(c, c+2, b, b+4); // true

}

Technical Notes

Precondition: !(*(i + 1) < *i) for all i in [first, last - 1).

The lower_bound function template returns first + n, in which n is the highest value in [0, last - first) such that *(first + m) < value for all m in [0, n).

Complexity is logarithmic. The number of comparisons is at most log(last - first) + 1. Although the iterator can be a forward iterator, the best performance is obtained with a random access iterator. With a forward or bidirectional iterator, the iterator is advanced a linear number of times, even though the number of comparisons is logarithmic.

Heap Data Structure

A heap is a data structure that is ideally suited for implementing priority queues. C++ defines a range as a heap if two properties are satisfied:

The first element of the range is the largest, which strictly means that *first < *(first + n) is false for all n in [1, last - first).
Adding or removing an element can be done in logarithmic time, and the result is still a heap.

The classic example of a heap is a binary tree, in which each node is greater than or equal to its children, but the relative order of the children is not specified. Thus, the root of the tree is the largest element in the entire tree.

Technical Notes

Postcondition: [first, last) is a heap.

Complexity is linear: at most, 3 x (last - first) comparisons are performed.

Technical Notes

The max_element function template returns first + n, in which n is the smallest value in [0, last - first) such that for all m in [0, last - first), *(first + n) < *(first + m) is false.

Complexity is linear: exactly max(last - first - 1, 0) comparisons are performed.

Technical Notes

Let length1 = last1 - first1 and length2 = last2 - first2.

Precondition: !(*(i + 1) < *i) for all i in [first1, last1 - 1) and !(*(j + 1) < *j) for all j in [first2, last2 - 1).

Postcondition: !(*(i + 1) < *i) for all i in [result, result + length1 + length2 - 1).

Complexity is linear: at most, length1 + length2 - 1 comparisons are performed.

Technical Notes

The min_element function template returns first + n, in which n is the smallest value in [0, last - first) such that for all m in [0, last - first), *(first + m) < *(first + n) is false.

Complexity is linear: exactly max(last - first - 1, 0) comparisons are performed.

13.1 <algorithm>

Table 13-1. Template parameter names for iterator categories

Figure 13-1. Using adjacent_find to find two adjacent, equivalent items

Technical Notes

See Also

Technical Notes

See Also

Figure 13-2. Copying a range

Technical Notes

See Also

Figure 13-3. Copying a range backward

Technical Notes

See Also

Technical Notes

See Also

Technical Notes

See Also

Technical Notes

See Also

Figure 13-4. Finding the limits of where the value 36 belongs in a sorted range

Technical Notes

See Also

Technical Notes

See Also

Technical Notes

See Also

Technical Notes

See Also

Figure 13-5. Finding a subsequence with find_end and search

Technical Notes

See Also

Figure 13-6. Finding any one of a list of items

Technical Notes

See Also

Technical Notes

See Also

Example

Example 13-1. Using for_each to test whether a list is sorted

Technical Notes

See Also

Example

Example 13-2. Using generate to fill a vector with integers

Technical Notes

See Also

Example

Example 13-3. Using generate_n to print a series of integers

Technical Notes

See Also

Technical Notes

See Also

Figure 13-7. Merging two sorted ranges

Technical Notes

See Also

Technical Notes

See Also

Technical Notes

Example

See Also

Technical Notes

See Also

Heap Data Structure

Technical Notes

See Also

See Also

Technical Notes

See Also

Technical Notes

See Also

See Also

Technical Notes

See Also