Chapter 17: The Standard Template Library, generic algorithms

Don't hesitate to send in feedback: send an e-mail if you like the C++ Annotations; if you think that important material was omitted; if you find errors or typos in the text or the code examples; or if you just feel like e-mailing. Send your e-mail to Frank B. Brokken.

Please state the document version you're referring to, as found in the title (in this document: 6.2.3) and please state chapter and paragraph name or number you're referring to.

All received mail is processed conscientiously, and received suggestions for improvements will usually have been processed by the time a new version of the Annotations is released. Except for the incidental case I will normally not acknowledge the receipt of suggestions for improvements. Please don't interpret this as me not appreciating your efforts.

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 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 templates is not discussed (see chapter 18 for that). Rather, this chapter focuses on the use of these template algorithms.

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.10 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 is 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.

All elements of the STL are defined in the standard namespace. Therefore, a using namespace std or comparable directive is required unless it is preferred to specify the required namespace explicitly. This holds true in at least one situation: in header files no using directive should be used, so here the std:: scope specification should always be specified when referring to elements of the STL.

17.1: Predefined function objects

Function objects play important roles in combination with generic algorithms. For example, there exists a generic algorithm sort() expecting two iterators defining the range of objects that should be sorted, as well as 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. Eventually, when sort() returns, the first element of the vector will be the greatest element.

The operator()() ( function call operator) itself is not visible at this point: don't confuse the parentheses in greater<string>() with calling operator()(). When that operator is actually used inside sort(), it receives two arguments: two strings to compare for `greaterness'. Internally, the operator>() of the data type to which the iterators point (i.e., string) is called by greater<string>'s function operator (operator()()) to compare the two objects. Since greater<>'s function call operator 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 sort()'s final argument. 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 when called by 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 many commonly used 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. Before predefined function objects can be used the following preprocessor directive must have been specified: 

    #include <functional>
Predefined function objects are used predominantly with generic algorithms. Predefined function objects exists for arithmetic, relational, and logical operations. In section 20.4 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. These predefined arithmetic function objects invoke the corresponding operator of the associated data type. 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 with all kinds of data types (not only with 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, in turn on each element of an array. 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>(). Note here 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 <<
                                                        " hours, " <<
                            time.d_minutes << " minutes and " <<
                            time.d_seconds << " seconds.";
        }

        unsigned d_days;
        unsigned d_hours;
        unsigned d_minutes;
        unsigned d_seconds;

        public:
            Time(unsigned hours, unsigned minutes, unsigned seconds)
            :
                d_days(0),
                d_hours(hours),
                d_minutes(minutes),
                d_seconds(seconds)
            {}
            Time &operator+=(Time const &rValue)
            {
                d_seconds   += rValue.d_seconds;
                d_minutes   += rValue.d_minutes   + d_seconds / 60;
                d_hours     += rValue.d_hours     + d_minutes / 60;
                d_days      += rValue.d_days      + d_hours   / 24;
                d_seconds   %= 60;
                d_minutes   %= 60;
                d_hours     %= 24;

                return *this;
            }
    };
    Time const operator+(Time const &lValue, Time const &rValue)
    {
        return Time(lValue) += rValue;
    }

    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 hours, 51 minutes and 30 seconds.
    */
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 Time's operator+=() 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 a constructor, it defines an insertion operator and it defines its own operator+(), adding two time objects.

In main() 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 are called by 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 of the data type to which the iterators point. 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 promotion from char const * to string is performed silently.

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 operator!() is provided in the following trivial program, 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: One may wonder which of these alternative approaches is fastest. Using the first approach, in which a directly available function object was used, two actions must be performed for each iteration by count_if(): Using the second appproach, in which the not2 negator is used to negate the truth value of the complementary logical function adaptor, three actions must be performed for each iteration by count_if(): Using the third appproach, in which a not1 negator is used to negate the truth value of the binder, three actions must be performed for each iteration by count_if(): From this, one might deduct that the first approach is fastest. Indeed, using Gnu's g++ compiler on an old, 166 MHz pentium, performing 3.000.000 count_if() calls for each variant, shows the first approach requiring about 70% of the time needed by the other two approaches to complete.

However, these differences disappear if the compiler is instructed to optimize for speed (using the -O6 compiler flag). When interpreting these results one should keep in mind that multiple nested function calls are merged into a single function call if the implementations of these functions are given inline and if the compiler follows the suggestion to implement these functions as true inline functions indeed. If this is happening, the three approaches all merge to a single operation: the comparison between two int values. It is likely that the compiler does so when asked to optimize for speed.

17.2: Iterators

Iterators are ojects acting like pointers. Iterators have the following general characteristics: 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. Note that with empty containers the begin- and end-iterators are equal to each other.

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 series of 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)
    {
        vector<string> const 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 that plain pointers can be used instead of 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 characteristics. In general, iterators must define:

The following types of iterators are used when describing generic algorithms later in this chapter: The example given with the RandomAccessIterator illustrates how to approach approach towards iterators 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 defining the range of visited elements, and the third parameter defines the first position where the results of the copy operation should be stored. With the copy() algorithm the number of elements that are copied are usually available beforehand, since the number is usually determined using pointer arithmetic. However, there are situations where pointer arithmetic cannot be used. Analogously, the number of resulting elements sometimes differs 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 types of inserter() adaptors:

Concentrating on the back_inserter(), this iterator expects the name of a container having a member push_back(). This member is called by the inserter's operator()() member. When a class (other than the abstract containers) supports a push_back() container, its objects can also be used as arguments of the back_inserter() if the class defines a 
    typedef DataType const &const_reference;
in its interface, where DataType const & is the type of the parameter of the class' member function push_back(). For example, the following program defines a (compilable) skeleton of a class IntStore, whose objects can be used as arguments of the back_inserter iterator: 
    #include <algorithm>
    #include <iterator>
    using namespace std;

    class Y
    {
        public:
            typedef int const &const_reference;

            void push_back(int const &)
            {}
    };

    int main()
    {
        int arr[] = {1};
        Y y;

        copy(arr, arr + 1, back_inserter(y));
    }

17.2.2: Iterators for `istream' objects

The istream_iterator<Type>() can be used to define an iterator (pair) for istream objects. 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 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 was specified for the begin-iterator is not mentioned here.

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));
Before istream_iterators can be used the following preprocessor directive must have been specified: 
    #include <iterator>
This is implied when iostream is included.

17.2.3: Iterators for `istreambuf' objects

Input iterators are also available for streambuf objects. Before istreambuf_iterators can be used the following preprocessor directive must have been specified: 
    #include <iterator>
The istreambuf_iterator is available for reading from streambuf objects supporting input operations. The standard operations that are available for istream_iterator objects are also available for istreambuf_iterators. There are three constructors: In section 17.2.4.1 an example is given using both istreambuf_iterators and ostreambuf_iterators.

17.2.4: Iterators for `ostream' objects

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:
    ostream_iterator<Type> identifier(ostream &outStream, char const *delim);
Type is the type of the data elements that should be written to the ostream stream. Type may be any type for which operator<<() is defined in combinations 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 following example shows how istream_iterators and an ostream_iterator may be used 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]);
        ofstream out(argv[2]);

        in.unsetf(ios::skipws);
        copy(istream_iterator<char>(in), istream_iterator<char>(),
             ostream_iterator<char>(out));

        return 0;
    }
Before ostream_iterators can be used the following preprocessor directive must have been specified: 
    #include <iterator>

17.2.4.1: Iterators for `ostreambuf' objects Before an ostreambuf_iterator can be used the following preprocessor directive must have been specified: 

    #include <iterator>
The ostreambuf_iterator is available for writing to streambuf objects supporting output operations. The standard operations that are 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>
    #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 class 'auto_ptr'

One of the problems using pointers is that strict bookkeeping is required about their memory use and lifetime. 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(): the allocated int value remains inaccessibly allocated: 
    void fun()
    {
        new int;
    }
To prevent memory leaks strict bookkeeping is required: 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;
    }
Now fun() only wastes a bit of time.

When a pointer variable points to a single value or object, the bookkeeping requirements may be relaxed when the pointer variable is defined as a std::auto_ptr object. Auto_ptrs are objects, masquerading as pointers. Since they're objects, their destructors are called when they go out of scope, and because of that, their destructors will take the responsibility of deleting the dynamically allocated memory.

Before auto_ptrs can be used the following preprocessor directive must have been specified: 

    #include <memory>
Normally, an auto_ptr object is initialized using a dynamically created value or object.

The following restrictions apply to auto_ptrs:

The class auto_ptr defines several member functions 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 next 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 allocated by operator new operator. The generic form is: 
    auto_ptr<type> identifier(new-expression);
For example, to initialize an auto_ptr to point to a string object the following construction can be used: 
    auto_ptr<string> strPtr(new string("Hello world"));
To initialize an auto_ptr to point to a double value the following construction can be used: 
    auto_ptr<double> dPtr(new double(123.456));
Note the use of operator new in the above expressions. Using 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 as used in the new expression.

In the example allocating an int values given in section 17.3, the memory leak can be avoided using an auto_ptr object: 

    #include <memory>
    using namespace std;

    void fun()
    {
        auto_ptr<int> ip(new int);
    }
All member functions available for objects 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'

An auto_ptr may also be initialized by 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<string>, given the variable sp defined in the previous section, the following construction can be used: 
    auto_ptr<string> strPtr(sp);
Analogously, the assignment operator can be used. An 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"));
        auto_ptr<string> hello2(hello1);
        auto_ptr<string> hello3;

        hello3 = hello2;
        cout << *hello1 << endl <<
                *hello2 << endl <<
                *hello3 << endl;
    }
    /*
        Produced output:

        Segmentation fault
    */
Looking at the above example, we see that The program generates a segmentation fault. The reason for this will now be clear: it is caused by dereferencing 0-pointers. At the end, only hello3 actually points to a string.

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 not pointing 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 next section.

17.3.5: Operators and members

The following operators are defined for the class auto_ptr: The following member functions are defined for auto_ptr objects:

17.3.6: Constructors and pointer data members

Now that the auto_ptr's main features have been described, consider the following simple class: 
    // required #includes

    class Map
    {
        std::map<string, Data> *d_map;
        public:
            Map(char const *filename) throw(std::exception);
    };
The class' constructor Map() performs the following tasks: Of course, it may not be possible to open the file. In that case an appropriate exception is thrown. So, the constructor's implementation will look somewhat like this: 
    Map::Map(char const *fname)
    :
        d_map(new std::map<std::string, Data>) throw(std::exception)
    {
        ifstream istr(fname);
        if (!istr)
            throw std::exception("can't open the file");
        fillMap(istr);
    }
What's wrong with this implementation? Its main weakness is that it hosts a potential memory leak. The memory leak only occurs when the exception is actually thrown. In all other cases, the function operates perfectly well. When the exception is thrown, the map has just been dynamically allocated. However, even though the class' destructor will dutifully call delete d_map, the destructor is actually never called, as the destructor will only be called to destroy objects that were constructed completely. Since the constructor terminates in an exception, its associated object is not constructed completely, and therefore that object's destructor is never called.

Auto_ptrs may be used to prevent these kinds of problems. By defining d_map as 

        std::auto_ptr<std::map<std::string, Data> >
it suddenly changes into an object. Now, Map's constructor may safely throw an exception. As d_map is an object itself, its destructor will be called by the time the (however incompletely constructed) Map object goes out of scope.

As a rule of thumb: classes should use auto_ptr objects, rather than plain pointers for their pointer data members if there's any chance that their constructors will end prematurely in an exception.

17.4: The Generic Algorithms

The following sections describe the generic algorithms in alphabetical order. For each algorithm the following information is provided: In the prototypes of the algorithms Type is used to specify a generic data type. Also, the particular type of iterator (see section 17.2) that is required is mentioned, as well as other generic types that might be required (e.g., performing BinaryOperations, like plus<Type>()).

Almost every generic algorithm expects 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, function objects used by the algorithms 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 are (of course) 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_end()

17.4.15: find_first_of()

17.4.16: find_if()

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.

The for_each() algorithm cannot directly be used (i.e., by passing *this as the function object argument) inside a member function to modify its own object as the for_each() algorithm first creates it own copy of the passed function object. A wrapper class whose constructor accepts a pointer or reference to the current object and possibly to one of its member functions solves this problem. In section 20.7 the construction of such wrapper classes is described.

17.4.18: generate()

17.4.19: generate_n()

17.4.20: includes()

17.4.21: inner_product()