(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.