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.2.0a) 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 is 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<std::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. It will call the operator>() of the provided data type (here std::string) wheneven its operator()() is called.

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>

    using namespace std;
    
    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>

    using namespace std;
    
    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>

    using namespace std;
    
    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 <sstream>
    #include <string>
    #include <vector>
    #include <functional>
    #include <numeric>
    
    using namespace std;

    class Time
    {
        friend ostream &operator<<(ostream &str, Time const &time)
        {
            return cout << time.d_days << " days, " << time.d_hours << ":" << 
                            time.d_minutes << ":" << time.d_seconds;
        }

        unsigned
            d_days,
            d_hours,
            d_minutes,
            d_seconds;

        public:
            Time(unsigned hours, unsigned minutes, unsigned seconds)
            :
                d_days(0),
                d_hours(hours),
                d_minutes(minutes),
                d_seconds(seconds)
            {}

            Time(Time const &other)
            :
                d_days(other.d_days),
                d_hours(other.d_hours),
                d_minutes(other.d_minutes),
                d_seconds(other.d_seconds)
            {}

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

                added.d_seconds   += rValue.d_seconds;
                added.d_minutes   += rValue.d_minutes   + added.d_seconds / 60;
                added.d_hours     += rValue.d_hours     + added.d_minutes / 60;
                added.d_days      += rValue.d_days      + added.d_hours   / 24;
                added.d_seconds   %= 60;
                added.d_minutes   %= 60;
                added.d_hours     %= 24;

                return added;
            } 
    };
    
    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:

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>
    
    using namespace std;

    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: 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>
    
    using namespace std;

    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: 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>

    using namespace std;
    
    int main(int argc, char **argv)
    {
        bool
            bArr[] = {true, true, true, false, false, false};
        unsigned const
            bArrSize = sizeof(bArr) / sizeof(bool);
    
        for (unsigned idx = 0; idx < bArrSize; ++idx)
            cout << bArr[idx] << " ";
        cout << endl;
    
        transform(bArr, bArr + bArrSize, bArr, logical_not<bool>());
    
        for (unsigned 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: 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:

17.2: Iterators

Iterators are an abstraction of pointers. In general, the following holds true for iterators: 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>
    
    using namespace std;
    
    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>

    using namespace std;
    
    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;

        return 0;
    }
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:

The following types of iterators are used with the generic algorithms: 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:

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>

    using namespace std;
        
    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;

        return 0;
    }
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 implied 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: 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>

    using namespace std;
    
    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));

        return 0;
    }
In order to use the ostream_iterator adaptor, sources must 
    #include <iterator>
This is implied 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: 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);

        return 0;
    }

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 a std::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 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:

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>

    using namespace std;

    void fun()
    {
        auto_ptr<int> ip(new int[200]);
    }
Note that the elements of the allocated array are not class-type objects, but primitive int value. Hence an array can be allocated for the auto_ptr<int> ip.

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 <memory>

    using namespace std;

    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>

    using namespace std;

    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: The following member functions are defined for auto_ptr objects:

17.4: The Generic Algorithms

The following sections describe the generic algorithms in alphabetical order. For each algorithm the following information is provided: The generic algorithms are part of the standard namespace. So, they should be used with their std:: namespace prefix, a using directive or a using declaration should be used.

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 usually receive Type const & objects or values: function objects can therefore not modify the objects they receive as their arguments. This does not hold true for modifying generic algorithms, which (of course) are able to modify the objects they operate upon.

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

17.4.1: accumulate()

17.4.2: adjacent_difference()

17.4.3: adjacent_find()

17.4.4: binary_search()

17.4.5: copy()

17.4.6: copy_backward()

17.4.7: count()

17.4.8: count_if()

17.4.9: equal()

17.4.10: equal_range()

17.4.11: fill()

17.4.12: fill_n()

17.4.13: find()

17.4.14: find_if()

17.4.15: find_end()

17.4.16: find_first_of()

17.4.17: for_each()

The example also shows that the for_each algorithm may be used with functions defining const and non-const parameters. Also, see section 17.4.63 for differences between the for_each() and transform() generic algorithms.

17.4.18: generate()

17.4.19: generate_n()

17.4.20: includes()

17.4.21: inner_product()

17.4.22: inplace_merge()

17.4.23: iter_swap()

17.4.24: lexicographical_compare()

17.4.25: lower_bound()

17.4.26: max()

17.4.27: max_element()

17.4.28: merge()

17.4.29: min()

17.4.30: min_element()

17.4.31: mismatch()

17.4.32: next_permutation()

17.4.33: nth_element()

17.4.34: partial_sort()

17.4.35: partial_sort_copy()

17.4.36: partial_sum()

17.4.37: partition()

17.4.38: prev_permutation()

17.4.39: random_shuffle()

17.4.40: remove()

17.4.41: remove_copy()

17.4.42: remove_if()

17.4.43: remove_copy_if()

17.4.44: replace()

17.4.45: replace_copy()

17.4.46: replace_if()

17.4.47: replace_copy_if()

17.4.48: reverse()

17.4.49: reverse_copy()

17.4.50: rotate()

17.4.51: rotate_copy()

17.4.52: search()

17.4.53: search_n()

17.4.54: set_difference()

17.4.55: set_intersection()

17.4.56: set_symmetric_difference()

17.4.57: set_union()

17.4.58: sort()

17.4.59: stable_partition()

17.4.60: stable_sort()

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

17.4.62: swap_ranges()

17.4.63: transform()

Compared to the for_each (section 17.4.17) generic algorithm, the following differences between the for_each() and transform() generic algorithms should be noted:

17.4.64: unique()

17.4.65: unique_copy()

17.4.66: upper_bound()

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 18 is shown here.
figure 18: 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()

17.4.67.2: pop_heap()

17.4.67.3: push_heap()

17.4.67.4: sort_heap()

17.4.67.5: An example using the heap algorithms

    #include <algorithm>
    #include <iostream>
    #include <functional>
    
    using namespace std;
    
    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");

        return 0;
    }
    /*
        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 
    */