Chapter 17: The Standard Template Library, generic algorithms

We're always interested in getting feedback. E-mail us if you like this guide, if you think that important material is omitted, if you encounter errors in the code examples or in the documentation, if you find any typos, or generally just if you feel like e-mailing. Send your email to Frank Brokken.

Please state the document version you're referring to, as found in the title (in this document: 5.1.0d) and please state the paragraph you're referring to.

All mail received is seriously considered, and new (sub)releases of the Annotations will normally reflect your suggestions for improvements. Except for the incidental case I will not otherwise acknowledge the receipt of suggestions for improvements. Please don't misinterpret this for lack of appreciation.

The Standard Template Library ( STL) consists of containers, generic algorithms, iterators, function objects, allocators and adaptors. The STL is a general purpose library consisting of algorithms and data structures. The data structures that are used in the algorithms are abstract in the sense that the algorithms can be used on (practically) every data type.

The algorithms can work on these abstract data types due to the fact that they are template based algorithms. In this chapter the construction of these templates in not further discussed (see chapter 18 for that). Rather, the use of these template algorithms is the focus of this chapter.

Several parts of the standard template library have already been discussed in the C++ Annotations. In chapter 12 the abstract containers were discussed, and in section 9.9 function objects were introduced. Also, iterators were mentioned at several places in this document.

The remaining components of the STL will be covered in this chapter. Iterators, adaptors and generic algorithms will be discussed in the coming sections. Allocators take care of the memory allocation within the STL. The default allocator class suffices for most applications, and are not further discussed in the C++ Annotations.

Forgetting to delete allocated memory is a common source of errors or memory leaks in a program. The auto_ptr template class may be used to prevent these types of problems. The auto_ptr class is discussed in section 17.3 in this chapter.

17.1: Predefined function objects

Function objects play important roles in combination with generic algorithms. For example, there exists a generic algorithm sort() that takes two iterators defining the range of objects that should be sorted, and a function object calling the appropriate comparison operator for two objects. Let's take a quick look at this situation. Assume strings are stored in a vector, and we want to sort the vector in descending order. In that case, sorting the vector stringVec is as simple as:
        sort(stringVec.begin(), stringVec.end(), greater<string>());
The last argument is recognized as a constructor: it is an instantiation of the greater<>() template class, applied to strings. This object is called as a function object by the sort() generic algorithm. The operator()() ( function call operator) itself is not visible at this point: don't confuse the parentheses in greater<string>() with the calling of its operator()(). When that operator is actually used by sort(), it receives two arguments: two strings to compare for `greaterness'. Internally, the operator>() of the underlying datatype (i.e., string) is called by greater<string>::operator()() to compare the two objects. Since the function call operator of greater<> is defined inline, the call itself is not actually present in the code. Rather, sort() calls string::operator>(), thinking it called greater<>::operator()().

Now that we know that a constructor is passed as argument to (many) generic algorithms, we can design our own function objects. Assume we want to sort our vector case-insensitively. How do we proceed? First we note that the default string::operator<() (for an incremental sort) is not appropriate, as it does case sensitive comparisons. So, we provide our own case_less class, in which the two strings are compared case insensitively. Using the standard C function strcasecmp(), the following program performs the trick. It sorts its command-line arguments in ascending alphabetical order:

    #include <iostream>
    #include <string>
    #include <functional>
    #include <algorithm>
    
    class case_less
    {
        public:
            bool operator()(string const &left, string const &right) const
            {
                return strcasecmp(left.c_str(), right.c_str()) < 0;
            }
    };
    
    int main(int argc, char **argv)
    {
        sort(argv, argv + argc, case_less());
        for (int idx = 0; idx < argc; ++idx)
            cout << argv[idx] << " ";
        cout << endl;
    }
The default constructor of the class case_less is used with the final argument of sort(). Therefore, the only member function that must be defined with the class case_less is the function object operator operator()(). Since we know it's called with string arguments, we define it to expect two string arguments, which are used in the strcasecmp() function. Furthermore, the operator()() function is made inline, so that it does not produce overhead in the sort() function. The sort() function calls the function object with various combinations of strings, i.e., it thinks it does so. However, in fact it calls strcasecmp(), due to the inline-nature of case_less::operator()().

The comparison function object is often a predefined function object, since these are available for most of the common operations. In the following sections the available predefined function objects are presented, together with some examples showing their use. At the end of the section about function objects function adaptors are introduced. In order to use predefined function objects and function adapters, sources must

    #include <functional>
Predefined function objects are used predominantly with generic algorithms. Predefined function objects exists for arithmetic, relational, and logical operations. In section 19.5 predefined function objects are developed performing bitwise operations.

17.1.1: Arithmetic Function Objects

The arithmetic function objects support the standard arithmetic operations: addition, subtraction, multiplication, division, modulus and negation. By using predefined arithmetic function objects, the corresponding operator of the associated data type is invoked. For example, for addition the function object plus<Type> is available. If we set type to unsigned then the + operator for unsigned values is used, if we set type to string, then the + operator for strings is used. For example:
    #include <iostream>
    #include <string>
    #include <functional>
    
    int main(int argc, char **argv)
    {
        plus<unsigned>
            uAdd;       // function object to add unsigneds
    
        cout << "3 + 5 = " << uAdd(3, 5) << endl;
    
        plus<string>
            sAdd;       // function object to add strings
    
        cout << "argv[0] + argv[1] = " << sAdd(argv[0], argv[1]) << endl;
    }
    /*
        generated output with call: a.out going

    3 + 5 = 8
    argv[0] + argv[1] = a.outgoing
    */
Why is this useful? Note that the function object can be used for all kinds of data types, not only on the predefined datatypes, in which the particular operator has been overloaded. Assume that we want to perform an operation on a common variable on the one hand and, on the other hand, on each element of an array in turn. E.g., we want to compute the sum of the elements of an array; or we want to concatenate all the strings in a text-array. In situations like these the function objects come in handy. As noted before, the function objects are heavily used in the context of the generic algorithms, so let's take a quick look ahead at one of them.

One of the generic algorithms is called accumulate(). It visits all elements implied by an iterator-range, and performs a requested binary operation on a common element and each of the elements in the range, returning the accumulated result after visiting all elements. For example, the following program accumulates all command line arguments, and prints the final string:

    #include <iostream>
    #include <string>
    #include <functional>
    #include <numeric>
    
    int main(int argc, char **argv)
    {
        string
            result =
                accumulate(argv, argv + argc, string(), plus<string>());
    
        cout << "All concatenated arguments: " << result << endl;
    }
The first two arguments define the (iterator) range of elements to visit, the third argument is string(). This anonymous string object provides an initial value. It could as well have been initialized to
string("All concatenated arguments: ")

in which case the cout statement could have been a simple

cout << result << endl

Then, the operator to apply is plus<string>(). Here it is important to note that a constructor is called: it is not plus<string>, but rather plus<string>(). The final concatenated string is returned.

Now we define our own class Time, in which the operator+() has been overloaded. Again, we can apply the predefined function object plus, now tailored to our newly defined datatype, to add times:

    #include <iostream>
    #include <strstream>
    #include <string>
    #include <vector>
    #include <functional>
    #include <numeric>
    
    class Time
    {
        friend ostream &operator<<(ostream &str, Time const &time)
        {
            return cout << time.days << " days, " << time.hours << ":" << 
                            time.minutes << ":" << time.seconds;
        }

        public:
            Time(unsigned hours, unsigned minutes, unsigned seconds)
            {
                days = 0;
                this->hours   = hours;
                this->minutes = minutes;
                this->seconds = seconds;
            }

            Time(Time const &other)
            {
                this->days    = other.days;
                this->hours   = other.hours;
                this->minutes = other.minutes;
                this->seconds = other.seconds;
            }

            Time operator+(Time const &rValue) const
            {
                Time
                    added(*this);

                added.seconds   += rValue.seconds;
                added.minutes   += rValue.minutes   + added.seconds / 60;
                added.hours     += rValue.hours     + added.minutes / 60;
                added.days      += rValue.days      + added.hours   / 24;
                added.seconds   %= 60;
                added.minutes   %= 60;
                added.hours     %= 24;

                return added;
            } 

        private:
            unsigned
                days,
                hours,
                minutes,
                seconds;
    };
    
    int main(int argc, char **argv)
    {
        vector<Time>
            tvector;
    
        tvector.push_back(Time( 1, 10, 20));
        tvector.push_back(Time(10, 30, 40));
        tvector.push_back(Time(20, 50,  0));
        tvector.push_back(Time(30, 20, 30));
    
        cout << 
            accumulate
            (
                tvector.begin(), tvector.end(), Time(0, 0, 0), plus<Time>()
            ) << 
            endl;
    }
    /*
        produced output:
    2 days, 14:51:30
    */
Note that all member functions of Time in the above source are inline functions. This approach was followed in order to keep the example relatively small and to show explicitly that the operator+() function may be an inline function. On the other hand, in real life the operator+() function of Time should probably not be made inline, due to its size. Considering the previous discussion of the plus function object, the example is pretty straightforward. The class Time defines two constructors, the second one being the copy-constructor, it defines a conversion operator (operator char const *()) to produce a textual representation of the stored time (deploying an ostrstream object, see chapter 5), and it defines its own operator+(), adding two time objects.

The overloading of operator+() deserves some attention. In expressions like x + y neither x nor y are modified. The result of the addition is returned as a temporary value, which is then used in the rest of the expression. Consequently, in the operator+() function the this object and the rValue object must not be modified. Hence the const modifier for operator+(), forcing this to be constant, and the const modifier for rValue, forcing rValue to be constant. The sum of both times is stored in a separate Time object, a copy of which is then returned by the function.

In the main() function four Time objects are stored in a vector<Time> object. Then, the accumulate() generic algorithm is called to compute the accumulated time. It returns a Time object, which is inserted in the cout ostream object.

While the first example did show the use of a named function object, the last two examples showed the use of anonymous objects which were passed to the (accumulate()) function.

The following arithmetic objects are available as predefined objects:

  • plus<>(), as shown, this object calls the operator+()
  • minus<>(), calling operator-() as a binary operator,
  • multiplies<>(), calling operator*() as a binary operator,
  • divides<>(), calling operator/(),
  • modulus<>(), calling operator%(),
  • negate<>(), calling operator-() as a unary operator.
  • An example using the unary operator-() follows, in which the transform() generic algorithm is used to toggle the signs of all elements in an array. The transform() generic algorithm expects two iterators, defining the range of objects to be transformed, an iterator defining the begin of the destination range (which may be the same iterator as the first argument) and a function object defining a unary operation for the indicated data type.
        #include <iostream>
        #include <string>
        #include <functional>
        #include <algorithm>
        
        int main(int argc, char **argv)
        {
            int
                iArr[] = { 1, -2, 3, -4, 5, -6 };
        
            transform(iArr, iArr + 6, iArr, negate<int>());
        
            for (int idx = 0; idx < 6; ++idx)
                cout << iArr[idx] << ", ";
        
            cout << endl;
        }
        /*
            generated output:
        -1, 2, -3, 4, -5, 6,
        */
    

    17.1.2: Relational Function Objects

    The relational operators may be called from the relational function objects. All standard relational operators are supported: ==, !=, >, >=, < and <=. The following objects are available:
  • equal_to<>(), calling operator==(),
  • not_equal_to<>(), calling operator!=(),
  • greater<>(), calling operator>(),
  • greater_equal<>(), calling operator>=(),
  • less<>(), calling operator<(),
  • less_equal<>(), calling operator<=().
  • Like the arithmetic function objects, these function objects can be used as named or as anonymous objects. An example using the relational function objects using the generic algorithm sort() is:
        #include <iostream>
        #include <string>
        #include <functional>
        #include <algorithm>
        
        int main(int argc, char **argv)
        {
            sort(argv, argv + argc, greater_equal<string>());
    
            for (int idx = 0; idx < argc; ++idx)
                cout << argv[idx] << " ";
            cout << endl;
        
            sort(argv, argv + argc, less<string>());
    
            for (int idx = 0; idx < argc; ++idx)
                cout << argv[idx] << " ";
            cout << endl;
        }
    
    The sort() generic algorithm expects an iterator range and a comparator for the underlying data type. The example shows the alphabetic sorting of strings and the reversed sorting of strings. By passing greater_equal<string>() the strings are sorted in decreasing order (the first word will be the 'greatest'), by passing less<string>() the strings are sorted in increasing order (the first word will be the 'smallest').

    Note that the type of the elements of argv is char *, and that the relational function object expects a string. The relational object greater_equal<string>() will therefore use the >= operator of strings, but will be called with char * variables. The conversion from char * arguments to string const & parameters is done implicitly by the string(char const *) constructor.

    17.1.3: Logical Function Objects

    The logical operators are called by the logical function objects. The standard logical operators are supported: &&, || and !. The following objects are available:
  • logical_and<>(), calling operator&&(),
  • logical_or<>(), calling operator||(),
  • logical_not<>(), calling operator!() ( unary operator).
  • An example using the operator!() is the following trivial example, in which the transform() generic algorithm is used to transform the logical values stored in an array:
        #include <iostream>
        #include <string>
        #include <functional>
        #include <algorithm>
        
        int main(int argc, char **argv)
        {
            bool
                bArr[] = {true, true, true, false, false, false};
            unsigned const
                bArrSize = sizeof(bArr) / sizeof(bool);
        
            for (int idx = 0; idx < bArrSize; ++idx)
                cout << bArr[idx] << " ";
            cout << endl;
        
            transform(bArr, bArr + bArrSize, bArr, logical_not<bool>());
        
            for (int idx = 0; idx < bArrSize; ++idx)
                cout << bArr[idx] << " ";
            cout << endl;
        }
        /*
            generated output:
        1 1 1 0 0 0 
        0 0 0 1 1 1 
        */
    

    17.1.4: Function Adaptors

    Function adaptors modify the working of existing function objects. There are two kinds of function adaptors:
  • Binders are function adaptors converting binary function objects to unary function objects. They do so by binding one object to a constant function object. For example, with the minus<int>() function object, which is a binary function object, the first argument may be bound to 100, meaning that the resulting value will always be 100 minus the value of the second argument. Either the first or the second argument may be bound to a specific value. To bind the first argument to a specific value, the function object bind1st() is used. To bind the second argument of a binary function to a specific value bind2nd() is used. As an example, assume we want to count all elements of a vector of Person objects that exceed (according to some criterion) some reference Person object. For this situation we pass the following binder and relational function object to the count_if() generic algorithm:
        bind2nd(greater<Person>(), referencePerson)
    
    The count_if() generic algorithm visits all the elements in an iterator range, returning the number of times the predicate specified as its final argument returns true. Each of the elements of the iterator range is given to the predicate, which is therefore a unary function. By using the binder the binary function object greater() is adapted to a unary function object, comparing each of the elements in the range to the reference person. Here is, to be complete, the call of the count_if() function:
        count_if(pVector.begin(), pVector.end(), 
            bind2nd(greater<Person>(), referencePerson))
    
  • The negators are function adaptors converting the truth value of a predicate function. Since there are unary and binary predicate functions, there are two negator function adaptors: not1() is the negator to be used with unary function objects, not2() is the negator to be used with binary function objects.
  • If we want to count the number of persons in a vector<Person> vector not exceeding a certain reference person, we may, among other approaches, use either of the following alternatives:
  • Use a binary predicate that directly offers the required comparison:
        count_if(pVector.begin(), pVector.end(), 
            bind2nd(less_equal<Person>(), referencePerson))
    
  • Use not2 in combination with the greater() predicate:
        count_if(pVector.begin(), pVector.end(), 
            bind2nd(not2(greater<Person>()), referencePerson))
    
  • Use not1() in combination with the bind2nd() predicate:
        count_if(pVector.begin(), pVector.end(), 
            not1(bind2nd((greater<Person>()), referencePerson)))
    
    The following little example illustrates the use of negator function adaptors, completing the section on function objects:
        #include <iostream>
        #include <functional>
        #include <algorithm>
        #include <vector>
        
        int main(int argc, char **argv)
        {
            int
               iArr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        
            cout << count_if(iArr, iArr + 10, bind2nd(less_equal<int>(), 6)) << 
                endl;
            cout << count_if(iArr, iArr + 10, bind2nd(not2(greater<int>()), 6)) << 
                endl;
            cout << count_if(iArr, iArr + 10, not1(bind2nd(greater<int>(), 6))) << 
                endl;
        }
        /*
            produced output:
        6
        6
        6
        */
    
  • 17.2: Iterators

    Iterators are an abstraction of pointers. In general, the following holds true for iterators:
  • Given an iterator iter, *iter represents the object the iterator points to (alternatively, iter-> can be used to reach the object the iterator points to).
  • ++iter or iter++ advances the iterator to the next element. The notion of advancing an iterator to the next element is consequently applied: several containers have a reversed_iterator type, in which the iter++ operation actually reaches an previous element in a sequence.
  • For the containers that have their elements stored consecutively in memory pointer arithmetic is available as well. This includes the vector and deque. For these containers iter + 2 points to the second element beyond the one to which iter points.
  • The STL containers usually define members producing iterators (i.e., type iterator) using member functions begin() and end() and, in the case of reversed iterators (type reverse_iterator), rbegin() and rend(). Standard practice requires the iterator range to be left inclusive: the notation [left, right) indicates that left is an iterator pointing to the first element that is to be considered, while right is an iterator pointing just beyond the last element to be used. The iterator-range is said to be empty when left == right.

    The following example shows a situation where all elements of a vector of strings are written to cout using the iterator range [begin(), end()), and the iterator range [rbegin(), rend()). Note that the for-loops for both ranges are identical:

    #include <iostream>
    #include <vector>
    #include <string>
    
    int main(int argc, char **argv)
    {
        vector<string>
            args(argv, argv + argc);
    
        for 
        (
            vector<string>::iterator iter = args.begin();
                iter != args.end();
                    ++iter
        )
            cout << *iter << " ";
    
        cout << endl;
    
        for 
        (
            vector<string>::reverse_iterator iter = args.rbegin();
                iter != args.rend();
                    ++iter
        )
            cout << *iter << " ";
    
        cout << endl;
        
        return (0);
    }
    

    Furthermore, the STL defines const_iterator types to be able to visit a range of the elements in a constant container. Whereas the elements of the vector in the previous example could have been altered, the elements of the vector in the next example are immutable, and const_iterators are required:

        #include <iostream>
        #include <vector>
        #include <string>
        
        int main(int argc, char **argv)
        {
            const vector<string>
                args(argv, argv + argc);
        
            for 
            (
                vector<string>::const_iterator iter = args.begin();
                    iter != args.end();
                        ++iter
            )
                cout << *iter << " ";
        
            cout << endl;
        
            for 
            (
                vector<string>::const_reverse_iterator iter = args.rbegin();
                    iter != args.rend();
                        ++iter
            )
                cout << *iter << " ";
        
            cout << endl;
        }
    
    The examples also illustrates the use of plain pointers for iterators. The initialization vector<string> args(argv, argv + argc) provides the args vector with a pair of pointer-based iterators: argv points to the first element to initialize sarg with, argv + argc points just beyond the last element to be used, argv++ reaches the next string. This is a general characteristic of pointers, which is why they too can be used in situations where iterators are expected.

    The STL defines five types of iterators. These types recur in the generic algorithms, and in order to be able to create a particular type of iterator yourself it is important to know their characteristic. In general, iterators must define:

  • operator==(), testing two iterators for equality,
  • operator++(), incrementing the iterator, as prefix operator,
  • operator*(), to access the element the iterator refers to,
  • The following types of iterators are used with the generic algorithms:
  • InputIterators: InputIterators can read from a container. The dereference operator is guaranteed to work as rvalue in expressions. Instead of an InputIterator it is also possible to (see below) use a Forward-, Bidirectional- or RandomAccessIterator. With the generic algorithms presented in this chapter, iterator types like InputIterator1 and InputIterator2 may be observed as well. In these cases numbers are used to indicate which iterators `belong together'. E.g., the generic function inner_product() has the following prototype:
        Type inner_product(InputIterator1 first1, InputIterator1 last1,
                       InputIterator2 first2, Type init);
    
    Here InputIterator1 first1 and InputIterator1 last1 are a set of input iterators defining one range, while InputIterator2 first2 defines the beginning of a second range. Notations like this may be observed with other iterator types as well.
  • OutputIterators: OutputIterators can be used to write to a container. The dereference operator is guaranteed to work as an lvalue in expressions, but not necessarily as rvalue. Instead of an OutputIterator it is also possible to use, see below, a Forward-, Bidirectional- or RandomAccessIterator.
  • ForwardIterators: ForwardIterators combine InputIterators and OutputIterators. They can be used to traverse containers in one direction, for reading and/or writing. Instead of a ForwardIterator it is also possible to use a Bidirectional- or RandomAccessIterator.
  • BidirectionalIterators: BidirectionalIterators can be used to traverse containers in both directions, for reading and writing. Instead of a BidirectionalIterator it is also possible to use a RandomAccessIterator. For example, to traverse a list or a deque a BidirectionalIterator may be useful.
  • RandomAccessIterators: RandomAccessIterators provide random access to container elements. An algorithm such as sort() requires a RandomAccessIterator, and can therefore not be used with lists or maps, which only provide BidirectionalIterators.
  • The example given with the RandomAccessIterator provides an approach towards iterators: look for the iterator that's required by the (generic) algorithm, and then see whether the datastructure supports the required iterator. If not, the algorithm cannot be used with the particular datastructure.

    17.2.1: Insert iterators

    Generic algorithms often require a target container into which the results of the algorithm are deposited. For example, the copy() algorithm has three parameters, the first two of them define the range of elements which are visited, and the third parameter defines the first position where the result of the copy operation is to be stored. With the copy() algorithm the number of elements that are copied are normally available beforehand, since the number is normally equal to the number of elements in the range defined by the first two parameters, but this does not always hold true. Sometimes the number of resulting elements is different from the number of elements in the initial range. The generic algorithm unique_copy() is a case in point: the number of elements which are copied to the destination container is normally not known beforehand. In situations like these, an inserter adaptor function may be used to create elements in the destination container when they are needed.

    There are three inserter() adaptors:

  • back_inserter(): calls the container's push_back() member to add new elements at the end of the container. E.g., to copy all elements of source in reversed order to the back of destination:
        copy(source.rbegin(), source.rend(), back_inserter(destination));
    
  • front_inserter() calls the container's push_front() member to add new elements at the beginning of the container. E.g., to copy all elements of source to the front of the destination container (thereby also reversing the order of the elements):
        copy(source.begin(), source.end(), front_inserter(destination));
    
  • inserter() calls the container's insert() member to add new elements starting at a specified starting point. E.g., to copy all elements of source to the destination container, starting at the beginning of destination.
        copy(source.begin(), source.end(), inserter(destination,
            destination.begin()));
    
  • 17.2.2: istream iterators

    The istream_iterator<Type>() can be used to define an iterator (pair) for an istream object. The general form of the istream_iterator<Type>() iterator is:
        istream_iterator<Type> 
            identifier(istream &inStream)
    
    Here, Type is the type of the data elements that are to be read from the istream stream. Type may be any type for which operator>>() is defined with istream objects.

    The default constructor defines the end of the iterator pair, corresponding to end-of-stream. For example,

        istream_iterator<string> 
            endOfStream;
    
    Note that the actual stream object which is specified for the begin-iterator is not mentioned.

    Using a back_inserter() and a set of istream_iterator<>() adaptors all strings could be read from cin as follows:

        #include <algorithm>
        #include <iterator>
        #include <string>
        #include <vector>
        
        int main()
        {
            vector<string>
                vs;
        
            copy(istream_iterator<string>(cin), istream_iterator<string>(),
                 back_inserter(vs));
        
            for 
            (
                vector<string>::iterator from = vs.begin();
                    from != vs.end();
                        ++from
            )
                cout << *from << " ";
    
            cout << endl;
        }
    
    In the above example, note the use of the anonymous versions of the istream_iterator adaptors. Especially note the use of the anonymous default constructor. Instead of using istream_iterator<string>() the following (non-anonymous) construction could have been used:
        istream_iterator<string>
                eos;
    
        copy(istream_iterator<string>(cin), eos, back_inserter(vs));
    
    In order to use the istream_iterator adaptor, sources must
        #include <iterator>
    
    This is automatically done when iostream is included.

    17.2.2.1: istreambuf iterators

    For streambuf objects iterators are also available. The istreambuf_iterator is available after using the preprocessor directive

        #include <iterator>
    
    The istreambuf_iterator is available for reading from streambuf objects that are available for input operations. The standard operations that are also available for istream_iterator objects are also available for istreambuf_iterators. There are three constructors:
  • istreambuf_iterator<Type>():
    This constructor represents the end-of-stream iterator while extracting values of type Type from the streambuf.
  • istreambuf_iterator<Type>(istream):
    This constructor constructs an istream_iterator accessing the streambuf of the istream object, used as argument of the constructor.
  • istreambuf_iterator<Type>(streambuf *):
    This constructor constructs an istream_iterator accessing the streambuf whose address is used as argument of the constructor.
  • In section 17.2.3.1 an example is given using both istreambuf_iterators and ostreambuf_iterators.

    17.2.3: ostream iterators

    The ostream_iterator<Type>() can be used to define a destination iterator for an ostream object. The general forms of the ostream_iterator<Type>() iterator are:
        ostream_iterator<Type> 
            identifier(ostream &outStream), // and:
            identifier(ostream &outStream, char const *delimiter);
    
    Type is the type of the data elements that are to be written to the ostream stream. Type may be any type for which operator<<() is defined with ostream objects. The latter form of the ostream_iterators separates the individual Type data elements by delimiter strings. The former definition does not use any delimiters.

    The next example shows the use of a istream_iterators and an ostream_iterator to copy information of a file to another file. A subtlety is the statement in.unsetf(ios::skipws): it resets the ios::skipws flag. The consequence of this is that the default behavior of operator>>(), to skip whitespace, is modified. White space characters are simply returned by the operator, and the file is copied unrestrictedly. Here is the program:

        #include <algorithm>
        #include <fstream>
        #include <iomanip>
        
        int main(int argc, char **argv)
        {
            ifstream
                in(argv[1]);
        
            in.unsetf(ios::skipws);
        
            ofstream
                out(argv[2]);
        
            copy(istream_iterator<char>(in), istream_iterator<char>(),
                 ostream_iterator<char>(out));
        }
    
    In order to use the ostream_iterator adaptor, sources must
        #include <iterator>
    
    This is automatically done when iostream is included.

    17.2.3.1: ostreambuf iterators

    The ostreambuf_iterator is available after using the preprocessor directive

        #include <iterator>
    
    The ostreambuf_iterator is available for writing to streambuf objects that support output operations. The standard operations that are also available for ostream_iterator objects are also available for ostreambuf_iterators. There are two constructors:
  • ostreambuf_iterator<Type>(istream):
    This constructor constructs an ostream_iterator accessing the streambuf of the ostream object, used as argument of the constructor, to insert values of type Type.
  • ostreambuf_iterator<Type>(streambuf *):
    This constructor constructs an ostream_iterator accessing the streambuf whose address is used as argument of the constructor.
  • Here is an example using both istreambuf_iterators and an ostreambuf_iterator, showing yet another way to copy a stream:
        #include <iostream>
        #include <algorithm>    // implies #include <iterator>
        
        using namespace std;
    
        int main()
        {
            istreambuf_iterator<char> in(cin.rdbuf());
            istreambuf_iterator<char> eof;
            ostreambuf_iterator<char> out(cout.rdbuf());
    
            copy(in, eof, out);
        }
    

    17.3: The 'auto_ptr' class

    One of the problems using pointers is that strict bookkeeping is required about the memory the pointers point to. When a pointer variable goes out of scope, the memory pointed to by the pointer is suddenly inaccessible, and the program suffers from a memory leak. For example, in the following function fun(), a memory leak is created by calling fun(): 200 int values remain inaccessibly allocated:
        void fun()
        {
            new int[200];
        }
    
    The standard way to prevent memory leakage is strict bookkeeping: the programmer has to make sure that the memory pointed to by a pointer is deleted just before the pointer variable goes out of scope. In the above example the repair would be:
        void fun()
        {
            delete new int[200];
        }
    
    Now fun() only wastes a bit of time.

    When a pointer variable is used to point to a single value or object, the bookkeeping becomes less of a burden when the pointer variable is defined as an auto_ptr object. In order to use the auto_ptr template class, sources must

        #include <memory>
    
    Normally, an auto_ptr object is initialized to point to a dynamically created value or object. When the auto_ptr object goes out of scope, the memory pointed to by the object is automatically deleted, taking over the programmer's responsibility to delete memory.

    Note that:

  • the auto_ptr object cannot be used to point to arrays of objects.
  • an auto_ptr object should only point to memory that was made available dynamically, as only dynamically allocated memory can be deleted.
  • multiple auto_ptr objects should not be allowed to point to the same block of dynamically allocated memory. Once an auto_ptr object goes out of scope, it deletes the memory it points to, immediately changing the other objects into wild pointers. Ways to prevent this situation are discussed below.
  • The class auto_ptr defines several member functions which can be used to access the pointer itself or to have the auto_ptr point to another block of memory. These member functions and ways to construct auto_ptr objects are discussed in the following sections.

    17.3.1: Defining auto_ptr variables

    There are three ways to define auto_ptr objects. Each definition contains the usual <type> specifier between pointed brackets. Concrete examples are given in the coming sections, but an overview of the various possibilities is presented here:
  • The basic form initializes an auto_ptr object to a block of memory that's allocated by the new operator:
        auto_ptr<type> 
            identifier (new-expression);
    
    This form is discussed in section 17.3.2.
  • Another form initializes an auto_ptr object through another auto_ptr object:
        auto_ptr<type> 
            identifier(another auto_ptr for type);
    
    This form is discussed in section 17.3.3.
  • The third form simply creates an auto_ptr object that does not point to a particular block of memory:
        auto_ptr<type> 
            identifier;
    
    This form is discussed in section 17.3.4.
  • 17.3.2: Pointing to a newly allocated object

    The basic form to initialize an auto_ptr object is to provide its constructor with a block of memory that's allocated by operator new operator. The generic form is:
        auto_ptr<type> 
            identifier(new-expression);
    
    For example, to initialize an auto_ptr to a string variable the following construction can be used:
        auto_ptr<string> 
            strPtr(new string("Hello world"));
    
    To initialize an auto_ptr to a double variable the next construction can be used:
        auto_ptr<double> 
            dPtr(new double(123.456));
    
    Note the use of operator new in the above expressions. The use of new ensures the dynamic nature of the memory pointed to by the auto_ptr objects and allows the deletion of the memory once auto_ptr objects go out of scope. Also note that the type does not contain the pointer: the type used in the auto_ptr construction is the same type as used in the new expression.

    In the example allocating 200 int values given in section 17.3, the memory leak can be avoided by using auto_ptr objects:

        #include <memory>
    
        void fun()
        {
            auto_ptr<int>
                ip(new int[200]);
        }
    
    All member functions that are available for objects that were allocated by the new expression can be reached via the auto_ptr as if it was a plain pointer to the dynamically allocated object. For example, in the following program the text `C++' is inserted behind the word `hello':
        #include <iostream>
        #include <string>
        #include <memory>
    
        int main()
        {
            auto_ptr<string>
                sp(new string("Hello world"));
    
            cout << *sp << endl;
    
            sp->insert(strlen("Hello "), "C++ ");
            cout << *sp << endl;
        }
        /*
            produced output:
        Hello world
        Hello C++ world
        */
    

    17.3.3: Pointing to another auto_ptr

    Another form to initialize an auto_ptr object is to initialize it from another auto_ptr object for the same type. The generic form is:
        auto_ptr<type>
            identifier(other auto_ptr object);
    
    For example, to initialize an auto_ptr to a string variable, given the sp variable defined in the previous section, the following construction can be used:
        auto_ptr<string>
            strPtr(sp);
    
    A comparable construction can be used with the assignment operator in expressions. One auto_ptr object may be assigned to another auto_ptr object of the same type. For example:
        #include <iostream>
        #include <memory>
        #include <string>
    
        int main()
        {
            auto_ptr<string> 
                hello1(new string("Hello world")),
                hello2(hello1),
                hello3,
    
            hello3 = hello2;
            cout << *hello1 << endl <<
                    *hello2 << endl <<
                    *hello3 << endl;
        }        
        /*
            produced output:
        Segmentation fault
        */
    Looking at the above example, we see that hello1 is initialized as described in the previous section. Next hello2 is defined, and it receives its value from hello1, using a copy constructor type of initialization. Then hello3 is defined as a default auto_ptr<string>, but it receives its value through an assignment from hello2.

    Unfortunately, the program generates a segmentation fault. The reason for this is that eventually only hello3 points at the string hello world. First, at the initialization of hello2, hello1 loses the memory it points. Second, at the assignment to hello3 by hello2, hello2 loses the memory it points to: once a auto_ptr object is used for the initialization of or assignment to another auto_ptr object, the rvalue auto_ptr object will not refer anymore to the allocated memory. The allocated memory is now `owned' by the lvalue object.

    17.3.4: Creating a plain auto_ptr

    We've already seen the third form to create an auto_ptr object: Without arguments an empty auto_ptr object is constructed that does not point to a particular block of memory:
        auto_ptr<type> 
            identifier;
    
    In this case the underlying pointer is set to 0 (zero). Since the auto_ptr object itself is not the pointer, its value cannot be compared to 0 to see if it has not been initialized. E.g., code like
        auto_ptr<int>
            ip;
    
        if (!ip)
            cout << "0-pointer with an auto_ptr object ?" << endl;
    
    will not produce any output (actually, it won't compile either...). So, how do we inspect the value of the pointer that's maintained by the auto_ptr object? For this the member get() is available. This member function, as well as the other member functions of the class auto_ptr are described in the following sections.

    17.3.5: Auto_ptr: operators and members

    The following operators are defined for the class auto_ptr:
  • auto_ptr &auto_ptr<Type>operator=(auto_ptr<Type> &other):
    This operator will transfer the memory pointed to by the rvalue auto_ptr object to the lvalue auto_ptr object. So, the rvalue object loses the memory it pointed at.
  • Type &auto_ptr<Type>operator*():
    This operator returns a reference to the information stored in the auto_ptr object. It acts like a normal dereference operator with pointers.
  • Type *auto_ptr<Type>operator->():
    This operator returns a pointer to the information stored in the auto_ptr object. Through this operator members of a stored object an be selected. For example:
        auto_ptr<string>
            sp(new string("hello"));
    
        cout << sp->c_str() << endl;
    
  • The following member functions are defined for auto_ptr objects:
  • Type *auto_ptr<Type>::get():
    This operator does the same as operator->(): it returns a pointer to the information stored in the auto_ptr object. This pointer can be inspected: if it's zero the auto_ptr object does not point to any memory. This member cannot be used to let the auto_ptr object point to (another) block of memory.
  • Type *auto_ptr<Type>::release():
    This operator returns a pointer to the information stored in the auto_ptr object, which loses the memory it pointed at. The member can be used to transfer the information stored in the auto_ptr object to a plain Type pointer. After using release(), the auto_ptr object contains a 0-pointer while it is the responsibility of the programmer to delete the memory returned by this member function.
  • void auto_ptr<Type>::reset(Type *):
    This operator can be called without argument, to delete the memory stored in the auto_ptr object, or with an pointer to a dynamically allocated block of memory, which will thereupon become the memory that is stored in the auto_ptr object. This member function can therefore be used to assign a new block of memory (new content) to an auto_ptr object.
  • 17.4: The Generic Algorithms

    The following sections describe the generic algorithms in alphabetical order. For each algorithm the following information is provided:
  • The required header s
  • The function prototype
  • A short description
  • A short example
  • In the prototypes of the algorithms Type is used to specify a generic data type. The particular type of iterator (see section 17.2) that is required is mentioned, and possibly other generic types, e.g., performing BinaryOperations, like plus<Type>().

    Almost every generic algorithm has as its first two arguments an iterator range [first, last), defining the range of elements on which the algorithm operates. The iterators point to objects or values. When an iterator points to a Type value or object, called function objects receive Type const & objects or values: function objects can therefore not modify the objects they receive as their arguments.

    Generic algorithms may be categorized. In the C++ Annotations the following categories of generic algorithms are distinguished:

  • Comparators: comparing (ranges of) elements:
    Requires: #include <algorithm>

    equal(); includes(); lexicographical_compare(); max(); min(); mismatch();

  • Copiers: performing copy operations:
    Requires: #include <algorithm>

    copy(); copy_backward(); partial_sort_copy(); remove_copy(); remove_copy_if(); replace_copy(); replace_copy_if(); unique_copy();

  • Counters: performing count operations:
    Requires: #include <algorithm>

    count(); count_if();

  • Heap operators: manipulating a max-heap:
    Requires: #include <algorithm>

    make_heap(); pop_heap(); push_heap(); sort_heap();

  • Initializers: initializing data:
    Requires: #include <algorithm>

    fill(); fill_n(); generate(); generate_n();

  • Operators: performing arithmetic operations of some sort:
    Requires: #include <numeric>

    adjacent_difference(); accumulate(); inner_product(); partial_sum();

  • Searchers: performing search (and find) operations:
    Requires: #include <algorithm>

    adjacent_find(); binary_search(); equal_range(); find(); find_if(); find_end(); find_first_of(); lower_bound(); max_element(); min_element(); search(); search_n(); set_difference(); set_intersection(); set_symmetric_difference(); set_union(); upper_bound();

  • Shufflers: performing reordering operations ( sorting, merging, permuting, shuffling, swapping):
    Requires: #include <algorithm>

    inplace_merge(); iter_swap(); merge(); next_permutation(); nth_element(); partial_sort(); partial_sort_copy(); partition(); prev_permutation(); random_shuffle(); remove(); remove_copy(); remove_if(); remove_copy_if(); reverse(); reverse_copy(); rotate(); rotate_copy(); sort(); stable_partition(); stable_sort(); swap(); unique();

  • Visitors: visiting elements in a range:
    Requires: #include <algorithm>

    for_each(); replace(); replace_copy(); replace_if(); replace_copy_if(); transform(); unique_copy();

  • 17.4.1: accumulate()

  • Header file:
    #include <numeric>
    
  • Function prototypes:
  • Type accumulate(InputIterator first, InputIterator last, Type init);
  • Type accumulate(InputIterator first, InputIterator last, Type init, BinaryOperation op);
  • Description:
  • The first prototype: operator+() is applied to all elements implied by the iterator range and to the initial value init. The resulting value is returned.
  • The second prototype: the binary operator op() is applied to all elements implied by the iterator range and to the initial value init, and the resulting value is returned.
  • Example:
        #include<numeric>
        #include<vector>
        #include<iostream>
        
        int main()
        {
            int
                ia[] = {1, 2, 3, 4};
            vector<int>
                iv(ia, ia + 4);
        
            cout << 
                "Sum of values: " << accumulate(iv.begin(), iv.end(), int()) <<
                endl <<
                "Product of values: " << accumulate(iv.begin(), iv.end(), int(1),
                                                multiplies<int>()) <<
                endl;
        }
        /*
            generated output:
        Sum of values: 10
        Product of values: 24
        */
    
  • 17.4.2: adjacent_difference()

  • Header file:
    #include <numeric>
    
  • Function prototypes:
  • OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);
  • OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation op);
  • Description: All operations are performed on the original values, all computed values are returned values.
  • The first prototype: The first returned element is equal to the first element of the input range. The remaining returned elements are equal to the difference of the corresponding element in the input range and its previous element.
  • The second prototype: The first returned element is equal to the first element of the input range. The remaining returned elements are equal to the result of the binary operator op applied to the corresponding element in the input range (left operand) and its previous element (right operand).
  • Example:
        #include<numeric>
        #include<vector>
        #include<iostream>
        
        int main()
        {
            int
                ia[] = {1, 2, 5, 10};
            vector<int>
                iv(ia, ia + 4),
                ov(iv.size());
        
            adjacent_difference(iv.begin(), iv.end(), ov.begin());
    
            copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
            cout << endl;
        
            adjacent_difference(iv.begin(), iv.end(), ov.begin(), minus<int>());
    
            copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        1 1 3 5 
        1 1 3 5 
        */
    
  • 17.4.3: adjacent_find()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
  • OutputIterator adjacent_find(ForwardIterator first, ForwardIterator last, Predicate pred);
  • Description:
  • The first prototype: The iterator pointing to the first element of the first pair of two adjacent equal elements is returned. If no such element exists, last is returned.
  • The second prototype: The iterator pointing to the first element of the first pair of two adjacent elements for which the binary predicate pred returns true is returned. If no such element exists, last is returned.
  • Example:
        #include<algorithm>
        #include<string>
        #include<iostream>
        
        class SquaresDiff
        {
            public:
                SquaresDiff(unsigned minimum): minimum(minimum)
                {}
                bool operator()(unsigned first, unsigned second)
                {
                    return (second * second - first * first  >= minimum);
                }
            private:
                unsigned
                    minimum;
        };
            
                
        int main()
        {
            string
                sarr[] =
                {
                    "Alpha", "bravo", "charley", "delta", "echo", "echo", 
                    "foxtrot", "golf"
                };
            string
                *last = sarr + sizeof(sarr) / sizeof(string),
                *result = adjacent_find(sarr, last);
        
            cout << *result << endl;
            result = adjacent_find(++result, last);
        
            cout << "Second time, starting from the next position:\n" <<
                (
                    result == last ?
                        "** No more adjacent equal elements **"
                    :
                        "*result"
                ) << endl;
        
            unsigned
                *ires,
                iv[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
                *ilast = iv + sizeof(iv) / sizeof(unsigned);
        
        
            ires = adjacent_find(iv, ilast, SquaresDiff(10));
            cout << 
                "The first numbers for which the squares differ at least 10: "
                << *ires << " and " << *(ires + 1) << endl;
        }
        /*
            generated output:
        echo
        Second time, starting from the next position:
        ** No more adjacent equal elements **
        The first numbers for which the squares differ at least 10: 5 and 6
        */
    
  • 17.4.4: binary_search()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • bool binary_search(ForwardIterator first, ForwardIterator last, Type const &value);
  • bool binary_search(ForwardIterator first, ForwardIterator last, Type const &value, Comparator comp);
  • Description:
  • The first prototype: value is looked up using binary search in the range of elements implied by the iterator range [first, last). The elements in the range must have been sorted by the Type::operator<() function. True is returned if the element was found, false otherwise.
  • The second prototype: value is looked up using binary search in the range of elements implied by the iterator range [first, last). The elements in the range must have been sorted by the Comparator function object. True is returned if the element was found, false otherwise.
  • Example:
        #include <algorithm>
        #include <string>
        #include <iostream>
        #include <functional>
        
        int main()
        {
            string
                sarr[] =
                {
                    "alpha", "bravo", "charley", "echo", "delta", 
                    "foxtrot", "golf", "hotel"
                };
            string
                *last = sarr + sizeof(sarr) / sizeof(string);
            bool
                result = binary_search(sarr, last, "foxtrot");
    
            cout << (result ? "found " : "didn't find ") << "foxtrot" << endl;
        
            reverse(sarr, last);                // reverse the order of elements
                                                // binary search now fails:
            result = binary_search(sarr, last, "foxtrot");
            cout << (result ? "found " : "didn't find ") << "foxtrot" << endl;
                                                // ok when using appropriate
                                                // comparator:
            result = binary_search(sarr, last, "foxtrot", greater<string>());
            cout << (result ? "found " : "didn't find ") << "foxtrot" << endl;
        }
        /*
            generated output:
        found foxtrot
        didn't find foxtrot
        found foxtrot
        */
    
  • 17.4.5: copy()

  • Header file:
    #include <algorithm>
    
  • Function prototype:
  • OutputIterator copy(InputIterator first, InputIterator last, OutputIterator destination);
  • Description:
  • The range of elements implied by the iterator range [first, last) are copied to an output range, starting at destination, using the assignment operator of the underlying data type. The return value is the OutputIterator pointing just beyond the last element that was copied to the destinatin range (so, `last' in the destination range is returned). In the example, note the second call to copy(). It uses an ostream_iterator for string objects. This iterator will write the string values to the specified ostream (i.e., cout), separating the values by the specified separation string (i.e., " ").
  • Example:
        #include <algorithm>
        #include <string>
        #include <iostream>
        
        int main()
        {
            string
                sarr[] =
                {
                    "alpha", "bravo", "charley", "echo", "delta", 
                    "foxtrot", "golf", "hotel"
                };
            string
                *last = sarr + sizeof(sarr) / sizeof(string);
        
            copy(sarr + 2, last, sarr); // move all elements two positions left
        
                                        // copy to cout using an ostream_iterator
                                        // for strings,  
            copy(sarr, last, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        charley echo delta foxtrot golf hotel golf hotel 
        */
    
  • See also: unique_copy()
  • 17.4.6: copy_backward()

  • Header file:
    #include <algorithm>
    
  • Function prototype:
  • BidirectionalIterator copy_backward(InputIterator first, InputIterator last, BidirectionalIterator last2);
  • Description:
  • The range of elements implied by the iterator range [first, last) are copied from the element at position last - 1 until (and including) the element at position first to the element range, ending at position last2 - 1, using the assignment operator of the underlying data type. The destination range is therefore [last2 - (last - first), last2).

    The return value is the BidirectionalIterator pointing at the last element that was copied to the destinatin range (so, `first' in the destination range, pointed to by last2 - (last - first), is returned).

  • Example:
        #include <algorithm>
        #include <string>
        #include <iostream>
        
        int main()
        {
            string
                sarr[] =
                {
                    "alpha", "bravo", "charley", "echo", "delta", 
                    "foxtrot", "golf", "hotel"
                };
            string
                *last = sarr + sizeof(sarr) / sizeof(string);
        
            copy
            (
                copy_backward(sarr + 3, last, last - 3), 
                last, 
                ostream_iterator<string>(cout, " ")
            );
            cout << endl;
        }
        /*
            generated output:
        golf hotel foxtrot golf hotel foxtrot golf hotel 
        */
    
  • 17.4.7: count()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • size_t cout(InputIterator first, InputIterator last, Type const &value);
  • Description:
  • The number of times value occurs in the iterator range first, last is returned. To determine wheter value is equal to an element in the iterator range Type::operator==() is used.
  • Example:
        #include<algorithm>
        #include<iostream>
        
        int main()
        {
            int
                ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};
        
            cout << "Number of times the value 3 is available: " <<
                count(ia, ia + sizeof(ia) / sizeof(int), 3) <<
                endl;
        }
        /*
            generated output:
        Number of times the value 3 is available: 3
        */
    
  • 17.4.8: count_if()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • size_t cout_if(InputIterator first, InputIterator last, Predicate predicate);
  • Description:
  • The number of times unary predicate `predicate' returns true when applied to the elements implied by the iterator range first, last is returned.
  • Example:
        #include<algorithm>
        #include<iostream>
        
        class Odd
        {
            public:
                bool operator()(int value)
                {
                    return value & 1;
                }
        };
        
        int main()
        {
            int
                ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};
        
            cout << "The number of odd values in the array is: " << 
                count_if(ia, ia + sizeof(ia) / sizeof(int), Odd()) <<
                endl;
        }
        /*
            generated output:
        The number of odd values in the array is: 5
        */
    
  • 17.4.9: equal()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • bool equal(InputIterator first, InputIterator last, InputIterator otherFirst);
  • bool equal(InputIterator first, InputIterator last, InputIterator otherFirst, BinaryPredicate pred);
  • Description:
  • The first prototype: The elements in the range [first, last) are compared to a range of equal length starting at otherFirst. The function returns true if the visited elements in both ranges are equal pairwise. The ranges need not be of equal length, only the elements in the indicated range are considered (and must be available).
  • The second prototype: The elements in the range [first, last) are compared to a range of equal length starting at otherFirst. The function returns true if the binary predicate, applied to all corresponding elements in both ranges returns true for every pair of corresponsing elements. The ranges need not be of equal length, only the elements in the indicated range are considered (and must be available).
  • Example:
        #include <algorithm>
        #include <string>
        #include <iostream>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return !strcasecmp(first.c_str(), second.c_str());
                }
        };
        
        int main()
        {
            string
                first[] =
                {
                    "Alpha", "bravo", "Charley", "echo", "Delta", 
                    "foxtrot", "Golf", "hotel"
                },
                second[] =
                {
                    "alpha", "bravo", "charley", "echo", "delta", 
                    "foxtrot", "golf", "hotel"
                };
    
            string
                *last = first + sizeof(first) / sizeof(string);
        
            cout << "The elements of `first' and `second' are pairwise " <<
                (equal(first, last, second) ? "equal" : "not equal") <<
                endl <<
                "compared case-insensitively, they are " <<
                (
                    equal(first, last, second, CaseString()) ? 
                        "equal" : "not equal"
                ) << 
                endl;
        }
        /*
            generated output:
        The elements of `first' and `second' are pairwise not equal
        compared case-insensitively, they are equal
        */
    
  • 17.4.10: equal_range()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Type const &value);
  • pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Type const &value, Compare comp);
  • Description (see also identically named member functions of, e.g., the map (section 12.2.6) and multimap (section 12.2.7)containers):
  • The first prototype: Starting from a sorted sequence (where the operator<() of the underlying data type was used to sort the elements in the provided range), a pair of iterators representing the return value of, respectively, lower_bound() (returning the first element that is equal to the provided reference value, see section 17.4.25) and upper_bound()(returning the first element beyond the provided reference value, see section 17.4.66) is returned.
  • The second prototype: Starting from a sorted sequence (where the comp function object was used to sort the elements in the provided range), a pair of iterators representing the return value of, respectively, lower_bound() (section 17.4.25) and upper_bound()(section 17.4.66) is returned.
  • Example:
    #include <algorithm>
    #include <functional>
    #include <iostream>
    
    void  main()
    {
        int
            range[] = {1, 3, 5, 7, 7, 9, 9, 9};
        unsigned const
            size = sizeof(range) / sizeof(int);
    
        pair<int *, int *>
            pi;
    
        pi = equal_range(range, range + size, 7);
    
        cout << "Lower bound for 7: ";
        copy(pi.first, range + size, ostream_iterator<int>(cout, " "));
        cout << endl;
    
        cout << "Upper bound for 7: ";
        copy(pi.second, range + size, ostream_iterator<int>(cout, " "));
        cout << endl;
    
        sort(range, range + size, greater<int>());
    
        cout << "Sorted in descending order\n";
    
        copy(range, range + size, ostream_iterator<int>(cout, " "));
        cout << endl;
    
        pi = equal_range(range, range + size, 7, greater<int>());
    
        cout << "Lower bound for 7: ";
        copy(pi.first, range + size, ostream_iterator<int>(cout, " "));
        cout << endl;
    
        cout << "Upper bound for 7: ";
        copy(pi.second, range + size, ostream_iterator<int>(cout, " "));
        cout << endl;
    }
        /*
            generated output:
        Lower bound for 7: 7 7 9 9 9 
        Upper bound for 7: 9 9 9 
        Sorted in descending order
        9 9 9 7 7 5 3 1 
        Lower bound for 7: 7 7 5 3 1 
        Upper bound for 7: 5 3 1 
        */
    
  • 17.4.11: fill()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • void fill(ForwardIterator first, ForwardIterator last, Type const &value);
  • Description:
  • all the elements implied by the iterator range [first, last) are initialized to value, overwriting the previous values stored in the range.
  • Example:
        #include<algorithm>
        #include<vector>
        #include<iostream>
        
        int main()
        {
            vector<int>
                iv(8);
        
            fill(iv.begin(), iv.end(), 8);
        
            copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        8 8 8 8 8 8 8 8 
        */
    
  • 17.4.12: fill_n()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • void fill_n(ForwardIterator first, Size n, Type const &value);
  • Description:
  • n elements starting at the element pointed to by first are initialized to value, overwriting the previous values stored in the range.
  • Example:
        #include<algorithm>
        #include<vector>
        #include<iostream>
        
        int main()
        {
            vector<int>
                iv(8);
        
            fill_n(iv.begin() + 2, 4, 8);
        
            copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        0 0 8 8 8 8 0 0 
        */
    
  • 17.4.13: find()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • InputIterator find(InputIterator first, InputIterator last, Type const &value);
  • Description:
  • Element value is searched for in the range of the elements implied by the iterator range [first, last). An iterator pointing to the first element found is returned. If the element was not found, last is returned. The operator==() of the underlying data type is used to compare the elements.
  • Example:
        #include<algorithm>
        #include<string>
        #include<iostream>
        
        int main()
        {
            string
                sarr[] =
                {
                    "alpha", "bravo", "charley", "echo", "delta"
                };
            string
                *last = sarr + sizeof(sarr) / sizeof(string);
        
            copy
            (   
                find(sarr, last, "echo"), last, ostream_iterator<string>(cout, " ")
            );
            cout << endl;
        
            if (find(sarr, last, "india") == last)
            {
                cout << "`india' was not found in the range\n";
                copy(sarr, last, ostream_iterator<string>(cout, " "));
                cout << endl;
            }
        }
        /*
            generated output:
        echo delta 
        `india' was not found in the range
        alpha bravo charley echo delta 
        */
    
  • 17.4.14: find_if()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • InputIterator find_if(InputIterator first, InputIterator last, Prdicate pred);
  • Description:
  • An iterator pointing to the first element in the range implied by the iterator range [first, last) for which the (unary) predicate pred returns true is returned. If the element was not found, last is returned.
  • Example:
        #include<algorithm>
        #include<string>
        #include<iostream>
        
        class CaseName
        {
            public:
                CaseName(char const *str): _string(str)
                {}
                bool operator()(string const &element)
                {
                    return (!strcasecmp(element.c_str(), _string.c_str()));
                }
            private:
                string
                    _string;
        };
        
        
        int main()
        {
            string
                sarr[] =
                {
                    "Alpha", "Bravo", "Charley", "Echo", "Delta", 
                };
            string
                *last = sarr + sizeof(sarr) / sizeof(string);
        
            copy
            (   
                find_if(sarr, last, CaseName("charley")), 
                last, ostream_iterator<string>(cout, " ")
            );
            cout << endl;
        
            if (find_if(sarr, last, CaseName("india")) == last)
            {
                cout << "`india' was not found in the range\n";
                copy(sarr, last, ostream_iterator<string>(cout, " "));
                cout << endl;
            }
        }
        /*
            generated output:
        Charley Echo Delta 
        `india' was not found in the range
        Alpha Bravo Charley Echo Delta 
        */
    
  • 17.4.15: find_end()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
  • ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)
  • Description:
  • The first prototype: The sequence of elements implied by [first1, last1) is searched for the last occurrence of the sequence of elements implied by [first2, last2). If the sequence [first2, last2) is not found, last1 is returned, otherwise an iterator pointing to the first element of the matching sequence is returned. The operator==() of the underlying data type is used to compare the elements in the two sequences.
  • The second prototype: The sequence of elements implied by [first1, last1) is searched for the last occurrence of the sequence of elements implied by [first2, last2). If the sequence [first2, last2) is not found, last1 is returned, otherwise an iterator pointing to the first element of the matching sequence is returned. The provided binary predicate is used to compare the elements in the two sequences.
  • Example:
        #include<algorithm>
        #include<string>
        #include<iostream>
        
        class Twice
        {
            public:
                bool operator()(unsigned first, unsigned second) const
                {
                    return (first == (second << 1));
                }
        };
        
        int main()
        {
            string
                sarr[] =
                {
                    "alpha", "bravo", "charley", "echo", "delta", 
                    "foxtrot", "golf", "hotel",
                    "foxtrot", "golf", "hotel",
                    "india", "juliet", "kilo"
                },
                search[] = 
                {
                    "foxtrot",
                    "golf", 
                    "hotel"
                };
            string
                *last = sarr + sizeof(sarr) / sizeof(string);
        
            copy
            (   
                find_end(sarr, last, search, search + 3),   // sequence starting
                last, ostream_iterator<string>(cout, " ")   // at 2nd 'foxtrot'
            );                                              
            cout << endl;
        
            unsigned
                range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10},
                nrs[]   = {2, 3, 4};
        
        
            copy                // sequence of values starting at last sequence 
            (                   // of range[] that are twice the values in nrs[]
                find_end(range, range + 9, nrs, nrs + 3, Twice()), 
                range + 9, ostream_iterator<unsigned>(cout, " ")
            );                                              
            cout << endl;
        }
        /*
            generated output:
        foxtrot golf hotel india juliet kilo 
        4 6 8 10 
        */
    
  • 17.4.16: find_first_of()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • 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 pred)
  • Description:
  • The first prototype: The sequence of elements implied by [first1, last1) is searched for the first occurrence of an element in the sequence of elements implied by [first2, last2). If no element in the sequence [first2, last2) is found, last1 is returned, otherwise an iterator pointing to the first element in [first1, last1) that is equal to an element in [first2, last2) is returned. The operator==() of the underlying data type is used to compare the elements in the two sequences.
  • The second prototype: The sequence of elements implied by [first1, first1) is searched for the first occurrence of an element in the sequence of elements implied by [first2, last2). Each element in the range [first1, last1) is compared to each element in the range [first2, last2), and an iterator to the first element in [first1, last1) for which the binary predicate pred (receiving an the element out of the range [first1, last1) and an element from the range [first2, last2)) returns true is returned. Otherwise, last1 is returned.
  • Example:
        #include<algorithm>
        #include<string>
        #include<iostream>
        
        class Twice
        {
            public:
                bool operator()(unsigned first, unsigned second) const
                {
                    return (first == (second << 1));
                }
        };
        
        int main()
        {
            string
                sarr[] =
                {
                    "alpha", "bravo", "charley", "echo", "delta", 
                    "foxtrot", "golf", "hotel",
                    "foxtrot", "golf", "hotel",
                    "india", "juliet", "kilo"
                },
                search[] = 
                {
                    "foxtrot",
                    "golf", 
                    "hotel"
                };
            string
                *last = sarr + sizeof(sarr) / sizeof(string);
        
            copy
            (                                               // sequence starting
                find_first_of(sarr, last, search, search + 3),  // at 1st 'foxtrot'
                last, ostream_iterator<string>(cout, " ")   
            );                                              
            cout << endl;
        
            unsigned
                range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10},
                nrs[]   = {2, 3, 4};
        
            copy            // sequence of values starting at first sequence 
            (               // of range[] that are twice the values in nrs[]
                find_first_of(range, range + 9, nrs, nrs + 3, Twice()), 
                range + 9, ostream_iterator<unsigned>(cout, " ")
            );                                              
            cout << endl;
        }
        /*
            generated output:
        foxtrot golf hotel foxtrot golf hotel india juliet kilo 
        4 6 8 10 4 6 8 10 
        */
    
  • 17.4.17: for_each()

  • Header file:
    #include <algorithm>
    
  • Function prototype:
  • Function for_each(InputIterator first, InputIterator last, Function func);
  • Description:
  • Each of the elements implied by the iterator range [first, last) is passed in turn as a const & to the function object func. The function is not supposed to modify the elements it receives (as the used iterator is an input iterator). If the elements are to be transformed, transform() (see section 17.4.63) should be used. The function object is returned: see the example below, in which an extra argument list is added to the for_each() call, which argument is eventually also passed to the function given to for_each(). Within for_each() the return value of the function that is passed to it is ignored.
  • Example:
        #include<algorithm>
        #include<string>
        #include<iostream>
        
        void capitalizedOutput(string const &str)
        {
            char
                *tmp = strcpy(new char[str.size() + 1], str.c_str());
        
                                // can't use for_each here, as 'tmp' is modified
            transform(tmp + 1, tmp + str.size(), tmp + 1, tolower);
        
            tmp[0] = toupper(*tmp);
            cout << tmp << " ";
            delete tmp;
        };
        
        int main()
        {
            string
                sarr[] =
                {
                    "alpha", "BRAVO", "charley", "ECHO", "delta", 
                    "FOXTROT", "golf", "HOTEL", 
                },
                *last = sarr + sizeof(sarr) / sizeof(string);
        
            for_each(sarr, last, capitalizedOutput)("that's all, folks");
            cout << endl;
        }
        /*
            generated output:
        Alpha Bravo Charley Echo Delta Foxtrot Golf Hotel That's all, folks 
        */
    
  • Although the function receives const references to objects, applications may consider it acceptable to overrule the const & nature of the parameter of func.operator()(). If the parameter expects a Type const &cref, the function could modify the referenced object after defining:
    Type &ref = const_cast<Type &>(cref)

    Following this definition ref can be used to modify the object that was passed as a reference. It is clear that we are stepping on dangerous grounds here, but if the programmer knows what he/she is doing, no damage should result from this type cast. The alternative, using the transform() generic algorithm involves the copying of an object, possibly into its original location. The penalty for doing so (calling a destructor and a copy constructor) might be considered more severe than using a type cast. Let it, however, be clear that we are not really advocating the use of a type cast with foreach() here. Rather, a possibility is mentioned. It is, as always, the responsibility of the programmer to use or avoid the typecast.

    17.4.18: generate()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • void generate(ForwardIterator first, ForwardIterator last, Generator generator);
  • Description:
  • All elements implied by the iterator range [first, last) are initialized by the return value of generator, which can be a function or function object. Note that Generator::opeator()() is not given any arguments. The example uses a well-known fact from algebra: in order to obtain the square of n + 1, add 1 + 2 * n to n * n.
  • Example:
        #include<algorithm>
        #include<vector>
        #include<iostream>
        
        class NaturalSquares
        {
            public:
                NaturalSquares(): newsqr(0), last(0)
                {}    
                unsigned operator()()
                {                           // using: (a + 1)^2 == a^2 + 2*a + 1
                    return newsqr += (last++ << 1) + 1;
                }
        
            private:
                unsigned
                    newsqr,
                    last;
        };
        
        int main()
        {
            vector<unsigned>
                uv(10);
        
            generate(uv.begin(), uv.end(), NaturalSquares());
        
            copy(uv.begin(), uv.end(), ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        1 4 9 16 25 36 49 64 81 100 
        */
    
  • 17.4.19: generate_n()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • void generate_n(ForwardIterator first, Size n, Generator generator);
  • Description:
  • n elements starting at the element pointed to by iterator first are initialized by the return value of generator, which can be a function or function object.
  • Example:
        #include<algorithm>
        #include<vector>
        #include<iostream>
        
        class NaturalSquares
        {
            public:
                NaturalSquares(): newsqr(0), last(0)
                {}    
                unsigned operator()()
                {                                   // (a + 1)^2 == a^2 + 2*a + 1
                    return (newsqr += (last++ << 1) + 1);
                }
        
            private:
                unsigned
                    newsqr,
                    last;
        };
        
        int main()
        {
            vector<unsigned>
                uv(10);
        
            generate_n(uv.begin(), 5, NaturalSquares());
        
            copy(uv.begin(), uv.end(), ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        1 4 9 16 25 0 0 0 0 0 
        */
    
  • 17.4.20: includes()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
  • bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
  • Description:
  • The first prototype: Both sequences of elements implied by the ranges [first1, last1) and [first2, last2) should be sorted, using the operator<() of the underlying datatype. The function returns true if every element in the second sequence [first2, second2) is contained in the first sequence [first1, second1) (the second range is a subset of the first range).
  • The second prototype: Both sequences of elements implied by the ranges [first1, last1) and [first2, last2) should be sorted, using the comp function object. The function returns true if every element in the second sequence [first2, second2) is contained in the first seqence [first1, second1) (the second range is a subset of the first range).
  • Example:
        #include <algorithm>
        #include <string>
        #include <iostream>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return (!strcasecmp(first.c_str(), second.c_str()));
                }
        };
        
        int main()
        {
            string
                first1[] =
                {
                    "alpha", "bravo", "charley", "echo", "delta", 
                    "foxtrot", "golf", "hotel"
                },
                first2[] =
                {
                    "Alpha", "bravo", "Charley", "echo", "Delta", 
                    "foxtrot", "Golf", "hotel"
                },
                second[] = 
                {
                    "charley", "foxtrot", "hotel"
                };
            unsigned
                n = sizeof(first1) / sizeof(string);
        
            cout << "The elements of `second' are " <<
                (includes(first1, first1 + n, second, second + 3) ? "" : "not") 
                << " contained in the first sequence:\n"
                   "second is a subset of first1\n";
        
            cout << "The elements of `first1' are " <<
                (includes(second, second + 3, first1, first1 + n) ? "" : "not") 
                << " contained in the second sequence\n";
        
            cout << "The elements of `second' are " <<
                (includes(first2, first2 + n, second, second + 3) ? "" : "not") 
                << " contained in the first2 sequence\n";
        
            cout << "Using case-insensitive comparison,\n"
                "the elements of `second' are " 
                << 
                (includes(first2, first2 + n, second, second + 3, CaseString()) ? 
                    "" : "not") 
                << " contained in the first2 sequence\n";
        }
        /*
            generated output:
        The elements of `second' are  contained in the first sequence: 
        second is a subset of first1
        The elements of `first1' are not contained in the second sequence
        The elements of `second' are not contained in the first2 sequence
        Using case-insensitive comparison,
        the elements of `second' are  contained in the first2 sequence
        */
    
  • 17.4.21: inner_product()

  • Header files:
    #include <numeric>
    
  • Function prototypes:
  • Type inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Type init);
  • Type inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Type init, BinaryOperator1 op1, BinaryOperator2 op2);
  • Description:
  • The first prototype: The sum of all pairwise products of the elements implied by the range [first1, last1) and the same number of elements starting at the element pointed to by first2 are added to init, and this sum is returned. The function uses the operator+() and operator*() of the underlying datatype.
  • The second prototype: Binary operator op2 instead of the default addition operator, and binary operator op1 instead of the default multiplication operator are applied to all pairwise elements implied by the range [first1, last1) and the same number of elements starting at the element pointed to by first2. The final result is returned.
  • Example:
        #include <numeric>
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class Cat
        {
            public:
                Cat(string const &sep): sep(sep)
                {}
                string operator()(string const &s1, string const &s2)
                {
                    return (s1 + sep + s2);
                }
            private:
                string
                    sep;
        };
        
        int main()
        {
            unsigned
                ia1[] = {1, 2, 3, 4, 5, 6, 7},
                ia2[] = {7, 6, 5, 4, 3, 2, 1},
                init = 0;
        
            cout << "The sum of all squares in ";
            copy(ia1, ia1 + 7, ostream_iterator<unsigned>(cout, " "));
            cout << "is " << 
                inner_product(ia1, ia1 + 7, ia1, init) << endl;
        
            cout << "The sum of all cross-products in ";
            copy(ia1, ia1 + 7, ostream_iterator<unsigned>(cout, " "));
            cout << " and ";
            copy(ia2, ia2 + 7, ostream_iterator<unsigned>(cout, " "));
            cout << "is " << 
                inner_product(ia1, ia1 + 7, ia2, init) << endl;
        
            string
                names1[] = {"Frank", "Karel", "Piet"},
                names2[] = {"Brokken", "Kubat", "Plomp"};
        
            cout << "A list of all combined names in ";
            copy(names1, names1 + 3, ostream_iterator<string>(cout, " "));
            cout << "and\n";
            copy(names2, names2 + 3, ostream_iterator<string>(cout, " "));
            cout << "is:" <<
                inner_product(names1, names1 + 3, names2, string("\t"), 
                    Cat("\n\t"), Cat(" ")) << 
                endl;
        }
        /*
            generated output:
        The sum of all squares in 1 2 3 4 5 6 7 is 140
        The sum of all cross-products in 1 2 3 4 5 6 7  and 7 6 5 4 3 2 1 is 84
        A list of all combined names in Frank Karel Piet and 
        Brokken Kubat Plomp is:   
                Frank Brokken
                Karel Kubat
                Piet Plomp
        */
    
  • 17.4.22: inplace_merge()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
  • void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
  • Description:
  • The first prototype: The two (sorted) ranges [first, middle) and [middle, last) are merged, keeping a sorted list (using the operator<() of the underlying data type). The final series is stored in the range [first, last).
  • The second prototype: The two (sorted) ranges [first, middle) and [middle, last) are merged, keeping a sorted list (using the boolean result of the binaray comparison operator comp). The final series is stored in the range [first, last).
  • Example:
        #include <algorithm>
        #include <string>
        #include <iostream>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return strcasecmp(first.c_str(), second.c_str()) < 0;
                }
        };
        
        int main()
        {
            string
                range[] =
                {
                    "alpha", "charley", "echo", "golf",
                    "bravo", "delta", "foxtrot",
                };
        
            inplace_merge(range, range + 4, range + 7);
            copy(range, range + 7, ostream_iterator<string>(cout, " "));
            cout << endl;
        
            string
                range2[] =
                {
                    "ALFA", "CHARLEY", "DELTA", "foxtrot", "hotel",
                    "bravo", "ECHO", "GOLF"
                };
        
            inplace_merge(range2, range2 + 5, range2 + 8, CaseString());
            copy(range2, range2 + 8, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        alpha bravo charley delta echo foxtrot golf 
        ALFA bravo CHARLEY DELTA ECHO foxtrot GOLF hotel 
        */
    
  • 17.4.23: iter_swap()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • void iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2);
  • Description:
  • The elements pointed to by iter1 and iter2 are swapped.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
    
        int main()
        {
            string
                first[] = {"alpha", "bravo", "charley"},
                second[] = {"echo", "foxtrot", "golf"};
            unsigned
                n = sizeof(first) / sizeof(string);
            
            cout << "Before:\n";
            copy(first, first + n, ostream_iterator<string>(cout, " "));
            cout << endl;
            copy(second, second + n, ostream_iterator<string>(cout, " "));
            cout << endl;
        
            for (unsigned idx = 0; idx < n; ++idx)
                iter_swap(first + idx, second + idx);
        
            cout << "After:\n";
            copy(first, first + n, ostream_iterator<string>(cout, " "));
            cout << endl;
            copy(second, second + n, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        Before:
        alpha bravo charley 
        echo foxtrot golf 
        After:
        echo foxtrot golf 
        alpha bravo charley 
        */
    
  • 17.4.24: lexicographical_compare()

  • Header files:
            #include <algorithm>
    
  • Function prototypes:
  • bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
  • bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
  • Description:
  • The first prototype: The corresponding pairs of elements in the ranges pointed to by [first1, last1) and [first2, last2) are compared. The function returns true
  • at the first element in the first range which is less than the corresponding element in the second range (using the operator<() of the underlying data type),
  • if last1 is reached, but last2 isn't reached yet.
  • False is returned in the other cases, which indicates that the first sequence is not lexicographical less than the second sequence. I.e., false is returned
  • at the first element in the first range which is greater than the corresponding element in the second range (using the operator<() of the underlying data type),
  • if last2 is reached, but last1 isn't reached yet.
  • if last1 and last2 are reached.
  • The second prototype: With this function the binary comparison operation as defined by comp is used instead of the underlying operator<().
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return strcasecmp(first.c_str(), second.c_str()) < 0;
                }
        };
        
        int main()
        {
            string
                word1 = "hello",
                word2 = "help";
        
            cout << word1 << " is " <<
                (
                    lexicographical_compare(word1.begin(), word1.end(),
                                            word2.begin(), word2.end()) ?
                        "before "
                    :
                        "beyond or at "
                ) <<
                word2 << " in the alphabet\n";
                
            cout << word1 << " is " <<
                (
                    lexicographical_compare(word1.begin(), word1.end(),
                                            word1.begin(), word1.end()) ?
                        "before "
                    :
                        "beyond or at "
                ) <<
                word1 << " in the alphabet\n";
                
            cout << word2 << " is " <<
                (
                    lexicographical_compare(word2.begin(), word2.end(),
                                            word1.begin(), word1.end()) ?
                        "before "
                    :
                        "beyond or at "
                ) <<
                word1 << " in the alphabet\n";
                
            string
                one[] = {"alpha", "bravo", "charley"},
                two[] = {"ALPHA", "BRAVO", "DELTA"};
        
            copy(one, one + 3, ostream_iterator<string>(cout, " "));
            cout << " is ordered " <<
                (
                    lexicographical_compare(one, one + 3,
                                            two, two + 3, CaseString()) ?
                        "before "
                    :
                        "beyond or at "
                );
            copy(two, two + 3, ostream_iterator<string>(cout, " "));
            cout << endl <<
                "using case-insensitive comparisons.\n";
        }
        /*
            generated output:
        hello is before help in the alphabet
        hello is beyond or at hello in the alphabet
        help is beyond or at hello in the alphabet
        alpha bravo charley  is ordered before ALPHA BRAVO DELTA 
        using case-insensitive comparisons.
        */
    
  • 17.4.25: lower_bound()

  • Header files:
            #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value);
  • ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value, Compare comp);
  • Description:
  • The first prototype: The sorted elements indicated by the iterator range [first, last) are searched for the first element that is not less than (i.e., greater than or equal to) value. The returned iterator marks the location in the sequence where value can be inserted without breaking the sorted order of the elements. The operator<() of the underlying datatype is used. If no such element is found, last is returned.
  • The second prototype: The elements indicated by the iterator range [first, last) must have been sorted using the comp function (-object). Each element in the range is compared to value using the comp function. An iterator to the first element for which the binary predicate comp, applied to the elements of the range and value, returns false is returned. If no such element is found, last is returned.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <functional>
        
        int main()
        {
            int 
                ia[] = {10, 20, 30};
        
            cout << "Sequence: ";
            copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
            cout << endl;
        
            cout << "15 can be inserted before " <<
                    *lower_bound(ia, ia + 3, 15) << endl;
            cout << "35 can be inserted after " <<
                    (lower_bound(ia, ia + 3, 35) == ia + 3 ? 
                                        "the last element" : "???") << endl;
        
            iter_swap(ia, ia + 2);
        
            cout << "Sequence: ";
            copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
            cout << endl;
        
            cout << "15 can be inserted before " <<
                    *lower_bound(ia, ia + 3, 15, greater<int>()) << endl;
            cout << "35 can be inserted before " <<
                    (lower_bound(ia, ia + 3, 35, greater<int>()) == ia ? 
                                        "the first element " : "???") << endl;
        }
        /*
            generated output:
        Sequence: 10 20 30 
        15 can be inserted before 20
        35 can be inserted after the last element
        Sequence: 30 20 10 
        15 can be inserted before 10
        35 can be inserted before the first element 
        */
    
  • 17.4.26: max()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • Type const &max(Type const &one, Type const &two);
  • Type const &max(Type const &one, Type const &two, Comparator comp);
  • Description:
  • The first prototype: The larger of the two elements one and two is returned, using the operator>() of the underlying type.
  • The second prototype: one is returned if the binary predicate comp(one, two) returns true, otherwise two is returned.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return (strcasecmp(second.c_str(), first.c_str()) > 0);
                }
        };
        
        
        int main()
        {
            cout << "Word '" << max(string("first"), string("second")) << 
                                        "' is lexicographically last\n";
        
            cout << "Word '" << max(string("first"), string("SECOND")) << 
                                        "' is lexicographically last\n";
        
            cout << "Word '" << max(string("first"), string("SECOND"), 
                                CaseString()) << "' is lexicographically last\n";
        }
        /*
            generated output:
        Word 'second' is lexicographically last
        Word 'first' is lexicographically last
        Word 'SECOND' is lexicographically last
        */
    
  • 17.4.27: max_element()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
  • ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Comparator comp);
  • Description:
  • The first prototype: An iterator pointing to the largest element in the range implied by [first, last) is returned. The operator<() of the underlying type is used.
  • The second prototype: rather than using operator<(), the binary predicate comp is used to make the comparisons between the elements implied by the iterator range [first, last). The element for which comp returns most often true, compared with other elements, is returned.
  • Example:
        #include <algorithm>
        #include <iostream>
        
        class AbsValue
        {
            public:
                bool operator()(int first, int second) const
                {
                    return abs(first) < abs(second);
                }
        };
        
        int main()
        {
            int
                ia[] = {-4, 7, -2, 10, -12};
        
            cout << "The max. int value is " << *max_element(ia, ia + 5) << endl;
            cout << "The max. absolute int value is " << 
                    *max_element(ia, ia + 5, AbsValue()) << endl;
        }
        /*
            generated output:
        The max. int value is 10
        The max. absolute int value is -12
        */
    
  • 17.4.28: merge()

  • Header files:
            #include <algorithm>
    
  • Function prototypes:
  • OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
  • OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
  • Description:
  • The first prototype: The two (sorted) ranges [first1, last1) and [first2, last2) are merged, keeping a sorted list (using the operator<() of the underlying data type). The final series is stored in the range starting at result and ending just before the OutputIterator that is returned by the function.
  • The first prototype: The two (sorted) ranges [first1, last1) and [first2, last2) are merged, keeping a sorted list (using the boolean result of the binaray comparison operator comp). The final series is stored in the range starting at result and ending just before the OutputIterator that is returned by the function.
  • Example:
        #include <algorithm>
        #include <string>
        #include <iostream>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return (strcasecmp(first.c_str(), second.c_str()) < 0);
                }
        };
        
        int main()
        {
            string
                range1[] =
                {
                    "alpha", "bravo", "foxtrot", "hotel", "zulu"
                },
                range2[] =
                {
                    "delta", "echo", "golf", "romeo"
                },
                result[5 + 4];
        
            
            copy(result,  
                merge(range1, range1 + 5, range2, range2 + 4, result),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        
            string
                range3[] =
                {
                    "ALPHA", "bravo", "foxtrot", "HOTEL", "ZULU"
                },
                range4[] =
                {
                    "delta", "ECHO", "GOLF", "romeo"
                };
        
            
            copy(result, 
                merge(range3, range3 + 5, range4, range4 + 4, result, 
                                                                CaseString()),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        alpha bravo delta echo foxtrot golf hotel romeo zulu 
        ALPHA bravo delta ECHO foxtrot GOLF HOTEL romeo ZULU 
        */
    
  • 17.4.29: min()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • Type const &min(Type const &one, Type const &two);
  • Type const &min(Type const &one, Type const &two, Comparator comp);
  • Description:
  • The first prototype: The smaller of the two elements one and two is returned, using the operator<() of the underlying type.
  • The second prototype: one is returned if the binary predicate comp(one, two) returns false, otherwise two is returned.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return (strcasecmp(second.c_str(), first.c_str()) > 0);
                }
        };
        
        
        int main()
        {
            cout << "Word '" << min(string("first"), string("second")) << 
                                        "' is lexicographically first\n";
        
            cout << "Word '" << min(string("first"), string("SECOND")) << 
                                        "' is lexicographically first\n";
        
            cout << "Word '" << min(string("first"), string("SECOND"), 
                                CaseString()) << "' is lexicographically first\n";
        }
        /*
            generated output:
        Word 'first' is lexicographically first
        Word 'SECOND' is lexicographically first
        Word 'first' is lexicographically first
        */
    
  • 17.4.30: min_element()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
  • ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Comparator comp);
  • Description:
  • The first prototype: An iterator pointing to the smallest element in the range implied by [first, last) is returned. The operator<() of the underlying type is used.
  • The second prototype: rather than using operator<(), the binary predicate comp is used to make the comparisons between the elements implied by the iterator range [first, last). The element with which comp returns most often false is returned.
  • Example:
        #include <algorithm>
        #include <iostream>
        
        class AbsValue
        {
            public:
                bool operator()(int first, int second) const
                {
                    return abs(first) < abs(second);
                }
        };
        
        
        int main()
        {
            int
                ia[] = {-4, 7, -2, 10, -12};
        
            cout << "The minimum int value is " << *min_element(ia, ia + 5) << 
                    endl;
            cout << "The minimum absolute int value is " << 
                    *min_element(ia, ia + 5, AbsValue()) << endl;
        }
        /*
            generated output:
        The minimum int value is -12
        The minimum absolute int value is -2
        */
    
  • 17.4.31: mismatch()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
  • pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Compare comp);
  • Description:
  • The first prototype: The two sequences of elements starting at first1 and first2 are compared using the equality operator of the underlying data type. Comparison stops if the compared elements differ (i.e., operator==() returns false) or last1 is reached. A pair containing iterators pointing to the final positions is returned. The second sequence may contain more elements than the first sequence. The behavior of the algorithm is undefined if the second sequence contains less elements than the first sequence.
  • The second prototype: The two sequences of elements starting at first1 and first2 are compared using With this function the binary comparison operation as defined by comp is used instead of the underlying operator==(). Comparison stops if the comp function returns false or last1 is reached. A pair containing iterators pointing to the final positions is returned. The second sequence may contain more elements than the first sequence. The behavior of the algorithm is undefined if the second sequence contains less elements than the first sequence.
  • Example:
        #include <algorithm>
        #include <string>
        #include <iostream>
        #include <utility>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return (strcasecmp(first.c_str(), second.c_str()) == 0);
                }
        };
        
        int main()
        {
            string
                range1[] =
                {
                    "alpha", "bravo", "foxtrot", "hotel", "zulu"
                },
                range2[] =
                {
                    "alpha", "bravo", "foxtrot", "Hotel", "zulu"
                };
        
            
            pair<string *, string *>
                pss = mismatch(range1, range1 + 5, range2);
        
            cout << "The elements " << *pss.first << " and " << *pss.second <<
                    " at offset " << (pss.first - range1) << " differ\n";
            if 
            (
                mismatch(range1, range1 + 5, range2, CaseString()).first 
                == range1 + 5
            )
                cout << "When compared case-insensitively they match\n";
        }
        /*
            generated output:
        The elements hotel and Hotel at offset 3 differ
        When compared case-insensitively they match
        */
    
  • 17.4.32: next_permutation()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
  • bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);
  • Description:
  • The first prototype: The next permutation, given the sequence of elements in the range [first, last), is determined. For example, if the elements 1, 2 and 3 are the range for which next_permutation() is called, then subsequent calls of next_permutation() reorders the following series:
            1 2 3 
            1 3 2 
            2 1 3 
            2 3 1 
            3 1 2 
            3 2 1 
    
    This example shows that the elements are reordered such a that each new permutation represents the next bigger value (132 is bigger than 123, 213 is bigger than 132, etc., using operator<() of the underlying data type. The value true is returned if a reordering took place, the value false is returned if no reordering took place, which is the case if the sequence represents the last (biggest) value. In that case, the sequence is also sorted according to the operator<() of the underlying data type.
  • The second prototype: The next permutation given the sequence of elements in the range [first, last) is determined. The elements in the range are reordered. The value true is returned if a reordering took place, the value false is returned if no reordering took place, which is the case if the resulting sequence would haven been ordered, using the binary predicate comp to compare elements. )
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return (strcasecmp(first.c_str(), second.c_str()) < 0);
                }
        };
        
        int main()
        {
            string
                saints[] = {"Oh", "when", "the", "saints"};
        
            cout << "All permutations of 'Oh when the saints':\n";
        
            cout << "Sequences:\n";
            do
            {
                copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
                cout << endl;
            }
            while (next_permutation(saints, saints + 4, CaseString()));
        
        
            cout << "After first sorting the sequence:\n";
        
            sort(saints, saints + 4, CaseString());
        
            cout << "Sequences:\n";
            do
            {
                copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
                cout << endl;
            }
            while (next_permutation(saints, saints + 4, CaseString()));
        }
        /*
            generated output (only partially given):
        All permutations of 'Oh when the saints':
        Sequences:
        Oh when the saints 
        saints Oh the when 
        saints Oh when the 
        saints the Oh when 
        ...
        After first sorting the sequence:
        Sequences:
        Oh saints the when 
        Oh saints when the 
        Oh the saints when 
        Oh the when saints 
        ...
        */
    
  • 17.4.33: nth_element()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
  • void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
  • Description:
  • The first prototype: All elements in the range [first, last) are sorted relative to the element pointed to by nth: all elements in the range [left, nth) are smaller than the element pointed to by nth, and alle elements in the range [nth + 1, last) are greater than the element pointed to by nth. The two subsets themselves are not sorted. The operator<() of the underlying datatype is used.
  • The second prototype: All elements in the range [first, last) are sorted relative to the element pointed to by nth: all elements in the range [left, nth) are smaller than the element pointed to by nth, and alle elements in the range [nth + 1, last) are greater than the element pointed to by nth. The two subsets themselves are not sorted. The comp function object is used to compare the elements.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <functional>
        
        int main()
        {
            int
                ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        
            nth_element(ia, ia + 3, ia + 10);
    
            cout << "sorting with respect to " << ia[3] << endl;
            copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
            cout << endl;
        
            nth_element(ia, ia + 5, ia + 10, greater<int>());
    
            cout << "sorting with respect to " << ia[5] << endl;
            copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        sorting with respect to 4
        1 2 3 4 9 7 5 6 8 10 
        sorting with respect to 5
        10 8 7 9 6 5 3 4 2 1 
        */
    
  • 17.4.34: partial_sort()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
  • void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
  • Description:
  • The first prototype: The middle - first smallest elements are sorted and stored in the [first, middle), using the operator<() of the underlying datatype. The remaining elements of the series remain unsorted, and are stored in [middle, last).
  • The second prototype: The middle - first smallest elements (according to the provided binary predicate comp) are sorted and stored in the [first, middle). The remaining elements of the series remain unsorted.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <functional>
        
        int main()
        {
            int
                ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        
            partial_sort(ia, ia + 3, ia + 10);
    
            cout << "find the 3 smallest elements:\n";
            copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
            cout << endl;
    
            cout << "find the 5 biggest elements:\n";
            partial_sort(ia, ia + 5, ia + 10, greater<int>());
            copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        find the 3 smallest elements:
        1 2 3 7 9 5 4 6 8 10 
        find the 5 biggest elements:
        10 9 8 7 6 1 2 3 4 5 
        */
    
  • 17.4.35: partial_sort_copy()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator dest_first, RandomAccessIterator dest_last);
  • void partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator dest_first, RandomAccessIterator dest_last, Compare comp);
  • Description:
  • The first prototype: The smallest elements in the range [first, last) are copied to the range [dest_first, dest_last), using the operator<() of the underlying datatype. Only the number of elements in the smaller range are copied to the second range.
  • The second prototype: The elements in the range [first, last) are are sorted by the binary predicate comp. The elements for which the predicate returns most often true are copied to the range [dest_first, dest_last). Only the number of elements in the smaller range are copied to the second range.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <functional>
        
        int main()
        {
            int
                ia[] = {1, 10, 3, 8, 5, 6, 7, 4, 9, 2},
                ia2[6];
        
            partial_sort_copy(ia, ia + 10, ia2, ia2 + 6);
        
            copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
            cout << endl;
            cout << "the 6 smallest elements: ";
            copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
            cout << endl;
        
            cout << "the 4 smallest elements to a larger range:\n";
            partial_sort_copy(ia, ia + 4, ia2, ia2 + 6);
            copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
            cout << endl;
        
            cout << "the 4 biggest elements to a larger range:\n";
            partial_sort_copy(ia, ia + 4, ia2, ia2 + 6, greater<int>());
            copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        1 10 3 8 5 6 7 4 9 2 
        the 6 smallest elements: 1 2 3 4 5 6 
        the 4 smallest elements to a larger range:
        1 3 8 10 5 6 
        the 4 biggest elements to a larger range:
        10 8 3 1 5 6 
        */
    
  • 17.4.36: partial_sum()

  • Header files:
    #include <numeric>
    
  • Function prototypes:
  • OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);
  • OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation op);
  • Description:
  • The first prototype: the value of each element in the range [result, <returned OutputIterator>) is obtained by adding the elements in the corresponding range of the range [first, last). The first element in the resulting range will be equal to the element pointed to by first.
  • The second prototype: the value of each element in the range [result, <returned OutputIterator>) is obtained by applying the binary operator op to the previous element in the resulting range and the corresponding element in the range [first, last). The first element in the resulting range will be equal to the element pointed to by first.
  • Example:
        #include <numeric>
        #include <algorithm>
        #include <iostream>
        #include <functional>
        
        int main()
        {
            int
                ia[] = {1, 2, 3, 4, 5},
                ia2[5];
        
            copy(ia2,
                partial_sum(ia, ia + 5, ia2),
                ostream_iterator<int>(cout, " "));
            cout << endl;
        
            copy(ia2,
                partial_sum(ia, ia + 5, ia2, multiplies<int>()),
                ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        1 3 6 10 15 
        1 2 6 24 120 
        */
    
  • 17.4.37: partition()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);
  • Description:
  • All elements in the range [first, last) for which the unary predicate pred evaluates as true are placed before the elements which evaluate as false. The return value points just beyond the last element in the partitioned range for which pred evaluates as true.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class LessThan
        {
            public:
                LessThan(int x): x(x)
                {}
                bool operator()(int value)
                {
                    return (value <= x);
                }
            private:
                int
                    x;
        };
        
        int main()
        {
            int
                ia[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4},
                *split;
        
            split = partition(ia, ia + 10, LessThan(ia[9]));
            cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";
        
            copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        Last element <= 4 is ia[3]
        1 3 4 2 9 10 7 8 6 5 
        */
    
  • 17.4.38: prev_permutation()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
  • bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);
  • Description:
  • The first prototype: The previous permutation given the sequence of elements in the range [first, last) is determined. The elements in the range are reordered in such a way that the first ordering is obtained representing a `smaller' value (see next_permutation() (section 17.4.32) for an example involving the opposite ordering). The value true is returned if a reordering took place, the value false is returned if no reordering took place, which is the case if the provided sequence was already ordered, according to the operator<() of the underlying data type.
  • The second prototype: The previous permutation given the sequence of elements in the range [first, last) is determined. The elements in the range are reordered. The value true is returned if a reordering took place, the value false is returned if no reordering took place, which is the case if the original sequence was already ordered, using the binary predicate comp to compare two elements.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return (strcasecmp(first.c_str(), second.c_str()) < 0);
                }
        };
        
        int main()
        {
            string
                saints[] = {"Oh", "when", "the", "saints"};
        
            cout << "All previous permutations of 'Oh when the saints':\n";
        
            cout << "Sequences:\n";
            do
            {
                copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
                cout << endl;
            }
            while (prev_permutation(saints, saints + 4, CaseString()));
        
        
            cout << "After first sorting the sequence:\n";
        
            sort(saints, saints + 4, CaseString());
        
            cout << "Sequences:\n";
            while (prev_permutation(saints, saints + 4, CaseString()))
            {
                copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
                cout << endl;
            }
            cout << "No (more) previous permutations\n";
        }
        /*
            generated output:
        All previous permutations of 'Oh when the saints':
        Sequences:
        Oh when the saints 
        Oh when saints the 
        Oh the when saints 
        Oh the saints when 
        Oh saints when the 
        Oh saints the when 
        After first sorting the sequence:
        Sequences:
        No (more) previous permutations
        */
    
  • 17.4.39: random_shuffle()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
  • void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator rand);
  • Description:
  • The first prototype: The elements in the range [first, last) are randomly reordered.
  • The second prototype: The elements in the range [first, last) are randomly reordered, using the rand random number generator, which should return an int in the range [0, remaining), where remaining is passed as argument to the operator()() of the rand function object.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <time.h>
        
        class randomGenerator
        {
            public:
                randomGenerator()
                { 
                    srand(static_cast<int>(time(0)));
                }
                int operator()(int remaining) const
                {
                    return (rand() % remaining);
                }
        };
        
        int main()
        {
            string
                words[] = 
                { "kilo", "lima", "mike", "november", "oscar", "papa"};
            unsigned
                size = sizeof(words) / sizeof(string);
        
            random_shuffle(words, words + size);
        
            copy(words, words + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        
            cout << "sorting the words again\n";
            sort(words, words + size);
        
            randomGenerator
                rg;
            random_shuffle(words, words + size, rg);
        
            copy(words, words + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        lima oscar mike november papa kilo 
        sorting the words again
        papa mike oscar kilo lima november 
        */
    
  • 17.4.40: remove()

  • Header file:
    #include <algorithm>
    
  • Function prototype:
  • ForwardIterator remove(ForwardIterator first, ForwardIterator last, Type &value);
  • Description:
  • The elements in the range pointed to by [first, last) are reordered in such a way that all values unequal to value are placed at the beginning of the range. The returned forward iterator points to the first element, after reordering, that can be removed. The range [return value, last) is called the leftover of the algorithm. Note that the leftover may contain other values than value, but these can also safely be removed, as they are also present in the range [first, return value).
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                words[] = 
                { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha", 
                    "oscar", "alpha", "alpha", "papa", "quebec" },
                *removed;
            unsigned
                size = sizeof(words) / sizeof(string);
        
            cout << "Removing all \"alpha\"s:\n";
            removed = remove(words, words + size, "alpha");
            copy(words, removed, ostream_iterator<string>(cout, " "));
            cout << endl
                 << "Trailing elements are:\n";
            copy(removed, words + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        Removing all "alpha"s:
        kilo lima mike november oscar papa quebec 
        Trailing elements are:
        oscar alpha alpha papa quebec 
        */
        
  • 17.4.41: remove_copy()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, Type &value);
  • Description:
  • The elements in the range pointed to by [first, last) not matching value are copied to the range [result, returnvalue), where returnvalue is the value returned by the function. The range [first, last) is not modified.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <functional>
    
        int main()
        {
            string
                words[] = 
                { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha", 
                    "oscar", "alpha", "alpha", "papa", "quebec" };
            unsigned
                size = sizeof(words) / sizeof(string);
            string
                *returnvalue,
                remaining[size - count_if(words, words + size, 
                    bind2nd(equal_to<string>(), string("alpha")))];
        
            returnvalue = remove_copy(words, words + size, remaining, "alpha");
                                                        
            cout << "Removing all \"alpha\"s:\n";
            copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        Removing all "alpha"s:
        kilo lima mike november oscar papa quebec 
        */
    
  • 17.4.42: remove_if()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, UnaryPredicate pred);
  • Description:
  • The elements in the range pointed to by [first, last) are reordered in such a way that all values for which the unary predicate pred evaluates as false are placed at the beginning of the range. The returned forward iterator points to the first element, after reordering, for which pred returns true. The range [returnvalue, last) is called the leftover of the algorithm. The leftover may contain other values than value, but these can also safely be removed, as they are also present in the range [first, returnvalue).
  • Example:
        #include <functional>
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                words[] = 
                { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha", 
                    "oscar", "alpha", "alpha", "papa", "quebec" },
                *removed;
            unsigned
                size = sizeof(words) / sizeof(string);
        
            cout << "Removing all \"alpha\"s:\n";
            removed = remove_if(words, words + size, 
                        bind2nd(equal_to<string>(), string("alpha")));
        
            copy(words, removed, ostream_iterator<string>(cout, " "));
            cout << endl
                 << "Trailing elements are:\n";
            copy(removed, words + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        Removing all "alpha"s:
        kilo lima mike november oscar papa quebec 
        Trailing elements are:
        oscar alpha alpha papa quebec 
        */
    
  • 17.4.43: remove_copy_if()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate pred);
  • Description:
  • The elements in the range pointed to by [first, last) for which the unary predicate pred returns true are copied to the range [result, returnvalue), where returnvalue is the value returned by the function. The range [first, last) is not modified.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <functional>
        
        int main()
        {
            string
                words[] = 
                { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha", 
                    "oscar", "alpha", "alpha", "papa", "quebec" };
            unsigned
                size = sizeof(words) / sizeof(string);
            string
                *returnvalue,
                remaining[size - count_if(words, words + size, 
                            bind2nd(equal_to<string>(), "alpha"))];
        
            returnvalue = remove_copy_if(words, words + size, remaining,
                            bind2nd(equal_to<string>(), "alpha"));
                                                        
            cout << "Removing all \"alpha\"s:\n";
            copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        Removing all "alpha"s:
        kilo lima mike november oscar papa quebec 
        */
    
  • 17.4.44: replace()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator replace(ForwardIterator first, ForwardIterator last, Type &oldvalue, Type &newvalue);
  • Description:
  • All elements equal to oldvalue in the range pointed to by [first, last) are replaced by the value newvalue.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                words[] = 
                { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha", 
                    "oscar", "alpha", "alpha", "papa", "quebec" },
                *removed;
            unsigned
                size = sizeof(words) / sizeof(string);
        
            replace(words, words + size, string("alpha"), string("ALPHA"));
            copy(words, words + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa quebec 
        */
    
  • 17.4.45: replace_copy()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, Type &oldvalue, Type &newvalue);
  • Description:
  • All elements equal to oldvalue in the range pointed to by [first, last) are replaced by the value newvalue in a new range [result, returnvalue), where returnvalue is the return value of the function.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                words[] = 
                { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha", 
                    "oscar", "alpha", "alpha", "papa", "quebec" };
            unsigned
                size = sizeof(words) / sizeof(string);
            string
                remaining[size],
                *returnvalue;
        
            returnvalue = replace_copy(words, words + size, remaining,
                                        string("alpha"), string("ALPHA")); 
                                                        
            copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa quebec 
        */
    
  • 17.4.46: replace_if()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator replace_if(ForwardIterator first, ForwardIterator last, UnaryPredicate pred, Type const &value);
  • Description:
  • The elements in the range pointed to by [first, last) for which the unary predicate pred evaluates as true are replaced by newvalue.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <functional>
        
        int main()
        {
            string
                words[] = 
                { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha", 
                    "oscar", "alpha", "alpha", "papa", "quebec" };
            unsigned
                size = sizeof(words) / sizeof(string);
        
            replace_if(words, words + size, 
                       bind1st(equal_to<string>(), string("alpha")), 
                       string("ALPHA"));
            copy(words, words + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa quebec 
        */
    
  • 17.4.47: replace_copy_if()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • OutputIterator replace_copy_if(ForwardIterator first, ForwardIterator last, OutputIterator result, UnaryPredicate pred, Type const &value);
  • Description:
  • The elements in the range pointed to by [first, last) are copied to the range [result, returnvalue), where returnvalue is the value returned by the function. The elements for which the unary predicate pred returns true are replaced by newvalue. The range [first, last) is not modified.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <functional>
        
        int main()
        {
            string
                words[] = 
                { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha", 
                    "oscar", "alpha", "alpha", "papa", "quebec" };
            unsigned
                size = sizeof(words) / sizeof(string);
            string
                result[size];
                                                        
            replace_copy_if(words, words + size, result, 
                            bind1st(greater<string>(), string("mike")), 
                            string("ALPHA"));
            copy (result, result + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        ALPHA ALPHA ALPHA mike ALPHA november ALPHA oscar ALPHA ALPHA papa quebec 
        */
    
  • 17.4.48: reverse()

  • Header files:
            #include <algorithm>
    
  • Function prototypes:
  • void reverse(BidirectionalIterator first, BidirectionalIterator last);
  • Description:
  • The elements in the range pointed to by [first, last) are reversed.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                line;
        
            while (getline(cin, line))
            {
                reverse(line.begin(), line.end());
                cout << line << endl;
            }
        }
        
  • 17.4.49: reverse_copy()

  • Header files:
            #include <algorithm>
    
  • Function prototypes:
  • OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
  • Description:
  • The elements in the range pointed to by [first, last) are copied to the range [result, returnvalue) in reversed order. The value returnvalue is the value that is returned by the function.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                line;
        
            while (getline(cin, line))
            {
                unsigned
                    size = line.size();
                char
                    copy[size + 1];
        
                cout << "line: " << line << endl <<
                        "reversed: ";
                reverse_copy(line.begin(), line.end(), copy);
                copy[size] = 0;     // 0 is not part of the reversed
                                    // line !
                cout << copy << endl;
            }
        }
    
  • 17.4.50: rotate()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
  • Description:
  • The elements implied by the range [first, middle) are moved to the end of the container, the elements implied by the range [middle, last) are moved to the beginning of the container.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                words[] =
                { "kilo", "lima", "mike", "november", "oscar", "papa",
                  "echo", "foxtrot", "golf", "hotel", "india", "juliet" };
            unsigned const
                size = sizeof(words) / sizeof(string),
                midsize = 6;
        
            rotate(words, words + midsize, words + size);
        
            copy(words, words + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        echo foxtrot golf hotel india juliet kilo lima mike november oscar papa
        */
    
  • 17.4.51: rotate_copy()

  • Header files:
            #include <algorithm>
    
  • Function prototypes:
  • OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
  • Description:
  • The elements implied by the range [middle, last) and then the elements implied by the range [first, middle) are copied to the destination container having range [result, returnvalue), where returnvalue is the iterator returned by the function.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                words[] =
                { "kilo", "lima", "mike", "november", "oscar", "papa", 
                  "echo", "foxtrot", "golf", "hotel", "india", "juliet" };
            unsigned const
                size = sizeof(words) / sizeof(string),
                midsize = 6;
            string
                out[size];
        
            copy(out,
                rotate_copy(words, words + midsize, words + size, out),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        echo foxtrot golf hotel india juliet kilo lima mike november oscar papa 
        */
    
  • 17.4.52: search()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
  • ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
  • Description:
  • The first prototype: An iterator into the first range [first1, last1) is returned where the elements in the range [first2, last2) are found, using operator==() operator of the underlying data type. If no such location exists, last1 is returned.
  • The second prototype: An iterator into the first range [first1, last1) is returned where the elements in the range [first2, last2) are found, using the provided binary predicate pred to compare the elements in the two ranges. If no such location exists, last1 is returned.
  • Example:
        #include <algorithm>
        #include <iostream>
        
        
        class absInt
        {
            public:
                bool operator()(int i1, int i2)
                {
                    return (abs(i1) == abs(i2));
                }
        };
        
        int main()
        {
            int
                range1[] = 
                    {-2, -4, -6, -8, 2, 4, 6, 8},
                range2[] = 
                    {6, 8};
        
            copy
            (
                search(range1, range1 + 8, range2, range2 + 2),
                range1 + 8,
                ostream_iterator<int>(cout, " ")
            );
            cout << endl;
        
            copy
            (
                search(range1, range1 + 8, range2, range2 + 2, absInt()),
                range1 + 8,
                ostream_iterator<int>(cout, " ")
            );
            cout << endl;
        }
        /*
            generated output:
        6 8 
        -6 -8 2 4 6 8 
        */
    
  • 17.4.53: search_n()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1, Size count, Type const & value);
  • ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1, Size count, Type const & value, BinaryPredicate pred);
  • Description:
  • The first prototype: An iterator into the first range [first1, last1) is returned where n elements having value value are found, using operator==() operator of the underlying data type to compare the elements. If no such location exists, last1 is returned.
  • The second prototype: An iterator into the first range [first1, last1) is returned where n elements having value value are found, using the provided binary predicate pred to compare the elements. If no such location exists, last1 is returned.
  • Example:
        #include <algorithm>
        #include <iostream>
        
        class absInt
        {
            public:
                bool operator()(int i1, int i2)
                {
                    return (abs(i1) == abs(i2));
                }
        };
        
        int main()
        {
            int
                range1[] = 
                    {-2, -4, -4, -6, -8, 2, 4, 4, 6, 8},
                range2[] = 
                    {6, 8};
        
            copy
            (
                search_n(range1, range1 + 8, 2, 4),
                range1 + 8,
                ostream_iterator<int>(cout, " ")
            );
            cout << endl;
        
            copy
            (
                search_n(range1, range1 + 8, 2, 4, absInt()),
                range1 + 8,
                ostream_iterator<int>(cout, " ")
            );
            cout << endl;
        }
        /*
            generated output:
        4 4 
        -4 -4 -6 -8 2 4 4 
        */
    
  • 17.4.54: set_difference()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • OutputIterator set_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
  • OutputIterator set_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
  • Description:
  • The first prototype: a sorted sequence of the elements pointed to by the range [first1, last1) that are not present in the range [first2, last2) is returned, starting at [result), and ending at the OutputIterator that is returned by the function. The elements in the two ranges must have been sorted using operator<() of the underlying datatype.
  • The second prototype: a sorted sequence of the elements pointed to by the range [first1, last1) that are not present in the range [first2, last2) is returned, starting at [result), and ending at the OutputIterator that is returned by the function. The elements in the two ranges must have been sorted using the comp function object.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseLess
        {
            public:
                bool operator()(string const &left, string const &right)
                {
                    return (strcasecmp(left.c_str(), right.c_str()) < 0);
                }
        };
        
        int main()
        {
            string
                set1[] = 
                { "kilo", "lima", "mike", "november", 
                    "oscar", "papa", "quebec" },
                set2[] =
                { "papa", "quebec", "romeo"},
                result[7],
                *returned;
        
            copy(result, 
                set_difference(set1, set1 + 7, set2, set2 + 3, result),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        
            string
                set3[] =
                { "PAPA", "QUEBEC", "ROMEO"};
            copy(result, 
                set_difference(set1, set1 + 7, set3, set3 + 3, result,
                CaseLess()),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        kilo lima mike november oscar 
        kilo lima mike november oscar 
        */
    
  • 17.4.55: set_intersection()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
  • OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
  • Description:
  • The first prototype: a sorted sequence of the elements pointed to by the range [first1, last1) that are also present in the ranges [first2, last2) is returned, starting at [result), and ending at the OutputIterator that is returned by the function. The elements in the two ranges must have been sorted using operator<() of the underlying datatype.
  • The second prototype: a sorted sequence of the elements pointed to by the range [first1, last1) that are also present in the ranges [first2, last2) is returned, starting at [result), and ending at the OutputIterator that is returned by the function. The elements in the two ranges must have been sorted using the comp function object.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseLess
        {
            public:
                bool operator()(string const &left, string const &right)
                {
                    return (strcasecmp(left.c_str(), right.c_str()) < 0);
                }
        };
        
        int main()
        {
            string
                set1[] = 
                { "kilo", "lima", "mike", "november", 
                    "oscar", "papa", "quebec" },
                set2[] =
                { "papa", "quebec", "romeo"},
                result[7],
                *returned;
        
            copy(result, 
                set_intersection(set1, set1 + 7, set2, set2 + 3, result),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        
            string
                set3[] =
                { "PAPA", "QUEBEC", "ROMEO"};
            copy(result, 
                set_intersection(set1, set1 + 7, set3, set3 + 3, result,
                CaseLess()),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        papa quebec 
        papa quebec 
        */
    
  • 17.4.56: set_symmetric_difference()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • OutputIterator set_symmetric_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
  • OutputIterator set_symmetric_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
  • Description:
  • The first prototype: a sorted sequence of the elements pointed to by the range [first1, last1) that are not present in the range [first2, last2) and those in the range [first2, last2) that are not present in the range [first1, last1) is returned, starting at [result) and ending at the OutputIterator that is returned by the function. The elements in the two ranges must have been sorted using operator<() of the underlying datatype.
  • The second prototype: a sorted sequence of the elements a sorted sequence of the elements pointed to by the range [first1, last1) that are not present in the range [first2, last2) and those in the range [first2, last2) that are not present in the range [first1, last1) is returned, starting at [result) and ending at the OutputIterator that is returned by the function. The elements in the two ranges must have been sorted using the comp function object.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseLess
        {
            public:
                bool operator()(string const &left, string const &right)
                {
                    return (strcasecmp(left.c_str(), right.c_str()) < 0);
                }
        };
        
        int main()
        {
            string
                set1[] = 
                { "kilo", "lima", "mike", "november", 
                    "oscar", "papa", "quebec" },
                set2[] =
                { "papa", "quebec", "romeo"},
                result[7],
                *returned;
        
            copy(result, 
                set_symmetric_difference(set1, set1 + 7, set2, set2 + 3, result),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        
            string
                set3[] =
                { "PAPA", "QUEBEC", "ROMEO"};
            copy(result, 
                set_symmetric_difference(set1, set1 + 7, set3, set3 + 3, result,
                CaseLess()),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        kilo lima mike november oscar romeo 
        kilo lima mike november oscar ROMEO 
        */
    
  • 17.4.57: set_union()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
  • OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
  • Description:
  • The first prototype: a sorted sequence of the elements pointed to by the range [first1, last1) that are also present in the ranges [first2, last2) is returned, starting at [result), and ending at the OutputIterator that is returned by the function. The elements in the two ranges must have been sorted using operator<() of the underlying datatype.
  • The second prototype: a sorted sequence of the elements pointed to by the range [first1, last1) that are also present in the ranges [first2, last2) is returned, starting at [result), and ending at the OutputIterator that is returned by the function. The elements in the two ranges must have been sorted using the comp function object.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseLess
        {
            public:
                bool operator()(string const &left, string const &right)
                {
                    return (strcasecmp(left.c_str(), right.c_str()) < 0);
                }
        };
        
        int main()
        {
            string
                set1[] = 
                { "kilo", "lima", "mike", "november", 
                    "oscar", "papa", "quebec" },
                set2[] =
                { "papa", "quebec", "romeo"},
                result[7],
                *returned;
        
            copy(result, 
                set_intersection(set1, set1 + 7, set2, set2 + 3, result),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        
            string
                set3[] =
                { "PAPA", "QUEBEC", "ROMEO"};
            copy(result, 
                set_intersection(set1, set1 + 7, set3, set3 + 3, result,
                CaseLess()),
                ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        papa quebec 
        papa quebec 
        */
    
  • 17.4.58: sort()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void sort( RandomAccessIterator first, RandomAccessIterator last);
  • void sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • Description:
  • The first prototype: the elements in the range [first, last) are sorted in ascending order, using operator<() of the underlying datatype.
  • The second prototype: the elements in the range [first, last) are sorted in ascending order, using the comp function object to compare the elements.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <functional>
        
        int main()
        {
            string
                words[] = 
                {"november", "kilo", "mike", "lima", 
                    "oscar", "quebec", "papa"};
        
            sort(words, words + 7);
            copy(words, words + 7, ostream_iterator<string>(cout, " "));
            cout << endl;
        
            sort(words, words + 7, greater<string>());
            copy(words, words + 7, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        kilo lima mike november oscar papa quebec 
        quebec papa oscar november mike lima kilo 
        */
    
  • 17.4.59: stable_partition()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);
  • Description:
  • All elements in the range [first, last) for which the unary predicate pred evaluates as true are placed before the elements which evaluate as false. The relative order of the elements in the container is kept. The return value points just beyond the last element in the partitioned range for which pred evaluates as true.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <functional>
        
        int main()
        {
            int
                org[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4},
                ia[10],
                *split;
        
            copy(org, org + 10, ia);
            split = partition(ia, ia + 10, bind2nd(less_equal<int>(), ia[9]));
            cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";
        
            copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
            cout << endl;
        
            copy(org, org + 10, ia);
            split = stable_partition(ia, ia + 10, 
                                        bind2nd(less_equal<int>(), ia[9]));
            cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";
        
            copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        Last element <= 4 is ia[3]
        1 3 4 2 9 10 7 8 6 5 
        Last element <= 4 is ia[3]
        1 3 2 4 5 7 9 10 8 6 
        */
    
  • 17.4.60: stable_sort()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void stable_sort( RandomAccessIterator first, RandomAccessIterator last);
  • void stable_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • Description:
  • The first prototype: the elements in the range [first, last) are stable-sorted in ascending order, using operator<() of the underlying datatype: the relative order of the equal elements is kept.
  • The second prototype: the elements in the range [first, last) are stable-sorted in ascending order, using the comp function object to compare the elements.
  • Example (annotated below):
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <functional>
        #include <vector>
        
        typedef pair<string, string>    pss;                 // 1 (see the text)
        
        class sortby
        {
            public:
                sortby(string pss::*field)                                  // 2
                :
                    field(field)
                {}
        
                bool operator()(pss const &p1, pss const &p2) const         // 3
                {
                    return p1.*field < p2.*field;
                }
            private:
                string 
                    pss::*field;
        };
        
        ostream &operator<<(ostream &out, pss const &p)                     // 4
        {
            return out << "    " << p.first << " " << p.second << endl;
        }
        
        int main()
        {
            vector<pss>                                                     // 5
                namecity;
        
            namecity.push_back(pss("Hampson",   "Godalming"));
            namecity.push_back(pss("Moran",     "Eugene"));
            namecity.push_back(pss("Goldberg",  "Eugene"));
            namecity.push_back(pss("Moran",     "Godalming"));
            namecity.push_back(pss("Goldberg",  "Chicago"));
            namecity.push_back(pss("Hampson",   "Eugene"));
        
            sort(namecity.begin(), namecity.end(), sortby(&pss::first));    // 6
        
            cout << "sorted by names:\n";
            copy(namecity.begin(), namecity.end(), ostream_iterator<pss>(cout));
            
                                                                            // 7
            stable_sort(namecity.begin(), namecity.end(), sortby(&pss::second));
        
            cout << "sorted by names within sorted cities:\n";
            copy(namecity.begin(), namecity.end(), ostream_iterator<pss>(cout));
        }
        /*
            generated output:
        sorted by names:
            Goldberg Eugene
            Goldberg Chicago
            Hampson Godalming
            Hampson Eugene
            Moran Eugene
            Moran Godalming
        sorted by names within sorted cities:
            Goldberg Chicago
            Goldberg Eugene
            Hampson Eugene
            Moran Eugene
            Hampson Godalming
            Moran Godalming
        */
    
  • Note that the example implements a solution to an often occurring problem: how to sort by multiple hierarchical criteria. The example deserves some extra attention:
    1. First, a typedef is used to reduce the clutter that occur from the repeated use of pair<string, string>.
    2. Then, a class sortby is defined, allowing us to construct an anonymous object which receives a pointer to one of the pair data members that are used for sorting. In this case, as both members are string objects, the constructor can easily be defined: its parameter is a pointer to a string member of the class pair<string, string>.
    3. The operator()() member will receive two pair references, and it will then use the pointer to its members, stored in the sortby object, to compare the appropriate fields of the pairs.
    4. Then, operator<<() is overloaded to be able to insert a pair into an ostream object. This is merely a service function to make life easy.
    5. In main(), first some data is stored in a vector.
    6. Then the first sorting takes place. The least important criterion must be sorted first, and for this a simple sort() will suffice. Since we want the names to be sorted within cities, the names represent the least important criterion, so we sort by names: sortby(&pss::first).
    7. The next important criterion, the cities, are sorted next. Since the relative ordering of the names will not be altered anymore by stable_sort(), the ties that are observed when cities are sorted are solved in such a way that the existing relative ordering will not be broken. So, we end up getting Goldberg in Eugene before Hampson in Eugene, before Moran in Eugene. To sort by cities, we use another anonymous sortby object: sortby(&pss::second).

    17.4.61: swap()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • void swap(Type &object1, Type &object2);
  • Description:
  • The elements object1 and object2 change their values.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                first[] = {"alpha", "bravo", "charley"},
                second[] = {"echo", "foxtrot", "golf"};
            unsigned
                n = sizeof(first) / sizeof(string);
            
            cout << "Before:\n";
            copy(first, first + n, ostream_iterator<string>(cout, " "));
            cout << endl;
            copy(second, second + n, ostream_iterator<string>(cout, " "));
            cout << endl;
        
            for (unsigned idx = 0; idx < n; ++idx)
                swap(first[idx], second[idx]);
        
            cout << "After:\n";
            copy(first, first + n, ostream_iterator<string>(cout, " "));
            cout << endl;
            copy(second, second + n, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        Before:
        alpha bravo charley 
        echo foxtrot golf 
        After:
        echo foxtrot golf 
        alpha bravo charley 
        */
    
  • 17.4.62: swap_ranges()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 result);
  • Description:
  • The elements in the ranges pointed to by [first1, last1) are swapped with the elements in the ranges [result, returnvalue), where returnvalue is the value returned by the function. The two ranges must be disjoint.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        int main()
        {
            string
                first[] = {"alpha", "bravo", "charley"},
                second[] = {"echo", "foxtrot", "golf"};
            unsigned
                n = sizeof(first) / sizeof(string);
            
            cout << "Before:\n";
            copy(first, first + n, ostream_iterator<string>(cout, " "));
            cout << endl;
            copy(second, second + n, ostream_iterator<string>(cout, " "));
            cout << endl;
        
            swap_ranges(first, first + n, second);
        
            cout << "After:\n";
            copy(first, first + n, ostream_iterator<string>(cout, " "));
            cout << endl;
            copy(second, second + n, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        Before:
        alpha bravo charley 
        echo foxtrot golf 
        After:
        echo foxtrot golf 
        alpha bravo charley 
        */
    
  • 17.4.63: transform()

  • Header files:
            #include <algorithm>
    
  • Function prototypes:
  • OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperator op);
  • OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperator op);
  • Description:
  • The first prototype: the unary operator op is applied to each of the elements in the range [first, last), and the resulting values are stored in the range starting at result. The return value points just beyond the last generated element.
  • The second prototype: the binary operator op is applied to each of the elements in the range [first, last) and the corresponding element in the second range starting at first2. The resulting values are stored in the range starting at result. The return value points just beyond the last generated element.
  • Example:
        #include <functional>
        #include <vector>
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <cctype>
        
        class Caps
        {
            public:
                string operator()(string const &src)
                {
                    string
                        tmp = src;
        
                    transform(tmp.begin(), tmp.end(), tmp.begin(), toupper);
                    return tmp;
                }
        };
        
        int main()
        {
            string
                words[] = {"alpha", "bravo", "charley"};
        
            copy(words, transform(words, words + 3, words, Caps()),
                                    ostream_iterator<string>(cout, " "));
            cout << endl;
        
            int
                values[] = {1, 2, 3, 4, 5};
            vector<int>
                squares;
        
            transform(values, values + 5, values, 
                                    back_inserter(squares), multiplies<int>());
        
            copy(squares.begin(), squares.end(), 
                                    ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        ALPHA BRAVO CHARLEY 
        1 4 9 16 25 
        */
    
  • 17.4.64: unique()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator unique(ForwardIterator first, ForwardIterator last);
  • ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
  • Description:
  • The first prototype: Consecutively equal elements (using operator==() of the underlying data type) in the range pointed to by [first, last) are collapsed into a single element. The returned forward iterator marks the leftover of the algorithm, and contains (unique) elements appearing earlier in the range.
  • The second prototype: Consecutive elements in the range pointed to by [first, last) for which the binary predicate pred returns true are collapsed into a single element. The returned forward iterator marks the leftover of the algorithm, and contains (unique) elements appearing earlier in the range.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return (!strcasecmp(first.c_str(), second.c_str()));
                }
        };
        
        int main()
        {
            string
                words[] = 
                {"alpha", "alpha", "Alpha", "papa", "quebec" },
                *removed;
            unsigned
                size = sizeof(words) / sizeof(string);
        
            removed = unique(words, words + size);
            copy(words, removed, ostream_iterator<string>(cout, " "));
            cout << endl
                 << "Trailing elements are:\n";
            copy(removed, words + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        
            removed = unique(words, words + size, CaseString());
            copy(words, removed, ostream_iterator<string>(cout, " "));
            cout << endl
                 << "Trailing elements are:\n";
            copy(removed, words + size, ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        alpha Alpha papa quebec 
        Trailing elements are:
        quebec 
        alpha papa quebec 
        Trailing elements are:
        quebec quebec 
        */
    
  • 17.4.65: unique_copy()

  • Header file:
    #include <algorithm>
    
  • Function prototypes:
  • OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);
  • OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator Result, BinaryPredicate pred);
  • Description:
  • The first prototype: The elements in the range [first, last) are copied to the resulting container, starting at result. Consecutively equal elements (using operator==() of the underlying data type) are copied only once. The returned output iterator points just beyond the last element that was copied.
  • The second prototype: The elements in the range [first, last) are copied to the resulting container, starting at result. Consecutive elements in the range pointed to by [first, last) for which the binary predicate pred returns true are copied only once. The returned output iterator points just beyond the last element that was copied.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <string>
        #include <vector>
        #include <functional>
        
        class CaseString
        {
            public:
                bool operator()(string const &first, string const &second) const
                {
                    return (!strcasecmp(first.c_str(), second.c_str()));
                }
        };
        
        int main()
        {
            string
                words[] = {"oscar", "Alpha", "alpha", "alpha", "papa", "quebec" };
            unsigned
                size = sizeof(words) / sizeof(string);
            vector<string>
                remaining;
        
            unique_copy(words, words + size, 
                                    back_inserter(remaining));
                                                        
            copy(remaining.begin(), remaining.end(), 
                    ostream_iterator<string>(cout, " "));
            cout << endl;
        
            vector<string>
                remaining2;
        
            unique_copy(words, words + size, 
                                    back_inserter(remaining2), CaseString());
                                                        
            copy(remaining2.begin(), remaining2.end(), 
                    ostream_iterator<string>(cout, " "));
            cout << endl;
        }
        /*
            generated output:
        oscar Alpha alpha papa quebec 
        oscar Alpha papa quebec 
        */
    
  • 17.4.66: upper_bound()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const Type &value);
  • ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const Type &value, Compare comp);
  • Description:
  • The first prototype: The sorted elements stored in the iterator range [first, last) are searched for the first element that is greater than value. The returned iterator marks the location in the sequence where value can be inserted without breaking the sorted order of the elements, using operator<() of the underlying datatype. If no such element is found, last is returned.
  • The second prototype: The elements implied by the iterator range [first, last) must have been sorted using the comp function (-object). Each element in the range is compared to value using the comp function. An iterator to the first element for which the binary predicate comp, applied to the elements of the range and value, returns true is returned. If no such element is found, last is returned.
  • Example:
        #include <algorithm>
        #include <iostream>
        #include <functional>
        
        int main()
        {
            int 
                ia[] = {10, 15, 15, 20, 30};
            unsigned
                n = sizeof(ia) / sizeof(int);
    
            cout << "Sequence: ";
            copy(ia, ia + n, ostream_iterator<int>(cout, " "));
            cout << endl;
        
            cout << "15 can be inserted before " <<
                    *upper_bound(ia, ia + n, 15) << endl;
            cout << "35 can be inserted after " <<
                    (upper_bound(ia, ia + n, 35) == ia + n ? 
                                        "the last element" : "???") << endl;
        
            sort(ia, ia + n, greater<int>());
        
            cout << "Sequence: ";
            copy(ia, ia + n, ostream_iterator<int>(cout, " "));
            cout << endl;
        
            cout << "15 can be inserted before " <<
                    *upper_bound(ia, ia + n, 15, greater<int>()) << endl;
            cout << "35 can be inserted before " <<
                    (upper_bound(ia, ia + n, 35, greater<int>()) == ia ? 
                                        "the first element " : "???") << endl;
        }
        /*
            generated output:
        Sequence: 10 15 15 20 30 
        15 can be inserted before 20
        35 can be inserted after the last element
        Sequence: 30 20 15 15 10 
        15 can be inserted before 10
        35 can be inserted before the first element 
        */
    
  • 17.4.67: Heap algorithms

    A heap is a form of binary tree represented as an array. In the standard heap, the key of an element is greater or equal to the key of its children. This kind of heap is called a max heap. A tree in which numbers are keys could be organized as follows:

    figure 17 is shown here.
    figure 17: A binary tree representation of a heap


    This tree can be organized in an array as follows:

    12, 11, 10, 8, 9, 7, 6, 1, 2, 4, 3, 5

    Here, 12 is the top node. its children are 11 and 10, both less than 12. 11, in turn, has 8 and 9 as its children, while the children of 10 are 7 and 6. 8 has 1 and 2 as its children, 9 has 4 and 3, and finally, 7 has left child 5. 7 doesn't have a right child, and 6 has no children.

    Note that the left and right branches are not ordered: 8 is less than 9, but 7 is larger than 6.

    The heap is formed by traversing a binary tree level-wise, starting from the top node. The top node is 12, at the zeroth level. At the first level we find 11 and 10. At the second level 6, 7, 8 and 9 are found, etc.

    Heaps can be created in containers supporting random access. So, a heap is not, for example, constructed in a list. Heaps can be constructed from an (unsorted) array (using make_heap()). The top-element can be pruned from a heap, followed by reordering the heap (using pop_heap()), a new element can be added to the heap, followed by reordering the heap (using push_heap()), and the elements in a heap can be sorted (using sort_heap(), which invalidates the heap, though).

    The following subsections introduce the prototypes of the heap-algorithms, the final subsection provides a small example in which the heap algorithms are used.

    17.4.67.1: make_heap()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void make_heap(RandomAccessIterator first, RandomAccessIterator last);
  • void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • Description:
  • The first prototype: The elements in the range [first, last) are reordered to form a max-heap, using operator<() of the underlying data type.
  • The second prototype: The elements in the range [first, last) are reordered to form a heap, using the binary comparison function object comp to compare elements.
  • Follow this link for a small example of a program using make_heap().
  • 17.4.67.2: pop_heap()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
  • void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • Description:
  • The first prototype: The first element in the range [first, last) is moved to last - 1. Then, the elements in the range [first, last - 1) are reordered to form a max-heap, using the operator<() of the underlying data type.
  • The second prototype: The first element in the range [first, last) is moved to last - 1. Then, the elements in the range [first, last - 1) are reordered to form a heap, using the binary comparison function object comp to compare elements.
  • Follow this link for a small example of a program using pop_heap().
  • 17.4.67.3: push_heap()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void push_heap(RandomAccessIterator first, RandomAccessIterator last);
  • void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • Description:
  • The first prototype: Assuming that the range [first, last - 2) contains a valid heap, and the element at last - 1 contains an element to be added to the heap, the elements in the range [first, last - 1) are reordered to form a max-heap, using the operator<() of the underlying data type.
  • The second prototype: Assuming that the range [first, last - 2) contains a valid heap, and the element at last - 1 contains an element to be added to the heap, the elements in the range [first, last - 1) are reordered to form a heap, using the binary comparison function object comp to compare elements.
  • Follow this link for a small example of a program using push_heap().

  • 17.4.67.4: sort_heap()

  • Header files:
    #include <algorithm>
    
  • Function prototypes:
  • void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
  • void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • Description:
  • The first prototype: Assuming the elements in the range [first, last) form a valid max-heap, the elements in the range [first, last) are sorted, using operator<() of the underlying data type.
  • The second prototype: Assuming the elements in the range [first, last) form a valid heap, the elements in the range [first, last) are sorted, using the binary comparison function object comp to compare elements.
  • Follow this link for a small example of a program using sort_heap().

  • 17.4.67.5: An example using the heap algorithms

        #include <algorithm>
        #include <iostream>
        #include <functional>
        
        void show(int *ia, char const *header)
        {
            cout << header << ":\n";
            copy(ia, ia + 20, ostream_iterator<int>(cout, " "));
            cout << endl;
        }
        
        int main()
        {
            int
                ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
                        11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        
            make_heap(ia, ia + 20);
            show(ia, "The values 1-20 in a max-heap");
        
            pop_heap(ia, ia + 20);
            show(ia, "Removing the first element (now at the end)");
        
            push_heap(ia, ia + 20);
            show(ia, "Adding 20 (at the end) to the heap again");
        
            sort_heap(ia, ia + 20);
            show(ia, "Sorting the elements in the heap");
    
        
            make_heap(ia, ia + 20, greater<int>());
            show(ia, "The values 1-20 in a heap, using > (and beyond too)");
        
            pop_heap(ia, ia + 20, greater<int>());
            show(ia, "Removing the first element (now at the end)");
        
            push_heap(ia, ia + 20, greater<int>());
            show(ia, "Adding 20 (at the end) to the heap again");
        
            sort_heap(ia, ia + 20, greater<int>());
            show(ia, "Sorting the elements in the heap");
        }
        /*
            generated output:
        The values 1-20 in a max-heap:
        20 19 15 18 11 13 14 17 9 10 2 12 6 3 7 16 8 4 1 5 
        Removing the first element (now at the end):
        19 18 15 17 11 13 14 16 9 10 2 12 6 3 7 5 8 4 1 20 
        Adding 20 (at the end) to the heap again:
        20 19 15 17 18 13 14 16 9 11 2 12 6 3 7 5 8 4 1 10 
        Sorting the elements in the heap:
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
        The values 1-20 in a heap, using > (and beyond too):
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
        Removing the first element (now at the end):
        2 4 3 8 5 6 7 16 9 10 11 12 13 14 15 20 17 18 19 1 
        Adding 20 (at the end) to the heap again:
        1 2 3 8 4 6 7 16 9 5 11 12 13 14 15 20 17 18 19 10 
        Sorting the elements in the heap:
        20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
        */