Cppin a Nutshell-10.3 Algorithms

10.3 Algorithms

The so-called algorithms in the standard library distinguish C++ from other programming languages. Every major programming language has a set of containers, but in the traditional object-oriented approach, each container defines the operations that it permits, e.g., sorting, searching, and modifying. C++ turns object-oriented programming on its head and provides a set of function templates, called algorithms, that work with iterators, and therefore with almost any container.

The advantage of the C++ approach is that the library can contain a rich set of algorithms, and each algorithm can be written once and work with (almost) any kind of container. And when you define a custom container, it automatically works with the standard algorithms (assuming you implemented the container's iterators correctly). The set of algorithms is easily extensible without touching the container classes. Another benefit is that the algorithms work with iterators, not containers, so even non-container iterators (such as the stream iterators) can participate.

C++ algorithms have one disadvantage, however. Remember that iterators, like pointers, can be unsafe. Algorithms use iterators, and therefore are equally unsafe. Pass the wrong iterator to an algorithm, and the algorithm cannot detect the error and produces undefined behavior. Fortunately, most uses of algorithms make it easy to avoid programming errors.

Most of the standard algorithms are declared in the <algorithm> header, with some numerical algorithms in <numeric>. Refer to the respective sections of Chapter 13 for details.

10.3.1 How Algorithms Work

The generic algorithms all work in a similar fashion. They are all function templates, and most have one or more iterators as template parameters. Because the algorithms are templates, you can instantiate the function with any template arguments that meet the basic requirements. For example, for_each is declared as follows:

template<typename InIter, typename Function>
Function for_each(InIter first, InIter last, Function func);

The names of the template parameters tell you what is expected as template arguments: InIter must be an input iterator, and Function must be a function pointer or functor. The documentation for for_each further tells you that Function must take one argument whose type is the value_type of InIter. That's all. The InIter argument can be anything that meets the requirements of an input iterator. Notice that no container is mentioned in the declaration or documentation of for_each. For example, you can use an istream_iterator.

For a programmer trained in traditional object-oriented programming, the flexibility of the standard algorithms might seem strange or backwards. Thinking in terms of algorithms takes some adjustment.

For example, some object-oriented container classes define sort as a member function or as a function that applies only to certain kinds of objects. (For example, Java defines sort only on arrays and List objects). If you have a new kind of container, you must duplicate the implementation of sort or make sure the implementation of your container maps to one of the standard implementations of sort. In C++, you can invent any kind of crazy container, and as long as it supports a random access iterator, you can use the standard sort function.

Whenever you need to process the contents of a container, you should think about how the standard algorithms can help you. For example, suppose you need to read a stream of numbers into a data array. Typically, you would set up a while loop to read the input stream and, for each number read, append the number to the array. Now rethink the problem in terms of an algorithmic solution. What you are actually doing is copying data from an input stream to an array, so you could use the copy algorithm:

std::copy(std::istream_iterator<double>(stream), 
          std::istream_iterator<double>(  ),
          std::back_inserter(data));

The copy algorithm copies all the items from one range to another. The input comes from an istream_iterator, which is an iterator interface for reading from an istream. The output range is a back_insert_iterator (created by the back_inserter function), which is an output iterator that pushes items onto a container.

At first glance, the algorithmic solution doesn't seem any simpler or clearer than a straightforward loop:

double x;
while (stream >> x)
  data.push_back(x);

More complex examples demonstrate the value of the C++ algorithms. For example, all major programming languages have a type for character strings. They typically also have a function for finding substrings. What about the more general problem of finding a subrange in any larger range? Suppose a researcher is looking for patterns in a data set and wants to see if a small data pattern occurs in a larger data set. In C++, you can use the search algorithm:

std::vector<double> data;
...
if (std::search(data.begin(  ), data.end(  ), pattern.begin(), 
    pattern.end(  )) != data.end(  ))
{
  // found the pattern...
}

A number of algorithms take a function pointer or functor (that is, an object that overloads operator( )) as one of the arguments. The algorithms call the function and possibly use the return value. For example, count_if counts the number of times the function returns a true (nonzero) result when applied to each element in a range:

bool negative(double x)
{
  return x < 0;
}

std::vector<double>::iterator::difference_type neg_cnt;
std::vector<double> data;
...
neg_cnt = std::count_if(data.begin(  ), data.end(  ), negative);

In spite of the unwieldy declaration for neg_cnt, the application of count_if to count the number of negative items in the data vector is easy to write and read.

If you don't want to write a function to be used only with an algorithm, you might be able to use the standard functors or function objects (which are declared in the <functional> header). For example, the same count of negative values can be obtained with the following:

std::vector<double>::iterator::difference_type neg_cnt;
std::vector<double> data;
...
neg_cnt = std::count_if(data.begin(  ), data.end(  ),
          std::bind2nd(std::less<double>, 0.0));

The std::less class template defines operator( ), so it takes two arguments and applies operator< to those arguments. The bind2nd function template takes a two-argument functor and binds a constant value (in this case 0.0) as the second argument, returning a one-argument function (which is what count_if requires). The use of standard function objects can make the code harder to read, but also helps avoid writing one-off custom functions. (The Boost project expands and enhances the standard library's binders. See Appendix B for information about Boost.)

When using function objects, be very careful if those objects maintain state or have global side effects. Some algorithms copy the function objects, and you must be sure that the state is also properly copied. The numerical algorithms do not permit function objects that have side effects.

Example 10-8 shows one use of a function object. It accumulates statistical data for computing the mean and variance of a data set. Pass an instance of Statistics to the for_each algorithm to accumulate the statistics. The copy that is returned from for_each contains the desired results.

Example 10-8. Computing statistics with a functor

#include <algorithm>
#include <cstddef>
#include <cmath>
#include <iostream>
#include <ostream>

template<typename T>
class Statistics {
public:
  typedef T value_type;
  Statistics(  ) : n_(0), sum_(0), sumsq_(0) {}
  void operator(  )(double x) {
    ++n_;
    sum_ += x;
    sumsq_ += x * x;
  }
  std::size_t count(  ) const { return n_; }
  T sum(  )        const { return sum_; }
  T sumsq(  )      const { return sumsq_; }
  T mean(  )       const { return sum_ / n_; }
  T variance(  )   const
      { return (sumsq_ - sum_*sum_ / n_) / (n_ - 1); }
private:
  std::size_t n_;
  T sum_;
  T sumsq_; // Sum of squares
};

int main(  )
{
  using namespace std;

  Statistics<double> stat = for_each(
    istream_iterator<double>(cin),
    istream_iterator<double>(  ),
    Statistics<double>(  ));

  cout << "count=" << stat.count(  ) << '\n';
  cout << "mean =" << stat.mean(  ) << '\n';
  cout << "var  =" << stat.variance(  ) << '\n';
  cout << "stdev=" << sqrt(stat.variance(  )) << '\n';
  cout << "sum  =" << stat.sum(  ) << '\n';
  cout << "sumsq=" << stat.sumsq(  ) << '\n';
}

10.3.2 Standard Algorithms

Chapter 13 describes all the algorithms in detail. This section presents a categorized summary of the algorithms.

It is always your responsibility to ensure that the output range is large enough to accommodate the input.

If the algorithm name ends with _if, the final argument must be a predicate, that is, a function pointer or function object that returns a Boolean result (a result that is convertible to type bool).

10.3.2.1 Nonmodifying operations

The following algorithms examine every element of a sequence without modifying the order:

count: Returns the number of items that match a given value
count_if: Returns the number of items for which a predicate returns true
for_each: Applies a function or functor to each item

10.3.2.2 Comparison

The following algorithms compare objects or sequences (without modifying the elements):

equal: Determines whether two ranges have equivalent contents
lexicographical_compare: Determines whether one range is considered less than another range
max: Returns the maximum of two values
max_element: Finds the maximum value in a range
min: Returns the minimum of two values
min_element: Finds the minimum value in a range
mismatch: Finds the first position where two ranges differ

10.3.2.3 Searching

The following algorithms search for a value or a subsequence in a sequence (without modifying the elements):

adjacent_find: Finds the first position where an item is equal to its neighbor
find: Finds the first occurrence of a value in a range
find_end: Finds the last occurrence of a subsequence in a range
find_first_of: Finds the first position where a value matches any one item from a range of values
find_if: Finds the first position where a predicate returns true
search
search_n: Finds a subsequence in a range

10.3.2.4 Binary search

The following algorithms apply a binary search to a sorted sequence. The sequence typically comes from a sequence container in which you have already sorted the elements. You can use an associative containers, but they provide the last three functions as member functions, which might result in better performance.

binary_search: Finds an item in a sorted range using a binary search
equal_range: Finds the upper and lower bounds
lower_bound: Finds the lower bound of where an item belongs in a sorted range
upper_bound: Finds the upper bound of where an item belongs in a sorted range

10.3.2.5 Modifying sequence operations

The following algorithms modify a sequence:

copy: Copies an input range to an output range
copy_backward: Copies an input range to an output range, starting at the end of the output range
fill
fill_n: Fills a range with a value
generate
generate_n: Fills a range with values returned from a function
iter_swap: Swaps the values that two iterators point to
random_shuffle: Shuffles a range into random order
remove: Reorders a range to prepare to erase all elements equal to a given value
remove_copy: Copies a range, removing all items equal to a given value
remove_copy_if: Copies a range, removing all items for which a predicate returns true
remove_if: Reorders a range to prepare to erase all items for which a predicate returns true
replace: Replaces items of a given value with a new value
replace_copy: Copies a range, replacing items of a given value with a new value
replace_copy_if: Copies a range, replacing items for which a predicate returns true with a new value
replace_if: Replaces items for which a predicate returns true with a new value
reverse: Reverses a range in place
reverse_copy: Copies a range in reverse order
rotate: Rotates items from one end of a range to the other end
rotate_copy: Copies a range, rotating items from one end to the other
swap_ranges: Swaps values in two ranges
transform: Modifies every value in a range by applying a transformation function
unique: Reorders a range to prepare to erase all adjacent, duplicate items
unique_copy: Copies a range, removing adjacent, duplicate items

10.3.2.6 Sorting

The following algorithms are related to sorting and partitioning. You can supply a comparison function or functor or rely on the default, which uses the < operator.

nth_element: Finds the item that belongs at the nth position (if the range were sorted) and reorders the range to partition it into items less than the nth item and items greater than or equal to the nth item.
partial_sort: Reorders a range so the first part is sorted.
partial_sort_copy: Copies a range so the first part is sorted.
partition: Reorders a range so that all items for which a predicate is true come before all items for which the predicate is false.
sort: Sorts items in ascending order.
stable_partition: Reorders a range so that all items for which a predicate is true come before all items for which the predicate is false. The relative order of items within a partition is maintained.
stable_sort: Sorts items in ascending order. The relative order of equal items is maintained.

10.3.2.7 Merging

The following algorithms merge two sorted sequences:

inplace_merge: Merges two sorted, consecutive subranges in place, so the results replace the original ranges
merge: Merges two sorted ranges, copying the results to a separate range

10.3.2.8 Set operations

The following algorithms apply standard set operations to sorted sequences:

includes: Determines whether one sorted range is a subset of another
set_difference: Copies the set difference of two sorted ranges to an output range
set_intersection: Copies the intersection of two sorted ranges to an output range
set_symmetric_difference: Copies the symmetric difference of two sorted ranges to an output range
set_union: Copies the union of two sorted ranges to an output range

10.3.2.9 Heap operations

The following algorithms treat a sequence as a heap data structure:

make_heap: Reorders a range into heap order
pop_heap: Reorders a range to remove the first item in the heap
push_heap: Reorders a range to add the last item to the heap
sort_heap: Reorders a range that starts in heap order into fully sorted order

10.3.2.10 Permutations

The following reorder the elements of a sequence to generate permutations:

next_permutation: Reorders a range to form the next permutation
prev_permutation: Reorders a range to form the previous permutation

10.3.3 Custom Algorithms

Writing your own algorithm is easy. Some care is always needed when writing function templates (as discussed in Chapter 7), but generic algorithms do not present any special or unusual challenges. Be sure you understand the requirements of the different categories of iterators and write your algorithm to use the most general category possible. You might even want to specialize your algorithm to improve its performance with some categories.

The first generic algorithm that most programmers will probably write is copy_if, which was inexplicably omitted from the standard. The copy_if function copies an input range to an output range, copying only the values for which a predicate returns true (nonzero). Example 10-9 shows a simple implementation of copy_if.

Example 10-9. One way to implement the copy_if function

template<typename InIter, typename OutIter, typename Pred>
OutIter copy_if(InIter first, InIter last, OutIter result, Pred pred)
{
  for (; first != last; ++first)
    if (pred(*first)) {
      *result = *first;
      ++result;
    }
  return result;
}

You can also specialize an algorithm. For example, you might be able to implement the algorithm more efficiently for a random access iterator. In this case, you can write helper functions and use the iterator_category trait to choose a specialized implementation. (Chapter 8 has more information about traits, including an example of how to use iterator traits to optimize a function template.)

The real trick in designing and writing algorithms is being able to generalize the problem and then find an efficient solution. Before running off to write your own solution, check the standard library. Your problem might already have a solution.

For example, I recently wanted to write an algorithm to find the median value in a range. There is no median algorithm, but there is nth_element, which solves the more general problem of finding the element at any sorted index. Writing median became a trivial matter of making a temporary copy of the data, calling nth_element, and then returning an iterator that points to the median value in the original range. Because median makes two passes over the input range, a forward iterator is required, as shown in Example 10-10.

Example 10-10. Finding the median of a range

template<typename FwdIter, typename Compare>
FwdIter median(FwdIter first, FwdIter last, Compare compare)
{
  typedef typename std::iterator_traits<FwdIter>::value_type value_type;
  std::vector<value_type> tmp(first, last);
  typename std::vector<value_type>::size_type median_pos = tmp.size(  ) / 2;
  std::nth_element(tmp.begin(  ), tmp.begin(  ) + median_pos,
              tmp.end(  ), compare);
  return std::find(first, last, tmp[median_pos]);
}