Cppin a Nutshell-13.1 <algorithm>

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.

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.

Technical Notes

The mismatch function template returns the pair (first1 + n, first2 + n), in which n is the smallest value in [0, last1 - first1) such that *(first1 + n) == *(first2 + n) is false and *(first1 + m) == *(first2 + m) is true for all m in [0, n). If there is no such n, n = last1 - first1.

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

Example

Example 13-4 shows a simple program that prints all the permutations of a sequence of integers. You can use this program to better understand the next_permutation function template.

Example 13-4. Generating permutations

#include <algorithm>
#include <iostream>
#include <istream>
#include <iterator>
#include <ostream>
#include <vector>
  
void print(const std::vector<int>& v)
{
  std::copy(v.begin(  ), v.end(  ),
            std::ostream_iterator<int>(std::cout, " "));
  std::cout << '\n';
}
  
int main(  )
{
  std::cout << "Enter a few integers, followed by EOF:";
  std::istream_iterator<int> start(std::cin);
  std::istream_iterator<int> end;
  std::vector<int> v(start, end);
  
  // Start with the first permutation (ascending order).
  std::sort(v.begin(  ), v.end(  ));
  print(v);
  
  // Print all the subsequent permutations.
  while (std::next_permutation(v.begin(  ), v.end(  )))
    print(v);
}

Technical Notes

Complexity is linear: at most, there are (last - first) / 2 swaps.

Technical Notes

Precondition: nth is in the range [first, last).

Postcondition: *i < *nth for all i in [first, nth), !(*j < *nth) for all j in [nth, last), and !(*k < *nth) for all k in [nth + 1, last).

Complexity is linear for the average case but is allowed to perform worse in the worst case.

Technical Notes

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

Complexity is logarithmic, taking about (last - first) x log(middle - first) comparisons.

Technical Notes

Let n = min(last - first, result_last - result_first).

Postcondition: for all i in [result_first, result_first + n - 1), *(i + 1) < *i is false.

Complexity is logarithmic, taking about (last - first) x log n comparisons.

Technical Notes

Postcondition: Let r be an iterator in the range [first, last] such that pred(*i) is true for all i in [first, r), and pred(*j) is false for all j in [r, last).

The partition function template returns r.

Complexity is linear: pred is called exactly last - first times, and at most (last - first) / 2 swaps are performed.

Technical Notes

Precondition: [first, last) is a heap (see make_heap for the definition of a heap).

Postcondition: [first, last - 1) is a heap, and !(*(last - 1) < *i) for all i in [first, last - 1).

Complexity is logarithmic: at most 2 x log(last - first) comparisons are performed.

Technical Notes

Complexity is linear: at most (last - first) / 2 swaps are performed.

Technical Notes

Precondition: [first, last - 1) is a heap (see make_heap for the definition of a heap).

Postcondition: [first, last) is a heap.

Complexity is logarithmic: at most log(last - first) comparisons are performed.

Technical Notes

Complexity is linear: exactly (last - first) + 1 swaps are performed.

Technical Notes

The remove function template assigns *(first + n++) = *(first + m), in which n starts at 0, for all values of m in [0, last - first) in which *(first + m) == value is false. The return value is first + n.

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

Technical Notes

The remove_copy function template assigns *(result + n++) = *(first + m), in which n starts at 0, for all values of m in [0, last - first), in which *(first + m) == value is false. The return value is result + n.

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

Technical Notes

The remove_copy_if function template assigns *(result + n++) = *(first + m), in which n starts at 0, for all values of m in [0, last - first), in which pred(*(first + m)) is false. The return value is result + n.

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

Technical Notes

The remove_if function template assigns *(first + n++) = *(first + m), in which n starts at 0, for all values of m in [0, last - first), in which pred(*(first + m)) is false. The return value is first + n.

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

Technical Notes

The replace function template assigns *i = (*i == old_value) ? new_value : *i for all i in [first, last).

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

Technical Notes

The replace_copy function template assigns *(result + n) = *(first + n) == old_value ? new_value : *(first + n) for all n in [0, last - first).

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

Technical Notes

The replace_copy_if function template assigns *(result + n) = *(first + n) == pred(*(first + n)) ? new_value : *(first + n) for all n in [0, last - first).

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

Technical Notes

The replace_if function template assigns *i = pred(*i) ? new_value : *i for all i in [first, last).

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

Technical Notes

The reverse function template swaps *(first + n) with *(last - n - 1) for all n in [0, (last - first) / 2].

Complexity is linear: exactly (last - first) / 2 swaps are performed.

Technical Notes

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

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

Technical Notes

For all n in [0, last - first), the rotate function template moves *(first + n) into position first + (n + (last - middle)) % (last - first).

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

Technical Notes

The rotate_copy function template assigns *(result + (n + (last - middle)) % (last - first)) = *(first + n) for all n in [0, last - first). It returns result + (last - first).

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

Technical Notes

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

The search function template returns first1 + n, in which n is the smallest value in the range [0, length1 - length2) such that *(i + n + m) == (first2 + m) for all 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

The search_n function template returns first + n, in which n is the smallest value in the range [0, last - first) such that *(i + n + m) == value for all m in the range [0, count). It returns last if no such n can be found.

Complexity: at most n x (last - first) comparisons are performed.

Technical Notes

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, return - 1).

The set_difference function template assigns *(result + n++) = *(first1 + m) for all m in [first1, last1), in which *(first1 + m) is not in [first2, last2). It returns result + n.

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 [first1, last1 - 1) and !(*(j + 1) < *j) for all j in [first2, last2 - 1).

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

The set_intersection function template assigns *(result + n++) = *(first1 + m) for all m in [first1, last1), in which *(first1 + m) is in [first2, last2). It returns result + n.

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 [first1, last1 - 1) and !(*(j + 1) < *j) for all j in [first2, last2 - 1).

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

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 [first1, last1 - 1) and !(*(j + 1) < *j) for all j in [first2, last2 - 1).

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

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

Technical Notes

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

Complexity is n log n comparisons in the average case, in which n = last - first. Worst case performance might be worse. Use stable_sort if the worst-case performance is more important than the average performance.

Technical Notes

Precondition: [first, last) is a heap (see make_heap for the definition of a heap).

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

Complexity is at most n log n comparisons, in which n = last - first.

Technical Notes

Postcondition: Let r be an iterator in the range [first, last] such that pred(*i) is true for all i in [first, r), and pred(*j)is false for all j in [r, last).

The stable_partition function template returns r.

Complexity is linear if there is enough memory. Otherwise, at most n log n swaps are performed, in which n = last - first. In all cases, pred is called exactly n times.

Technical Notes

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

Complexity is at most n log n comparisons, in which n = last - first, provided that enough memory is available for temporary results. If memory is limited, the complexity is at most n (log n)² comparisons.

Technical Notes

The swap_ranges function template performs the equivalent of swap(*(first1 + n), *(first2 + n)) for all n in [0, last1 - first1).

Complexity is linear: exactly last1 - first1 swaps are performed.

Technical Notes

The first form of transform assigns *(result + n) = unop(*(first + n)) for all n in [0, last - first).

The second form assigns *(result + n) = binop(*(first1 + n), *(first2 + n)) for all n in [0, last1 - first1).

Complexity is linear: unop or binop is called exactly n times, in which n = last - first for a unary operator or last1 - first1 for a binary operator.

Technical Notes

The unique function template assigns *(first + n++) = *(first + m) for all m in [0, last - first), in which m == 0 or *(first +m) == *(first + m - 1) is false. It returns first + n.

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

Technical Notes

The unique_copy function template assigns *(result + n++) = *(first + m) for all m in [0, last - first), in which m == 0 or *(first +m) == *(first + m - 1) is false. It returns result + n.

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

Technical Notes

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

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

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

Figure 13-8. Checking two sequences for a mismatch

Technical Notes

See Also

Figure 13-9. Permutations of a sequence

Example

Example 13-4. Generating permutations

Technical Notes

See Also

Figure 13-10. Reordering a range with nth_element