لطفا منتظر باشید ...
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]);
}
