(possibly distinct) types and returns a value of any type (including void).
- <!-- Unary Predicate: A Unary Function that returns a bool. -->
- <!-- Binary Predicate: A Binary Function that returns a bool. -->
+ Binary Function: A type of function object that takes two arguments of any two
+ (possibly distinct) types and returns a value of any type (including void).
+ Unary Predicate: A Unary Function that returns a bool.
+ Unary Predicate: A Unary Function that returns a bool.
+ Binary Predicate: A Binary Function that returns a bool.
+ Binary Predicate: A Binary Function that returns a bool.
indicate these assumptions:
- <!-- LessThanComparable: A class that has a less-than operator<. -->
- <!-- Assignable: A class that has a copy-assignment operator= for its own type. -->
- <!-- EqualityComparable: A class that has an equivalence operator== for its own type. -->
+ In addition, certain algorithms make assumptions about the operations available
+ for the types of objects they process. We will use the following terms to
+ indicate these assumptions:
+ LessThanComparable: A class that has a less-than operator<.
+ LessThanComparable: A class that has a less-than operator<.
+ Assignable: A class that has a copy-assignment operator= for its own type.
+ Assignable: A class that has a copy-assignment operator= for its own type.
+ EqualityComparable: A class that has an equivalence operator== for its own type.
+ EqualityComparable: A class that has an equivalence operator== for its own type.
+ We will use these terms later in this chapter to describe the generic algorithms
+ in the standard library.
for use with other function objects in a chain of operations.
+ The <functional> header defines a number of useful generic function
+ objects. They are admittedly simple, but you can use them to compose more
+ complicated function objects. Consequently, in many instances, you can construct
+ complicated predicates without writing a single function. You do so by using
+ function object adaptors[90] to take the simple function objects and adapt them
+ for use with other function objects in a chain of operations.
parameter at 15 using the function object adaptor bind2nd, like this:
+ To illustrate, let’s use only standard function objects to accomplish what gt15(
+ ) did earlier. The standard function object, greater, is a binary function
+ object that returns true if its first argument is greater than its second
+ argument. We cannot apply this directly to a sequence of integers through an
+ algorithm such as remove_copy_if( ) because remove_copy_if( ) expects a unary
+ predicate. We can construct a unary predicate on the fly that uses greater to
+ compare its first argument to a fixed value. We fix the value of the second
+ parameter at 15 using the function object adaptor bind2nd, like this:
and the fixed value it stored.
+ This program produces the same result as CopyInts3.cpp, but without writing our
+ own predicate function gt15( ). The function object adaptor bind2nd( ) is a
+ template function that creates a function object of type binder2nd, which simply
+ stores the two arguments passed to bind2nd( ), the first of which must be a
+ binary function or function object (that is, anything that can be called with
+ two arguments). The operator( ) function in binder2nd, which is itself a unary
+ function, calls the binary function it stored, passing it its incoming parameter
+ and the fixed value it stored.
+ To make the explanation concrete for this example, let’s call the instance of
+ binder2nd created by bind2nd( ) by the name b. When b is created, it receives
+ two parameters (greater<int>( ) and 15) and stores them. Let’s call the instance
+ of greater<int> by the name g, and call the instance of the output stream
+ iterator by the name o. Then the call to remove_copy_if( ) earlier conceptually
+ As remove_copy_if( ) iterates through the sequence, it calls b on each element,
+ to determine whether to ignore the element when copying to the destination. If
+ we denote the current element by the name e, that call inside remove_copy_if( )
the earlier call is the same as
+ but binder2nd’s function call operator just turns around and calls g(e,15), so
+ the earlier call is the same as
+ which is the comparison we were seeking. There is also a bind1st( ) adaptor that
+ creates a binder1st object, which fixes the first argument of the associated
its truth value. The following program will do the job:
+ As another example, let’s count the number of elements in the sequence not equal
+ to 20. This time we’ll use the algorithm count_if( ), introduced earlier. There
+ is a standard binary function object, equal_to, and also a function object
+ adaptor, not1( ), that takes a unary function object as a parameter and invert
+ its truth value. The following program will do the job:
//: V2C06:CountNotEqual.cpp
before, we call the current element of the sequence by the name e, the statement
+ As remove_copy_if( ) did in the previous example, count_if( ) calls the
+ predicate in its third argument (let’s call it n) for each element of its
+ sequence and increments its internal counter each time true is returned. If, as
+ before, we call the current element of the sequence by the name e, the statement
- <!-- in the implementation of count_if is interpreted as -->
+ in the implementation of count_if is interpreted as
+ in the implementation of count_if is interpreted as
if(!bind1st(equal_to<int>, 20)(e))
- <!-- which ends up as -->
arguments, we could have used either bind1st( ) or bind2nd( ) in this example.
+ because not1( ) returns the logical negation of the result of calling its unary
+ function argument. The first argument to equal_to is 20 because we used bind1st(
+ ) instead of bind2nd( ). Since testing for equality is symmetric in its
+ arguments, we could have used either bind1st( ) or bind2nd( ) in this example.
objects, along with the kinds of expressions to which they apply:
+ The following table shows the templates that generate the standard function
+ objects, along with the kinds of expressions to which they apply:
├───────────────┼────────────────┼────────────────────────────┤
│less_equal │BinaryPredicate │arg1 <= arg2 │
├───────────────┼────────────────┼────────────────────────────┤
- │logical_and │BinaryPredicate │arg1 && arg2 │
+ │logical_and │BinaryPredicate │arg1 && arg2 │
├───────────────┼────────────────┼────────────────────────────┤
│Logical_or │BinaryPredicate │arg1 || arg2 │
├───────────────┼────────────────┼────────────────────────────┤
expression from the last line of the earlier CountNotEqual.cpp program:
+ Standard function adaptors such as bind1st( ) and bind2nd( ) make some
+ assumptions about the function objects they process. Consider the following
+ expression from the last line of the earlier CountNotEqual.cpp program:
+ The bind1st( ) adaptor creates a unary function object of type binder1st, which
+ simply stores an instance of equal_to <int> and the value 20. The
+ binder1st::operator( ) function needs to know its argument type and its return
+ type; otherwise, it will not have a valid declaration. The convention to solve
+ this problem is to expect all function objects to provide nested type
+ definitions for these types. For unary functions, the type names are
+ argument_type and result_type; for binary function objects they are
+ first_argument_type, second_argument_type, and result_type. Looking at the
+ implementation of bind1st( ) and binder1st in the <functional> header reveals
+ these expectations. First inspect bind1st( ), as it might appear in a typical
+ library implementation:
the type names in Op in its declaration of its function call operator:
+ Note that the template parameter, Op, which represents the type of the binary
+ function being adapted by bind1st( ), must have a nested type named
+ first_argument_type. (Note also the use of typename to inform the compiler that
+ it is a member type name, as explained in Chapter 5.) Now see how binder1st uses
+ the type names in Op in its declaration of its function call operator:
+ Function objects whose classes provide these type names are called adaptable
adaptable. All we need to do is the following:
+ Since these names are expected of all standard function objects as well as of
+ any function objects you create to use with function object adaptors, the
+ unary_function and binary_function. You simply derive from these classes while
+ filling in the argument types as template parameters. Suppose, for example, that
+ we want to make the function object gt_n, defined earlier in this chapter,
+ adaptable. All we need to do is the following:
infers from its template parameters as you can see in its definition:
+ All unary_function does is to provide the appropriate type definitions, which it
+ infers from its template parameters as you can see in its definition:
unary_function. The binary_function template behaves in a similar manner.
+ These types become accessible through gt_n because it derives publicly from
+ unary_function. The binary_function template behaves in a similar manner.
following generators for convenience:
+ The following FunctionObjects.cpp example provides simple tests for most of the
+ built-in basic function object templates. This way, you can see how to use each
+ template, along with the resulting behavior. This example uses one of the
+ following generators for convenience:
random alphabetic character. Here is a sample program using UrandGen:
+ We’ll be using these generating functions in various examples throughout this
+ chapter. The SkipGen function object returns the next number of an arithmetic
+ sequence whose common difference is held in its skp data member. A URandGen
+ object generates a unique random number in a specified range. (It uses a set
+ container, which we’ll discuss in the next chapter.) A CharGen object returns a
+ random alphabetic character. Here is a sample program using UrandGen:
//: V2C06:FunctionObjects.cpp {-bor}
+ This example uses a handy function template, print( ), which is capable of
+ printing a sequence of any type along with an optional message. This template
+ appears in the header file PrintSequence.h, and is explained later in this
parameter, which in this case is the same as the input sequence.
+ The two template functions automate the process of testing the various function
+ object templates. There are two because the function objects are either unary or
+ binary. The testUnary( ) function takes a source vector, a destination vector,
+ and a unary function object to apply to the source vector to produce the
+ destination vector. In testBinary( ), two source vectors are fed to a binary
+ function to produce the destination vector. In both cases, the template
+ functions simply turn around and call the transform( ) algorithm, which applies
+ the unary function or function object found in its fourth parameter to each
+ sequence element, writing the result to the sequence indicated by its third
+ parameter, which in this case is the same as the input sequence.
the code of the expression that is executed followed by the result vector.
+ For each test, you want to see a string describing the test, followed by the
+ results of the test. To automate this, the preprocessor comes in handy; the T( )
+ and B( ) macros each take the expression you want to execute. After evaluating
+ the expression, they pass the appropriate range to print( ). To produce the
+ message the expression is “stringized” using the preprocessor. That way you see
+ the code of the expression that is executed followed by the result vector.
this should happen half the time.
+ The last little tool, BRand, is a generator object that creates random bool
+ values. To do this, it gets a random number from rand( ) and tests to see if
+ it’s greater than (RAND_MAX+1)/2. If the random numbers are evenly distributed,
+ this should happen half the time.
object for this is created with the expression:
- <!-- bind2nd(plus<int>(), 1) -->
+ In main( ), three vectors of int are created: x and y for source values, and r
+ for results. To initialize x and y with random values no greater than 50, a
+ generator of type URandGen from Generators.h is used. The standard generate_n( )
+ algorithm populates the sequence specified in its first argument by invoking its
+ third argument (which must be a generator) a given number of times (specified in
+ its second argument). Since there is one operation where elements of x are
+ divided by elements of y, we must ensure that there are no zero values of
+ y. This is accomplished by once again using the transform( ) algorithm, taking
+ the source values from y and putting the results back into y. The function
+ object for this is created with the expression:
+bind2nd(plus<int>(), 1)
This expression uses the plus function object to add 1 to its first argument. As
function so it can applied to the sequence by a single call to transform( ).
+ This expression uses the plus function object to add 1 to its first argument. As
+ we did earlier in this chapter, we use a binder adaptor to make this a unary
+ function so it can applied to the sequence by a single call to transform( ).
is equivalent; here element zero is chosen.
+ Another test in the program compares the elements in the two vectors for
+ equality, so it is interesting to guarantee that at least one pair of elements
+ is equivalent; here element zero is chosen.
is the output from an execution of FunctionObjects.cpp:
+ Once the two vectors are printed, T( ) tests each of the function objects that
+ produces a numeric value, and then B( ) tests each function object that produces
+ a Boolean result. The result is placed into a vector<bool>, and when this vector
+ is printed, it produces a ‘1’ for a true value and a ‘0’ for a false value. Here
+ is the output from an execution of FunctionObjects.cpp:
0, call cout.setf(ios::boolalpha).
+ If you want the Boolean values to display as “true” and “false” instead of 1 and
+ 0, call cout.setf(ios::boolalpha).
the transform( ) algorithm:
+ A binder doesn’t have to produce a unary predicate; it can also create any unary
+ function (that is, a function that returns something other than bool). For
+ example, you can to multiply every element in a vector by 10 using a binder with
+ the transform( ) algorithm:
bind2nd( ) in this case produces an int result.
+ Since the third argument to transform( ) is the same as the first, the resulting
+ elements are copied back into the source vector. The function object created by
+ bind2nd( ) in this case produces an int result.
have to be a compile-time constant. For example:
+ The “bound” argument to a binder cannot be a function object, but it does not
+ have to be a compile-time constant. For example:
//: V2C06:BinderValue.cpp
the sequence. Here is the output from one run:
+ Here, an array is filled with 20 random numbers between 0 and 100, and the user
+ provides a value on the command line. In the remove_copy_if( ) call, you can
+ see that the bound argument to bind2nd( ) is random number in the same range as
+ the sequence. Here is the output from one run:
4 12 15 17 19 21 26 30 47 48 56 58 60 63 71 79 82 90 92 95
functions returning random numbers to generate( ) and generate_n( ).
+ Wherever a function-like entity is expected by an algorithm, you can supply
+ either a pointer to an ordinary function or a function object. When the
+ algorithm issues a call, if it is through a function pointer, than the native
+ function-call mechanism is used. If it is through a function object, then that
+ object’s operator( ) member executes. In CopyInts2.cpp, we passed the raw
+ function gt15( ) as a predicate to remove_copy_if( ). We also passed pointers to
+ functions returning random numbers to generate( ) and generate_n( ).
arguments—they must only be used with unary functions or binary functions.
- <!-- The following program uses ptr_fun( ) to wrap a unary function: -->
+ You cannot use raw functions with function object adaptors such as bind2nd( )
+ because they assume the existence of type definitions for the argument and
+ result types. Instead of manually converting your native functions into function
+ objects yourself, the standard library provides a family of adaptors to do the
+ work for you. The ptr_fun( ) adaptors take a pointer to a function and turn it
+ into a function object. They are not designed for a function that takes no
+ arguments—they must only be used with unary functions or binary functions.
+The following program uses ptr_fun( ) to wrap a unary function:
+The following program uses ptr_fun( ) to wrap a unary function:
version of ptr_fun( ) looks something like this:
- template<class Arg, class Result>
- pointer_to_unary_function<Arg, Result>
- ptr_fun(Result (*fptr)(Arg)) {
- return pointer_to_unary_function<Arg, Result>(fptr);
+ We can’t simply pass isEven to not1, because not1 needs to know the actual
+ argument type and return type its argument uses. The ptr_fun( ) adaptor deduces
+ those types through template argument deduction. The definition of the unary
+ version of ptr_fun( ) looks something like this:
+template<class Arg, class Result>
+pointer_to_unary_function<Arg, Result>
+ptr_fun(Result (*fptr)(Arg)) {
+ return pointer_to_unary_function<Arg, Result>(fptr);
As you can see, this version of ptr_fun( ) deduces the argument and result types
fptr, as you can see by the last line of its code:
+ As you can see, this version of ptr_fun( ) deduces the argument and result types
+ from fptr and uses them to initialize a pointer_to_unary_function object that
+ stores fptr. The function call operator for pointer_to_unary_function just calls
+ fptr, as you can see by the last line of its code:
template<class Arg, class Result>
-class pointer_to_unary_function
-: public unary_function<Arg, Result> {
+class pointer_to_unary_function : public unary_function<Arg, Result> {
Result (*fptr)(Arg); // Stores the f-ptr
pointer_to_unary_function(Result (*x)(Arg)) : fptr(x) {}
type definitions come along for the ride and are available to not1.
+ Since pointer_to_unary_function derives from unary_function, the appropriate
+ type definitions come along for the ride and are available to not1.
reveals a pitfall when passing overloaded functions to ptr_fun ( ).
+ There is also a binary version of ptr_fun( ), which returns a
+ pointer_to_binary_function object (which derives from binary_function) that
+ behaves analogously to the unary case. The following program uses the binary
+ version of ptr_fun ( ) to raise numbers in a sequence to a power. It also
+ reveals a pitfall when passing overloaded functions to ptr_fun ( ).
//: V2C06:PtrFun2.cpp {-edg}
- The pow( ) function is overloaded in the Standard C++ header <cmath> for each of
+ The pow( ) function is overloaded in the Standard C++ header <cmath> for each of
the floating-point data types, as follows:
+ The pow( ) function is overloaded in the Standard C++ header <cmath> for each of
+ the floating-point data types, as follows:
float pow(float, int); // Efficient int power versions ...
long double pow(long double, int);
double pow(double, double);
long double pow(long double, long double);
Since there are multiple versions of pow( ), the compiler has no way of knowing
template specialization, as explained in the previous chapter.[91]
+ Since there are multiple versions of pow( ), the compiler has no way of knowing
+ which to choose. Here, we have to help the compiler by using explicit function
+ template specialization, as explained in the previous chapter.[91]
pointer in a container of Shape:
+ It’s even trickier to convert a member function into a function object suitable
+ for using with the generic algorithms. As a simple example, suppose we have the
+ classical “shape” problem and want to apply the draw( ) member function to each
+ pointer in a container of Shape:
+ The for_each( ) algorithm passes each element in a sequence to the function
+ object denoted by its third argument. Here, we want the function object to wrap
+ one of the member functions of the class itself, and so the function object’s
+ “argument” becomes the pointer to the object for the member function call. To
+ produce such a function object, the mem_fun( ) template takes a pointer to a
+ member as its argument.
+ The mem_fun( ) functions are for producing function objects that are called
+ using a pointer to the object that the member function is called for, while
+ mem_fun_ref( ) calls the member function directly for an object. One set of
+ overloads of both mem_fun( ) and mem_fun_ref( ) is for member functions that
+ take zero arguments and one argument, and this is multiplied by two to handle
+ const vs. non-const member functions. However, templates and overloading take
+ care of sorting all that out—all you need to remember is when to use mem_fun( )
form of the transform( ) algorithm:
+ Suppose you have a container of objects (not pointers), and you want to call a
+ member function that takes an argument. The argument you pass should come from
+ a second container of objects. To accomplish this, use the second overloaded
+ form of the transform( ) algorithm:
takes an argument using transform( ) or for_each( ).
+ Because the container is holding objects, mem_fun_ref( ) must be used with the
+ pointer-to-member function. This version of transform( ) takes the start and end
+ point of the first range (where the objects live); the starting point of the
+ second range, which holds the arguments to the member function; the destination
+ iterator, which in this case is standard output; and the function object to call
+ for each object. This function object is created with mem_fun_ref( ) and the
+ desired pointer to member. Notice that the transform( ) and for_each( ) template
+ functions are incomplete; transform( ) requires that the function it calls
+ return a value, and there is no for_each( ) that passes two arguments to the
+ function it calls. Thus, you cannot call a member function that returns void and
+ takes an argument using transform( ) or for_each( ).
you to use the string::empty( ) member function like this:
+ Most any member function works with mem_fun_ref( ). You can also use standard
+ library member functions, if your compiler doesn’t add any default arguments
+ beyond the normal arguments specified in the standard.[92] For example, suppose
+ you’d like to read a file and search for blank lines. Your compiler may allow
+ you to use the string::empty( ) member function like this:
select the current string.
+ This example uses find_if( ) to locate the first blank line in the given range
+ using mem_fun_ref( ) with string::empty ( ). After the file is opened and read
+ into the vector, the process is repeated to find every blank line in the file.
+ Each time a blank line is found, it is replaced with the characters “A BLANK
+ LINE.” All you have to do to accomplish this is dereference the iterator to
+ select the current string.
here’s a generator that creates the strings:
+ Consider how to write a program that converts strings representing
+ floating-point numbers to their actual numeric values. To get things started,
+ here’s a generator that creates the strings:
+ You tell it how big the strings should be when you create the NumStringGen
+ object. The random number generator selects digits, and a decimal point is
convert all the strings to char*, and then these can be transformed using atof.
+ The following program uses NumStringGen to fill a vector<string>. However, to
+ use the standard C library function atof ( ) to convert the strings to
+ floating-point numbers, the string objects must first be turned into char
+ pointers, since there is no automatic type conversion from string to char*. The
+ transform( ) algorithm can be used with mem_fun_ref( ) and string::c_str( ) to
+ convert all the strings to char*, and then these can be transformed using atof.
we can compose functions in mathematics, so why not C++?
+ This program does two transformations: one to convert strings to C-style strings
+ (arrays of characters), and one to convert the C-style strings to numbers via
+ atof( ). It would be nice to combine these two operations into one. After all,
+ we can compose functions in mathematics, so why not C++?
+ The obvious approach takes the two functions as arguments and applies them in
+ The unary_composer object in this example stores the function pointers atof and
+ string::c_str such that the latter function is applied first when its operator(
+ ) is called. The compose( ) function adaptor is a convenience, so we don’t need
+ to supply all four template arguments explicitly—F1 and F2 are deduced from the
+ It would be much better if we didn’t need to supply any template arguments. This
+ is achieved by adhering to the convention for type definitions for adaptable
+ function objects. In other words, we will assume that the functions to be
+ composed are adaptable. This requires that we use ptr_fun( ) for atof( ). For
+ maximum flexibility, we also make unary_composer adaptable in case it gets
+ passed to a function adaptor. The following program does so and easily solves
//: V2C06:ComposeFinal.cpp {-edg}
referring to is a nested type.
+ Once again we must use typename to let the compiler know that the member we are
+ referring to is a nested type.
to the next version of Standard C++.
+ Some implementations[93] support composition of function objects as an
+ extension, and the C++ Standards Committee is likely to add these capabilities
+ to the next version of Standard C++.
look into the more specialized references if you need more detail.
+ This section provides a quick reference when you’re searching for the
+ appropriate algorithm. We leave the full exploration of all the STL algorithms
+ to other references (see the end of this chapter, and Appendix A), along with
+ the more intimate details of issues like performance. Our goal here is for you
+ to rapidly become comfortable with the algorithms, and we’ll assume you will
+ look into the more specialized references if you need more detail.
+ Although you will often see the algorithms described using their full template
+ declaration syntax, we’re not doing that here because you already know they are
+ templates, and it’s quite easy to see what the template arguments are from the
+ function declarations. The type names for the arguments provide descriptions for
+ the types of iterators required. We think you’ll find this form is easier to
+ read, and you can quickly find the full declaration in the template header file
by the types of iteration facilities they require.
+ The reason for all the fuss about iterators is to accommodate any type of
+ container that meets the requirements in the standard library. So far we have
+ illustrated the generic algorithms with only arrays and vectors as sequences,
+ but in the next chapter you’ll see a broad range of data structures that support
+ less robust iteration. For this reason, the algorithms are categorized in part
+ by the types of iteration facilities they require.
+ The names of the iterator classes describe the iterator type to which they must
+ conform. There are no interface base classes to enforce these iteration
+ operations—they are just expected to be there. If they are not, your compiler
+ will complain. The various flavors of iterators are described briefly as
be tested with operator== and operator!=. That’s the extent of the constraints.
+ InputIterator. An input iterator only allows reading elements of its sequence in
+ a single, forward pass using operator++ and operator*. Input iterators can also
+ be tested with operator== and operator!=. That’s the extent of the constraints.
+ OutputIterator. An output iterator only allows writing elements to a sequence in
+ a single, forward pass using operator++ and operator*. OutputIterators cannot be
+ tested with operator== and operator!=, however, because you assume that you can
+ just keep sending elements to the destination and that you don’t need to see if
+ the destination’s end marker was reached. That is, the container that an
+ OutputIterator references can take an infinite number of objects, so no
+ end-checking is necessary. This requirement is important so that an
+ OutputIterator can be used with ostreams (via ostream_iterator), but you’ll also
+ commonly use the “insert” iterators such as are the type of iterator returned by
OutputIterator used as STL algorithm template arguments.
+ There is no way to determine whether multiple InputIterators or OutputIterators
+ point within the same range, so there is no way to use such iterators
+ together. Just think in terms of iterators to support istreams and ostreams, and
+ InputIterator and OutputIterator will make perfect sense. Also note that
+ algorithms that use InputIterators or OutputIterators put the weakest
+ restrictions on the types of iterators they will accept, which means that you
+ can use any “more sophisticated” type of iterator when you see InputIterator or
+ OutputIterator used as STL algorithm template arguments.
and write, they can be used in place of an InputIterator or OutputIterator.
+ ForwardIterator. Because you can only read from an InputIterator and write to an
+ OutputIterator, you can’t use either of them to simultaneously read and modify a
+ range, and you can’t dereference such an iterator more than once. With a
+ ForwardIterator these restrictions are relaxed; you can still only move forward
+ using operator++, but you can both write and read, and you can compare such
+ iterators in the same range for equality. Since forward iterators can both read
+ and write, they can be used in place of an InputIterator or OutputIterator.
ForwardIterator does, but in addition it has an operator - -.
+ BidirectionalIterator. Effectively, this is a ForwardIterator that can also go
+ backward. That is, a BidirectionalIterator supports all the operations that a
+ ForwardIterator does, but in addition it has an operator - -.
access iterators are necessary to be able to create an efficient algorithm.
+ RandomAccessIterator. This type of iterator supports all the operations that a
+ regular pointer does: you can add and subtract integral values to move it
+ forward and backward by jumps (rather than just one element at a time), you can
+ subscript it with operator[ ], you can subtract one iterator from another, and
+ you can compare iterators to see which is greater using operator<, operator>,
+ and so on. If you’re implementing a sorting routine or something similar, random
+ access iterators are necessary to be able to create an efficient algorithm.
include other arguments, often function objects.
+ The names used for the template parameter types in the algorithm descriptions
+ later in this chapter consist of the listed iterator types (sometimes with a ‘1’
+ or ‘2’ appended to distinguish different template arguments) and can also
+ include other arguments, often function objects.
pointing to the initial element, and last is the past-the-end iterator.
+ When describing the group of elements passed to an operation, mathematical
+ “range” notation is often used. In this, the square bracket means “includes the
+ end point,” and the parenthesis means “does not include the end point.” When
+ using iterators, a range is determined by the iterator pointing to the initial
+ element and by the “past-the-end” iterator, pointing past the last
+ element. Since the past-the-end element is never used, the range determined by a
+ pair of iterators can be expressed as [first, last), where first is the iterator
+ pointing to the initial element, and last is the past-the-end iterator.
and so on? This should help you find the algorithm you want more easily.
+ Most books and discussions of the STL algorithms arrange them according to
+ side-effects: non-mutating algorithms don’t change the elements in the range,
+ mutating algorithms do change the elements, and so on. These descriptions are
+ based primarily on the underlying behavior or implementation of the
+ algorithm—that is, on the designer’s perspective. In practice, we don’t find
+ this a useful categorization, so instead we’ll organize them according to the
+ problem you want to solve: Are you searching for an element or set of elements,
+ performing an operation on each element, counting elements, replacing elements,
+ and so on? This should help you find the algorithm you want more easily.
+ If you do not see a different header such as <utility> or <numeric> above the
+ function declarations, it appears in <algorithm>. Also, all the algorithms are
+ It’s useful to create some basic tools to test the algorithms. In the examples
+ that follow we’ll use the generators mentioned earlier in Generators.h, as well
any sequence, regardless of the type contained in that sequence:
+ Displaying a range is a frequent task, so here is a function template to print
+ any sequence, regardless of the type contained in that sequence:
//: V2C06:PrintSequence.h
member of the iterator passed.
+ By default this function template prints to cout with newlines as separators,
+ but you can change that by modifying the default argument. You can also provide
+ a message to print at the head of the output. Since print( ) uses the copy( )
+ algorithm to send objects to cout via an ostream_iterator, the ostream_iterator
+ must know the type of object it is printing, which we infer from the value_type
+ member of the iterator passed.
the following partial specialization for pointer types:
+ The std::iterator_traits template enables the print( ) function template to
+ process sequences delimited by any type of iterator. The iterator types returned
+ by the standard containers such as vector define a nested type, value_type,
+ which represents the element type, but when using arrays, the iterators are just
+ pointers, which can have no nested types. To supply the conventional types
+ associated with iterators in the standard library, std::iterator_traits provides
+ the following partial specialization for pointer types:
+ This makes the type of the elements pointed at (namely, T) available via the
stable_sort( ) is also provided.[94]
+ A number of the STL algorithms that move elements of a sequence around
+ distinguish between stable and unstable reordering of a sequence. A stable sort
+ preserves the original relative order of the elements that are equivalent as far
+ as the comparison function is concerned. For example, consider a sequence {
+ c(1), b(1), c(2), a(1), b(2), a(2) }. These elements are tested for equivalence
+ based on their letters, but their numbers indicate how they first appeared in
+ the sequence. If you sort (for example) this sequence using an unstable sort,
+ there’s no guarantee of any particular order among equivalent letters, so you
+ could end up with { a(2), a(1), b(1), b(2), c(2), c(1) }. However, if you use a
+ stable sort, you will get { a(1), a(2), b(1), b(2), c(1), c(2) }. The STL sort(
+ ) algorithm uses a variation of quicksort and is thus unstable, but a
+ stable_sort( ) is also provided.[94]
indicates the order in which this NString was discovered.
+ To demonstrate the stability versus instability of algorithms that reorder a
+ sequence, we need some way to keep track of how the elements originally
+ appeared. The following is a kind of string object that keeps track of the order
+ in which that particular object originally appeared, using a static map that
+ maps NStrings to Counters. Each NString then contains an occurrence field that
+ indicates the order in which this NString was discovered.
pairs instead. You’ll see plenty of similar examples in Chapter 7.
+ We would normally use a map container to associate a string with its number of
+ occurrences, but maps don’t appear until the next chapter, so we use a vector of
+ pairs instead. You’ll see plenty of similar examples in Chapter 7.
provided so that the greater template can call it.
+ The only operator necessary to perform an ordinary ascending sort is
+ NString::operator<( ). To sort in reverse order, the operator>( ) is also
+ provided so that the greater template can call it.
- void fill(ForwardIterator first, ForwardIterator last,
- void fill_n(OutputIterator first, Size n, const T& value);
+ These algorithms let you automatically fill a range with a particular value or
+ generate a set of values for a particular range. The “fill” functions insert a
+ single value multiple times into the container. The “generate” functions use
+ generators such as those described earlier to produce values to insert into the
+ void fill(ForwardIterator first, ForwardIterator last, const T& value);
+ void fill_n(OutputIterator first, Size n, const T& value);
fill( ) assigns value to every element in the range [first, last). fill_n( )
assigns value to n elements starting at first.
- void generate(ForwardIterator first, ForwardIterator last,
- void generate_n(OutputIterator first, Size n, Generator
+ fill( ) assigns value to every element in the range [first, last). fill_n( )
+ assigns value to n elements starting at first.
+ void generate(ForwardIterator first, ForwardIterator last, Generator gen);
+ void generate_n(OutputIterator first, Size n, Generator gen);
generate( ) makes a call to gen( ) for each element in the range [first, last),
gen( ) n times and assigns each result to n elements starting at first.
+ generate( ) makes a call to gen( ) for each element in the range [first, last),
+ presumably to produce a different value for each element. generate_n( ) calls
+ gen( ) n times and assigns each result to n elements starting at first.
+ The following example fills and generates into vectors. It also shows the use of
//: V2C06:FillGenerateTest.cpp
vector. Also, the default newline separator is replaced with a space.
+ A vector<string> is created with a predefined size. Since storage has already
+ been created for all the string objects in the vector, fill( ) can use its
+ assignment operator to assign a copy of “howdy” to each space in the
+ vector. Also, the default newline separator is replaced with a space.
+ The second vector<string> v2 is not given an initial size, so back_inserter(
+ ) must be used to force new elements in instead of trying to assign to existing
both generators are demonstrated.
+ The generate( ) and generate_n( ) functions have the same form as the “fill”
+ functions except that they use a generator instead of a constant value. Here,
+ both generators are demonstrated.
- <!-- IntegralValue count(InputIterator first, InputIterator last, const EqualityComparable& value); -->
+ All containers have a member function size( ) that tells you how many elements
+ they hold. The return type of size( ) is the iterator’s
+ difference_type[95] (usually ptrdiff_t), which we denote by IntegralValue in the
+ following. The following two algorithms count objects that satisfy certain
+IntegralValue count(InputIterator first, InputIterator last, const EqualityComparable&
Produces the number of elements in [first, last) that are equivalent to value
(when tested using operator==).
- <!-- IntegralValue count_if(InputIterator first, InputIterator last, Predicate pred); -->
+ Produces the number of elements in [first, last) that are equivalent to value
+ (when tested using operator==).
+IntegralValue count_if(InputIterator first, InputIterator last, Predicate pred);
Produces the number of elements in [first, last) that each cause pred to return
+ Produces the number of elements in [first, last) that each cause pred to return
characters, which are then displayed:
+ Here, a vector<char> v is filled with random characters (including some
+ duplicates). A set<char> is initialized from v , so it holds only one of each
+ letter represented in v. This set counts all the instances of all the
+ characters, which are then displayed:
+ The count_if( ) algorithm is demonstrated by counting all the lowercase letters;
+ the predicate is created using the bind2nd( ) and greater function object
<!-- Manipulating sequences -->
<title>Manipulación de secuencias</title>
- <!-- These algorithms let you move sequences around. -->
- <!-- OutputIterator copy(InputIterator first, InputIterator last, OutputIterator destination); -->
+ These algorithms let you move sequences around.
+ These algorithms let you move sequences around.
+OutputIterator copy(InputIterator first, InputIterator last, OutputIterator destination);
Using assignment, copies from [first, last) to destination, incrementing
) in the case of an associative container).
- <!-- BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 destinationEnd); -->
+ Using assignment, copies from [first, last) to destination, incrementing
+ destination after each assignment. This is essentially a “shuffle-left”
+ operation, and so the source sequence must not contain the destination. Because
+ assignment is used, you cannot directly insert elements into an empty container
+ or at the end of a container, but instead you must wrap the destination iterator
+ in an insert_iterator (typically by using back_inserter( ) or by using inserter(
+ ) in the case of an associative container).
+BidirectionalIterator2 copy_backward(
+ BidirectionalIterator1 first, BidirectionalIterator1 last,
+ BidirectionalIterator2 destinationEnd);
Like copy( ), but copies the elements in reverse order. This is essentially a
be within the source range.
- void reverse(BidirectionalIterator first, BidirectionalIterator last);
- OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator destination);
+ Like copy( ), but copies the elements in reverse order. This is essentially a
+ “shuffle-right” operation, and, like copy( ), the source sequence must not
+ contain the destination. The source range [first, last) is copied to the
+ destination, but the first destination element is destinationEnd - 1. This
+ iterator is then decremented after each assignment. The space in the destination
+ range must already exist (to allow assignment), and the destination range cannot
+ be within the source range.
+void reverse(BidirectionalIterator first, BidirectionalIterator last);
+OutputIterator reverse_copy(
+ BidirectionalIterator first, BidirectionalIterator last,
+ OutputIterator destination);
Both forms of this function reverse the range [first, last). reverse( ) reverses
iterator of the resulting range.
- <!-- ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); -->
+ Both forms of this function reverse the range [first, last). reverse( ) reverses
+ the range in place, and reverse_copy ( ) leaves the original range alone and
+ copies the reversed elements into destination, returning the past-the-end
+ iterator of the resulting range.
+ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
+ForwardIterator2 first2);
Exchanges the contents of two ranges of equal size by swapping corresponding
- void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
- OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator destination);
+ Exchanges the contents of two ranges of equal size by swapping corresponding
+void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
+OutputIterator rotate_copy(
+ ForwardIterator first, ForwardIterator middle, ForwardIterator last,
+ OutputIterator destination);
Moves the contents of [first, middle) to the end of the sequence, and the
the two ranges be exactly the same size, the “rotate” functions do not.
+ Moves the contents of [first, middle) to the end of the sequence, and the
+ contents of [middle, last) to the beginning. With rotate( ), the swap is
+ performed in place; and with rotate_copy( ) the original range is untouched, and
+ the rotated version is copied into destination, returning the past-the-end
+ iterator of the resulting range. Note that while swap_ranges( ) requires that
+ the two ranges be exactly the same size, the “rotate” functions do not.
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last,
-StrictWeakOrdering binary_pred);
+ StrictWeakOrdering binary_pred);
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last,
-StrictWeakOrdering binary_pred);
+ StrictWeakOrdering binary_pred);
the sequence of permutations.
+ A permutation is one unique ordering of a set of elements. If you have n unique
+ elements, there are n! (n factorial) distinct possible combinations of those
+ elements. All these combinations can be conceptually sorted into a sequence
+ using a lexicographical (dictionary-like) ordering and thus produce a concept of
+ a “next” and “previous” permutation. So whatever the current ordering of
+ elements in the range, there is a distinct “next” and “previous” permutation in
+ the sequence of permutations.
+ The next_permutation( ) and prev_permutation( ) functions rearrange the elements
+ into their next or previous permutation and, if successful, return true. If
+ there are no more “next” permutations, the elements are in sorted order so
+ next_permutation( ) returns false. If there are no more “previous” permutations,
+ the elements are in descending sorted order so previous_permutation( ) returns
the comparisons using binary_pred instead of operator<.
- void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
- void random_shuffle(RandomAccessIterator first, RandomAccessIterator last RandomNumberGenerator& rand);
+ The versions of the functions that have a StrictWeakOrdering argument perform
+ the comparisons using binary_pred instead of operator<.
+void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
+void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
+ RandomNumberGenerator& rand);
This function randomly rearranges the elements in the range. It yields uniformly
- BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
- BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
+ This function randomly rearranges the elements in the range. It yields uniformly
+ distributed results if the random-number generator does. The first form uses an
+ internal random number generator, and the second uses a user-supplied
+ random-number generator. The generator must return a value in the range [0, n)
+BidirectionalIterator partition(
+ BidirectionalIterator first, BidirectionalIterator last,
+BidirectionalIterator stable_partition(
+ BidirectionalIterator first, BidirectionalIterator last,
The “partition” functions move elements that satisfy pred to the beginning of
+ The “partition” functions move elements that satisfy pred to the beginning of
+ the sequence. An iterator pointing one past the last of those elements is
+ returned (which is, in effect, an “end” iterator” for the initial subsequence of
+ elements that satisfy pred). This location is often called the “partition
before the partitioning process.
+ With partition( ), the order of the elements in each resulting subsequence after
+ the function call is not specified, but with stable_partition( ), the relative
+ order of the elements before and after the partition point will be the same as
+ before the partitioning process.
- <!-- This gives a basic demonstration of sequence manipulation: -->
+ This gives a basic demonstration of sequence manipulation:
+ This gives a basic demonstration of sequence manipulation:
//: V2C06:Manipulations.cpp
want to redirect the output to a file.)
+ The best way to see the results of this program is to run it. (You’ll probably
+ want to redirect the output to a file.)
- The vector<int> v1 is initially loaded with a simple ascending sequence and
+ The vector<int> v1 is initially loaded with a simple ascending sequence and
printed. You’ll see that the effect of copy_backward( ) (which copies into v2,
which is the same size as v1) is the same as an ordinary copy. Again,
copy_backward( ) does the same thing as copy( )—it just performs the operations
+ The vector<int> v1 is initially loaded with a simple ascending sequence and
+ printed. You’ll see that the effect of copy_backward( ) (which copies into v2,
+ which is the same size as v1) is the same as an ordinary copy. Again,
+ copy_backward( ) does the same thing as copy( )—it just performs the operations
the entire vector, as long as they are of equivalent size.
+ reverse_copy( ) actually does create a reversed copy, and reverse( ) performs
+ the reversal in place. Next, swap_ranges ( ) swaps the upper half of the
+ reversed sequence with the lower half. The ranges could be smaller subsets of
+ the entire vector, as long as they are of equivalent size.
with arrays of char as easily as with anything else.
+ After re-creating the ascending sequence, rotate( ) is demonstrated by rotating
+ one third of v1 multiple times. A second rotate( ) example uses characters and
+ just rotates two characters at a time. This also demonstrates the flexibility of
+ both the STL algorithms and the print( ) template, since they can both be used
+ with arrays of char as easily as with anything else.
strictly defined order (that is, permuting is a deterministic process).
+ To demonstrate next_permutation( ) and prev_permutation( ), a set of four
+ characters “abcd” is permuted through all n! (n factorial) possible
+ combinations. You’ll see from the output that the permutations move through a
+ strictly defined order (that is, permuting is a deterministic process).
+ A quick-and-dirty demonstration of random_shuffle( ) is to apply it to a string
+ and see what words result. Because a string object has begin( ) and end( )
+ member functions that return the appropriate iterators, it too can be easily
+ used with many of the STL algorithms. An array of char could also have been
char arrays, but NString has a char* constructor that is automatically used.
+ Finally, the partition( ) and stable_partition( ) are demonstrated, using an
+ array of NString. You’ll note that the aggregate initialization expression uses
+ char arrays, but NString has a char* constructor that is automatically used.
whereas with the stable partition, their original order is maintained.
+ You’ll see from the output that with the unstable partition, the objects are
+ correctly above and below the partition point, but in no particular order;
+ whereas with the stable partition, their original order is maintained.
range defined by the first two iterator arguments.
- <!-- InputIterator find(InputIterator first, InputIterator last, const EqualityComparable& value); -->
+ All these algorithms are used for searching for one or more objects within a
+ range defined by the first two iterator arguments.
+InputIterator find(InputIterator first, InputIterator last, const EqualityComparable& value);
Searches for value within a range of elements. Returns an iterator in the range
- <!-- InputIterator find_if(InputIterator first, InputIterator last, Predicate pred); -->
+ Searches for value within a range of elements. Returns an iterator in the range
+ [first, last) that points to the first occurrence of value. If value isn’t in
+ the range, find( ) returns last. This is a linear search; that is, it starts at
+ the beginning and looks at each sequential element without making any
+ assumptions about the way the elements are ordered. In contrast, a
+ binary_search( ) (defined later) works on a sorted sequence and can thus be much
+InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
Just like find( ), find_if( ) performs a linear search through the
last if no such element can be found.
- ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
- ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
+ Just like find( ), find_if( ) performs a linear search through the
+ range. However, instead of searching for value, find_if( ) looks for an element
+ such that the Predicate pred returns true when applied to that element. Returns
+ last if no such element can be found.
+ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
+ForwardIterator adjacent_find(
+ ForwardIterator first, ForwardIterator last,
+ BinaryPredicate binary_pred);
Like find( ), performs a linear search through the range, but instead of looking
- ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
- ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
+ Like find( ), performs a linear search through the range, but instead of looking
+ for only one element, it searches for two adjacent elements that are
+ equivalent. The first form of the function looks for two elements that are
+ equivalent (via operator==). The second form looks for two adjacent elements
+ that, when passed together to binary_pred, produce a true result. An iterator to
+ the first of the two elements is returned if a pair is found; otherwise, last is
+ForwardIterator1 find_first_of(
+ ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,
+ ForwardIterator2 last2);
+ForwardIterator1 find_first_of(
+ ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,
+ ForwardIterator2 last2, BinaryPredicate binary_pred);
Like find( ), performs a linear search through the range. Both forms search for
- ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
- ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 BinaryPredicate binary_pred);
+ Like find( ), performs a linear search through the range. Both forms search for
+ an element in the second range that’s equivalent to one in the first, the first
+ form using operator==, and the second using the supplied predicate. In the
+ second form, the current element from the first range becomes the first argument
+ to binary_pred, and the element from the second range becomes the second
+ForwardIterator1 search(
+ ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,
+ ForwardIterator2 last2);
+ForwardIterator1 search(
+ ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,
+ ForwardIterator2 last2 BinaryPredicate binary_pred);
Checks to see if the second range occurs (in the exact order of the second
- ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
- ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
+ Checks to see if the second range occurs (in the exact order of the second
+ range) within the first range, and if so returns an iterator pointing to the
+ place in the first range where the second range begins. Returns last1 if no
+ subset can be found. The first form performs its test using operator==, and the
+ second checks to see if each pair of objects being compared causes binary_pred
+ForwardIterator1 find_end(
+ ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,
+ ForwardIterator2 last2);
+ForwardIterator1 find_end(
+ ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,
+ ForwardIterator2 last2, BinaryPredicate binary_pred);
The forms and arguments are just like search( ) in that they look for the second
and returns an iterator to its first element.
- ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
- ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate binary_pred);
+ The forms and arguments are just like search( ) in that they look for the second
+ range appearing as a subset of the first range, but while search( ) looks for
+ the first occurrence of the subset, find_end( ) looks for the last occurrence
+ and returns an iterator to its first element.
+ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
+ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate binary_pred);
Looks for a group of count consecutive values in [first, last) that are all
such a group cannot be found.
- ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
- ForwardIterator min_element(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);