Chapter 18: The Standard Template Library

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: 10.0.0) and please state chapter and paragraph name or number you're referring to.

All received mail is processed conscientiously, and received suggestions for improvements are usually 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) is a general purpose library consisting of containers, generic algorithms, iterators, function objects, allocators, adaptors and data structures. The data structures used by the algorithms are abstract in the sense that the algorithms can be used with (practically) any data type.

The algorithms can process these abstract data types because they are template based. This chapter does not cover template construction (see chapter 21 for that). Rather, it focuses on the use of the algorithms.

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

The main components of the STL are covered in this and the next chapter. Iterators, adaptors, smart pointers, multi threading and other features of the STL are discussed in coming sections. Generic algorithms are covered in the next chapter (19).

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.

All elements of the STL are defined in the standard namespace. Therefore, a using namespace std or a comparable directive is required unless it is preferred to specify the required namespace explicitly. In header files the std namespace should explicitly be used (cf. section 7.12.1).

In this chapter the empty angle bracket notation is frequently used. In code a typename must be supplied between the angle brackets. E.g., plus<> is used in the C++ Annotations, but in code plus<string> may be encountered.

18.1: Predefined function objects

Before using the predefined function objects presented in this section the <functional> header file must be included.

Function objects play important roles in 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<string>());
The last argument is recognized as a constructor: it is an instantiation of the greater<> class template, applied to strings. This object is called as a function object by the sort generic algorithm. The generic algorithm calls the function object's operator() member to compare two string objects. The function object's operator() will, in turn, call operator> of the string data type. Eventually, when sort returns, the first element of the vector will contain the string having the greatest string value of all.

The function object's operator() itself is not visible at this point. Don't confuse the parentheses in the `greater<string>()' argument with calling operator(). When operator() is actually used inside sort, it receives two arguments: two strings to compare for `greaterness'. Since greater<string>::operator() is defined inline, the call itself is not actually present in the above sort call. Instead sort calls string::operator> through greater<string>::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 CaseInsensitive class, which compares two strings case insensitively. Using the POSIX function strcasecmp, the following program performs the trick. It case-insensitively sorts its command-line arguments in ascending alphabetic order:

    #include <iostream>
    #include <string>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    class CaseInsensitive
    {
        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, CaseInsensitive());
        for (int idx = 0; idx < argc; ++idx)
            cout << argv[idx] << " ";
        cout << '\n';
    }

The default constructor of the class CaseInsensitive is used to provide sort with its final argument. So the only member function that must be defined is CaseInsensitive::operator(). Since we know it's called with string arguments, we define it to expect two string arguments, which are used when calling strcasecmp. Furthermore, operator() function is defined 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. If the compiler grants our inline requests, it will in fact call strcasecmp, skipping two extra function calls.

The comparison function object is often a predefined function object. Predefined function object classes 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. Near the end of the section about function objects function adaptors are introduced.

Predefined function objects are used predominantly with generic algorithms. Predefined function objects exists for arithmetic, relational, and logical operations. In section 24.3 predefined function objects are developed performing bitwise operations.

18.1.1: Arithmetic function objects

The arithmetic function objects support the standard arithmetic operations: addition, subtraction, multiplication, division, modulo and negation. These function objects invoke the corresponding operators of the data types for which they are instantiated. For example, for addition the function object plus<Type> is available. If we replace Type by size_t then the addition operator for size_t values is used, if we replace Type by string, the addition operator for strings is used. For example:
    #include <iostream>
    #include <string>
    #include <functional>
    using namespace std;

    int main(int argc, char **argv)
    {
        plus<size_t> uAdd;              // function object to add size_ts

        cout << "3 + 5 = " << uAdd(3, 5) << '\n';

        plus<string> sAdd;              // function object to add strings

        cout << "argv[0] + argv[1] = " << sAdd(argv[0], argv[1]) << '\n';
    }
    /*
        Output when called as: 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) supporting the operator called by the function object.

Suppose we want to perform an operation on a left hand side operand which is always the same variable and a right hand side argument for which, in turn, all elements of an array should be used. E.g., we want to compute the sum of all elements in an array; or we want to concatenate all the strings in a text-array. In situations like these function objects come in handy.

As stated, function objects are heavily used in the context of the generic algorithms, so let's take a quick look ahead at yet another one.

The generic algorithm accumulate visits all elements specified 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 specified by the iterator range. It's easy to use this algorithm. The next 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 << '\n';
    }

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. We could also have used

    string("All concatenated arguments: ")
in which case the cout statement could simply have been cout << result << '\n'. The string-addition operation is used, called from plus<string>. The final concatenated string is returned.

Now we define a class Time, overloading operator+. Again, we can apply the predefined function object plus, now tailored to our newly defined datatype, to add times:

    #include <iostream>
    #include <string>
    #include <vector>
    #include <functional>
    #include <numeric>
    using namespace std;

    class Time
    {
        friend ostream &operator<<(ostream &str, Time const &time);
        size_t d_days;
        size_t d_hours;
        size_t d_minutes;
        size_t d_seconds;
        public:
            Time(size_t hours, size_t minutes, size_t seconds);
            Time &operator+=(Time const &rValue);
    };
    Time operator+(Time const &lValue, Time const &rValue)
    {
        Time ret(lValue);
        ret += rValue;
        return ret;
    }
    Time::Time(size_t hours, size_t minutes, size_t seconds)
    :
        d_days(0),
        d_hours(hours),
        d_minutes(minutes),
        d_seconds(seconds)
    {}
    Time &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;
    }
    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.";
    }
    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>()
            ) <<
            '\n';
    }
    //  Displays: 2 days, 14 hours, 51 minutes and 30 seconds.

The design of the above program is fairly straightforward. 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, accumulate is used to compute the accumulated time. It returns a Time object, which is inserted into cout.

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

The STL supports the following set of arithmetic function objects. The function call operator (operator()) of these function objects calls the matching arithmetic operator for the objects that are passed to the function call operator, returning that arithmetic operator's return value. The arithmetic operator that is actually called is mentioned below:

In the next example the transform generic algorithm is used to toggle the signs of all elements of an array. Transform 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 << '\n';
    }
    // Displays:  -1, 2, -3, 4, -5, 6,

18.1.2: Relational function objects

The relational operators are called by the relational function objects. All standard relational operators are supported: ==, !=, >, >=, < and <=.

The STL supports the following set of relational function objects. The function call operator (operator()) of these function objects calls the matching relational operator for the objects that are passed to the function call operator, returning that relational operator's return value. The relational operator that is actually called is mentioned below:

An example using the relational function objects in combination with 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 << '\n';

        sort(argv, argv + argc, less<string>());

        for (int idx = 0; idx < argc; ++idx)
            cout << argv[idx] << " ";
        cout << '\n';
    }

The example illustrates how strings may be sorted alphabetically and reversed alphabetically. 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 argv contains char * values, and that the relational function object expects a string. The promotion from char const * to string is silently performed.

18.1.3: Logical function objects

The logical operators are called by the logical function objects. The standard logical operators are supported: and, or, and not.

The STL supports the following set of logical function objects. The function call operator (operator()) of these function objects calls the matching logical operator for the objects that are passed to the function call operator, returning that logical operator's return value. The logical operator that is actually called is mentioned below:

An example using operator! is provided in the following trivial program, using transform to transform the logicalvalues 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};
        size_t const bArrSize = sizeof(bArr) / sizeof(bool);

        for (size_t idx = 0; idx < bArrSize; ++idx)
            cout << bArr[idx] << " ";
        cout << '\n';

        transform(bArr, bArr + bArrSize, bArr, logical_not<bool>());

        for (size_t idx = 0; idx < bArrSize; ++idx)
            cout << bArr[idx] << " ";
        cout << '\n';
    }
    /*
      Displays:

        1 1 1 0 0 0
        0 0 0 1 1 1
    */

18.1.4: Function adaptors

Function adaptors modify the working of existing function objects. The STL offers three kinds of function adaptors: binders, negators and member function wrappers. Binders and negators are described in the next two subsections; member function adaptors are covered in section 19.2 of the next chapter, which is a more natural point of coverage than the current chapter.

18.1.4.1: Binders

Binders are function adaptors converting binary function objects to unary function objects. They do so by binding one parameter of a binary function object to a constant value. For example, the first parameter of the minus<int> function object may be bound to 100, meaning that the resulting value is always equal to 100 minus the value of the function object's second argument.

Either the first or the second parameter may be bound to a specific value. To bind the constant value to the function object's first parameter the function adaptor bind1st is used. To bind the constant value to the function object's second parameter the function adaptor bind2nd is used. As an example, assume we want to count all elements of a vector of string objects that occur later in the alphabetical ordering than some reference string.

The count_if generic algorithm is the algorithm of choice for solving these kinds of problems. It expects the usual iterator range and a function object. However, instead of providing it with a function object it is provided with the bind2nd adaptor which in turn is initialized with a relational function object (greater<string>) and a reference string against which all strings in the iterator range are compared. Here is the required bind2nd specification:

    bind2nd(greater<string>(), referenceString)
Here is what this binder does: Although binders are defined as templates, it is illustrative to have a look at their implementations, assuming they were ordinary classes. Here is such a pseudo-implementation of the bind2nd function adaptor:
    class bind2nd
    {
        FunctionObject d_object;
        Operand const &d_operand;
        public:
            bind2nd(FunctionObject const &object, Operand const &operand);
            ReturnType operator()(Operand const &lvalue);
    };
    inline bind2nd::bind2nd(FunctionObject const &object,
                            Operand const &operand)
    :
        d_object(object),
        d_operand(operand)
    {}
    inline ReturnType bind2nd::operator()(Operand const &lvalue)
    {
        return d_object(lvalue, d_operand);
    }
The binder's operator() merely calls the function object's operator(), providing it with two arguments. It uses its parameter as the (latter) operator()'s first argument and it uses d_operand as operator()'s second argument. The adaptor's members are typically very small so they are usually implemented inline.

The above application of the bind2nd adaptor has another important characteristic. Its return type is identical to the return type of the function object that it receives as its first argument, which is bool. Functions returning bool values are also called predicate functions. In the above application the bind2nd adaptor therefore becomes a predicate function itself.

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 passed to this predicate, which is therefore a unary predicate. Through the binder the binary function object greater<> is adapted to a unary function object, that now compares each of the elements referred to by the iterator range to the reference string. Eventually, the count_if function is called like this:

    count_if(stringVector.begin(), stringVector.end(),
             bind2nd(greater<string>(), referenceString));

18.1.4.2: Negators

Negators are function adaptors converting the values returned by predicate function. Since there are unary and binary predicate functions, two negator function adaptors were predefined: not1 is the negator to use with unary predicates, not2 is the negator to with binary function objects.

Example: to count the number of persons in a vector<string> vector ordered alphabetically before (i.e., not exceeding) a certain reference text one of the following alternatives could be used:

The use of negators is illustrated by the following program:
    #include <iostream>
    #include <functional>
    #include <algorithm>
    #include <vector>
    using namespace std;

    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)) <<
            ' ';
        cout << count_if(iArr, iArr + 10, bind2nd(not2(greater<int>()), 6)) <<
            ' ';
        cout << count_if(iArr, iArr + 10, not1(bind2nd(greater<int>(), 6))) <<
            '\n';
    }
    // Displays: 6 6 6

One may wonder which of these alternative approaches is the faster. Using the first approach, in which a directly available function object was used, two actions must be performed for each iteration by count_if:

When the compiler uses inline as requested, only the second step is actually performed.

Using the second approach, using the not2 negator to negate the truth value of the complementary logical function object, three actions must be performed for each iteration by count_if:

When the compiler uses inline as requested, only the third step is actually performed.

Using the third approach, using not1 negator to negate the truth value of the binder, three actions must be performed for each iteration by count_if:

When the compiler uses inline as requested, only the third step is actually performed.

With a commonly used optimization flag like -O2 the compiler tries to grant inline requests. However, if the compiler ignores the inline requests the first variant will be faster.

18.2: Iterators

In addition to the conceptual iterator types presented in this section the STL defines several adaptors allowing objects to be passed as iterators. These adaptors are presented in the upcoming sections. Before those adaptors can be used the <iterator> header file must be included.

Iterators are objects acting like pointers. Iterators have the following general characteristics:

STL containers usually define members offering iterators (i.e., they define their own type iterator). These members are commonly called begin and end and (for reversed iterators (type reverse_iterator)) rbegin and rend.

Standard practice requires iterator ranges to be left inclusive. The notation [left, right) indicates that left is an iterator pointing to the first element, while right is an iterator pointing just beyond the last element. The iterator range is empty when left == right.

The following example shows how all elements of a vector of strings can be inserted into cout using its iterator ranges [begin(), end()), and [rbegin(), rend()). Note that the for-loops for both ranges are identical. Furthermore it nicely illustrates how the auto keyword can be used to define the type of the loop control variable instead of using a much more verbose variable definition like vector<string>::iterator (see also section 3.3.5):

    #include <iostream>
    #include <vector>
    #include <string>
    using namespace std;

    int main(int argc, char **argv)
    {
        vector<string> args(argv, argv + argc);

        for (auto iter = args.begin(); iter != args.end(); ++iter)
            cout << *iter << " ";
        cout << '\n';

        for (auto iter = args.rbegin(); iter != args.rend(); ++iter)
            cout << *iter << " ";
        cout << '\n';
    }

Furthermore, the STL defines const_iterator types that must be used when visiting 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 << '\n';

        for
        (
            vector<string>::const_reverse_iterator iter = args.rbegin();
                iter != args.rend();
                    ++iter
        )
            cout << *iter << " ";
        cout << '\n';

        return 0;
    }

The examples also illustrates that plain pointers can be used as 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 args with, argv + argc points just beyond the last element to be used, ++argv reaches the next command line argument. This is a general pointer characteristic, which is why they too can be used in situations where iterators are expected.

The STL defines five types of iterators. These iterator types are expected by generic algorithms, and in order to create a particular type of iterator yourself it is important to know their characteristics. In general, iterators (see also section 22.14) must define:

The following types of iterators are used when describing generic algorithms in chapter 19: The example given with the RandomAccessIterator illustrates how to relate iterators and generic algorithms: look for the iterator that's required by the (generic) algorithm, and then see whether the datastructure supports the required type of iterator. If not, the algorithm cannot be used with the particular datastructure.

18.2.1: std::distance

Earlier, in section 18.2 it was stated that iterators support pointer arithmetic for containers storing their elements consecutively in memory. This is not completely true: to determine the number of elements between the elements to which two iterators refer the iterator must support the subtraction operator.

Using pointer arithmetic to compute the number of elements between two iterators in, e.g., a std::list or std::unordered_map is not possible, as these containers do not store their elements consecutively in memory.

The function std::distance fills in that little gap: std::distance expects two InputIterators and returns the number of elements between them.

Before using distance the <iterator> header file must be included.

If the iterator specified as first argument exceeds the iterator specified as its second argument then the number of elements is non-positive, otherwise it is non-negative. If the number of elements cannot be determined (e.g., the iterators do not refer to elements in the same container), then distance's return value is undefined.

Example:

    #include <iostream>
    #include <unordered_map>
        
    using namespace std;
    
    int main()
    {
        unordered_map<int, int> myMap = {{1, 2}, {3, 5}, {-8, 12}};
    
        cout << distance(++myMap.begin(), myMap.end()) << '\n'; // shows: 2
    }

18.2.2: Insert iterators

Generic algorithms often require a target container into which the results of the algorithm are deposited. For example, the copy generic algorithm has three parameters. The first two define the range of visited elements, the third defines the first position where the results of the copy operation should be stored.

With the copy algorithm the number of elements to copy is usually available beforehand, since that number can usually be provided by pointer arithmetic. However, situations exist 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. Here the number of elements that are copied to the destination container is normally not known beforehand.

In situations like these an inserter adaptor function can often be used to create elements in the destination container. There are three types of inserter adaptors:

The inserter adaptors require the existence of two typedefs: Concentrating on back_inserter, this iterator expects the name of a container supporting a member push_back. The inserter's operator() member calls the container's push_back member. Objects of any class supporting a push_back member can be passed as arguments to back_inserter provided the class adds
    typedef DataType const &const_reference;
to its interface (where DataType const & is the type of the parameter of the class's member push_back). Example:
    #include <iostream>
    #include <algorithm>
    #include <iterator>
    using namespace std;

    class Insertable
    {
        public:
            typedef int value_type;
            typedef int const &const_reference;

            void push_back(int const &)
            {}
    };

    int main()
    {
        int arr[] = {1};
        Insertable insertable;

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

18.2.3: Iterators for `istream' objects

The istream_iterator<Type> can be used to define a set of iterators for istream objects. The general form of the istream_iterator iterator is:
    istream_iterator<Type> identifier(istream &in)
Here, Type is the type of the data elements read from the istream stream. It is used as the `begin' iterator in an interator range. Type may be any type for which operator>> is defined in combination with istream objects.

The default constructor is used as the end-iterator and corresponds to the end-of-stream. For example,

    istream_iterator<string> endOfStream;
The stream object that was specified when defining the begin-iterator is not mentioned with the default constructor.

Using back_inserter and istream_iterator adaptors, all strings from a stream can easily be stored in a container. Example (using anonymous istream_iterator adaptors):

    #include <iostream>
    #include <iterator>
    #include <string>
    #include <vector>
    #include <algorithm>
    using namespace std;

    int main()
    {
        vector<string> vs;

        copy(istream_iterator<string>(cin), istream_iterator<string>(),
             back_inserter(vs));

        for
        (
            vector<string>::const_iterator begin = vs.begin(), end = vs.end();
                begin != end; ++begin
        )
            cout << *begin << ' ';
        cout << '\n';
    }

18.2.3.1: Iterators for `istreambuf' objects

Input iterators are also available for streambuf objects.

To read from streambuf objects supporting input operations istreambuf_iterators can be used, supporting the operations that are also available for istream_iterator. Different from the latter iterator type istreambuf_iterators support three constructors:

In section 18.2.4.1 an example is given using both istreambuf_iterators and ostreambuf_iterators.

18.2.4: Iterators for `ostream' objects

An ostream_iterator<Type> adaptor can be used to pass an ostream to algorithms expecting an OutputIterator. Two constructors are available for defining ostream_iterators:
    ostream_iterator<Type> identifier(ostream &outStream);
    ostream_iterator<Type> identifier(ostream &outStream, char const *delim);
Type is the type of the data elements that should be inserted into an ostream. It may be any type for which operator<< is defined in combinations with ostream objects. The latter constructor can be used to separate the individual Type data elements by delimiter strings. The former constructor does not use any delimiters.

The example shows how istream_iterators and an ostream_iterator may be used to copy information of a file to another file. A subtlety here is that you probably want to use in.unsetf(ios::skipws). It is used to clear the ios::skipws flag. As a consequence white space characters are simply returned by the operator, and the file is copied character by character. Here is the program:

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    using namespace std;

    int main()
    {
        cin.unsetf(ios::skipws);
        copy(istream_iterator<char>(cin), istream_iterator<char>(),
             ostream_iterator<char>(cout));
    }

18.2.4.1: Iterators for `ostreambuf' objects

Output iterators are also available for streambuf objects.

To write to streambuf objects supporting output operations ostreambuf_iterators can be used, supporting the operations that are also available for ostream_iterator. Ostreambuf_iterators support two constructors:

The next example illustrates the use of both istreambuf_iterators and ostreambuf_iterators when copying a stream in yet another way. Since the stream's streambufs are directly accessed the streams and stream flags are bypassed. Consequently there is no need to clear ios::skipws as in the previous section, while the next program's efficiency probably also exceeds the efficiency of the program shown in the previous section.
    #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;
    }

18.3: The class 'unique_ptr'

Before using the unique_ptr class presented in this section the <memory> header file must be included.

When pointers are used to access dynamically allocated memory strict bookkeeping is required to prevent memory leaks. When a pointer variable referring to dynamically allocated memory goes out of scope, the dynamically allocated memory becomes inaccessible and the program suffers from a memory leak.

To prevent such memory leaks strict bookkeeping is required: the programmer has to make sure that the dynamically allocated memory is returned to the common pool just before the pointer variable goes out of scope.

When a pointer variable points to a dynamically allocated single value or object, bookkeeping requirements are greatly simplified when the pointer variable is defined as a std::unique_ptr object.

Unique_ptrs are objects masquerading as pointers. Since they are objects, their destructors are called when they go out of scope. Their destructors automatically delete the dynamically allocated memory.

Unique_ptrs have some special characteristics:

The class unique_ptr offers several member functions to access the pointer itself or to have a unique_ptr point to another block of memory. These member functions (and unique_ptr constructors) are introduced in the next few sections.

A unique_ptr (as well as a shared_ptr, see section 18.4) can be used as a safe alternative to the now deprecated auto_ptr. Unique_ptr also augments auto_ptr as it can be used with containers and (generic) algorithms as it adds customizable deleters. Arrays can also be handled by unique_ptrs.

18.3.1: Defining `unique_ptr' objects

There are three ways to define unique_ptr objects. Each definition contains the usual <type> specifier between angle brackets:

18.3.2: Creating a plain `unique_ptr'

Unique_ptr's default constructor defines a unique_ptr not pointing to a particular block of memory:
    unique_ptr<type> identifier;
The pointer controlled by the unique_ptr object is initialized to 0 (zero). Although the unique_ptr object itself is not the pointer, its value can be compared to 0. Example:
    unique_ptr<int> ip;

    if (!ip)
        cout << "0-pointer with a unique_ptr object\n";
Alternatively, the member get can be used (cf. section 18.3.5).

18.3.3: Moving another `unique_ptr'

A unique_ptr may be initialized using an rvalue reference to a unique_ptr object for the same type:
    unique_ptr<type> identifier(other unique_ptr object);
The move constructor is used, e.g., in the following example:
    void mover(unique_ptr<string> &&param)
    {
        unique_ptr<string> tmp(move(param));
    }
Analogously, the assignment operator can be used. A unique_ptr object may be assigned to a temporary unique_ptr object of the same type (again move-semantics is used). For example:
    #include <iostream>
    #include <memory>
    #include <string>

    using namespace std;

    int main()
    {
        unique_ptr<string> hello1(new string("Hello world"));
        unique_ptr<string> hello2(move(hello1));
        unique_ptr<string> hello3;

        hello3 = move(hello2);
        cout << // *hello1 << /\n' <<   // would have segfaulted
                // *hello2 << '\n' <<   // same
                *hello3 << '\n';
    }
    // Displays:    Hello world

The example illustrates that

If hello1 or hello2 had been inserted into cout a segmentation fault would have resulted. The reason for this should now be clear: it is caused by dereferencing 0-pointers. In the end, only hello3 actually points to the originally allocated string.

18.3.4: Pointing to a newly allocated object

A unique_ptr is most often initialized using a pointer to dynamically allocated memory. The generic form is:
    unique_ptr<type [, deleter_type]> identifier(new-expression
            [, deleter = deleter_type()]);
The second (template) argument (deleter(_type)) is optional and may refer to a free function or function object handling the destruction of the allocated memory. A deleter is used, e.g., in situations where a double pointer is allocated and the destruction must visit each nested pointer to destroy the allocated memory (see below for an illustration).

Here is an example initializing a unique_ptr pointing to a string object:

    unique_ptr<string> strPtr(new string("Hello world"));
The argument that is passed to the constructor is the pointer returned by operator new. Note that type does not mention the pointer. The type that is used in the unique_ptr construction is the same as the type that is used in new expressions.

Here is an example showing how an explicitly defined deleter may be used to delete a dynamically allocated array of pointers to strings:

    #include <iostream>
    #include <string>
    #include <memory>
    using namespace std;

    struct Deleter
    {
        size_t d_size;
        Deleter(size_t size = 0)
        :
            d_size(size)
        {}
        void operator()(string **ptr) const
        {
            for (size_t idx = 0; idx < d_size; ++idx)
                delete ptr[idx];
            delete[] ptr;
        }
    };
    int main()
    {
        unique_ptr<string *, Deleter> sp2(new string *[10], Deleter(10));

        Deleter &obj = sp2.get_deleter();
    }

A unique_ptr can be used to reach the member functions that are available for objects allocated by the new expression. These members can be reached as if the unique_ptr 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>
    #include <cstring>
    using namespace std;

    int main()
    {
        unique_ptr<string> sp(new string("Hello world"));

        cout << *sp << '\n';
        sp->insert(strlen("Hello "), "C++ ");
        cout << *sp << '\n';
    }
    /*
        Displays:
            Hello world
            Hello C++ world
    */

18.3.5: Operators and members

The class unique_ptr offers the following operators:

The class unique_ptr supports the following member functions:

18.3.6: Using `unique_ptr' objects for arrays

When a unique_ptr is used to store arrays the dereferencing operator makes little sense but with arrays unique_ptr objects benefit from index operators. The distinction between a single object unique_ptr and a unique_ptr referring to a dynamically allocated array of objects is realized through a template specialization.

With dynamically allocated arrays the following syntax is available:

In these cases the smart pointer's destructors call delete[] rather than delete.

18.3.7: The legacy class 'auto_ptr' (deprecated)

The (now deprecated by the C++11 standard) smart pointer class std::auto_ptr<Type> has traditionally been offered by C++. This class does not support move semantics, but when an auto_ptr object is assigned to another, the right-hand object loses its information.

The class unique_ptr does not have auto_ptr's drawbacks and consequently using auto_ptr is now deprecated. Car_ptrs suffer from the following drawbacks:

Because of its drawbacks and available replacements the auto_ptr class is no longer covered by the C++ Annotations. Existing software should be modified to use smart pointers (unique_ptrs or shared_ptrs) and new software should, where applicable, directly be implemented in terms of these new smart pointer types.

18.4: The class 'shared_ptr'

In addition to unique_ptr the C++11 standard offers std::shared_ptr<Type> which is a reference counting smart pointer.

Before using shared_ptrs the <memory> header file must be included.

The shared pointer automatically destroys its contents once its reference count has decayed to zero. As with unique_ptr, when defining a shared_ptr<Base> to store a newly allocated Derived class object, the returned Base * may be cast to a Derived * using a static_cast: polymorphism isn't required, and when resetting the shared_ptr or when the shared_ptr goes out of scope, no slicing occurs, and Derived's destructor is called (cf. section 18.3).

Shared_ptrs support copy and move constructors as well as standard and move overloaded assignment operators.

Like unique_ptrs, shared_ptrs may refer to dynamically allocated arrays.

18.4.1: Defining `shared_ptr' objects

There are four ways to define shared_ptr objects. Each definition contains the usual <type> specifier between angle brackets:

18.4.2: Creating a plain `shared_ptr'

Shared_ptr's default constructor defines a shared_ptr not pointing to a particular block of memory:
    shared_ptr<type> identifier;
The pointer controlled by the shared_ptr object is initialized to 0 (zero). Although the shared_ptr object itself is not the pointer, its value can be compared to 0. Example:
    shared_ptr<int> ip;

    if (!ip)
        cout << "0-pointer with a shared_ptr object\n";
Alternatively, the member get can be used (cf. section 18.4.4).

18.4.3: Pointing to a newly allocated object

Most often a shared_ptr is initialized by a dynamically allocated block of memory. The generic form is:
    shared_ptr<type> identifier(new-expression [, deleter]);
The second argument (deleter) is optional and refers to a function object or free function handling the destruction of the allocated memory. A deleter is used, e.g., in situations where a double pointer is allocated and the destruction must visit each nested pointer to destroy the allocated memory (see below for an illustration). It is used in situations comparable to those encountered with unique_ptr (cf. section 18.3.4).

Here is an example initializing a shared_ptr pointing to a string object:

    shared_ptr<string> strPtr(new string("Hello world"));
The argument that is passed to the constructor is the pointer returned by operator new. Note that type does not mention the pointer. The type that is used in the shared_ptr construction is the same as the type that is used in new expressions.

The next example illustrates that two shared_ptrs indeed share their information. After modifying the information controlled by one of the objects the information controlled by the other object is modified as well:

    #include <iostream>
    #include <memory>
    #include <cstring>
    using namespace std;

    int main()
    {
        shared_ptr<string> sp(new string("Hello world"));
        shared_ptr<string> sp2(sp);

        sp->insert(strlen("Hello "), "C++ ");
        cout << *sp << '\n' <<
                *sp2 << '\n';
    }
    /*
        Displays:
            Hello C++ world
            Hello C++ world
    */

18.4.4: Operators and members

The class shared_ptr offers the following operators:

The following member function member functions are supported:

18.4.5: Casting shared pointers

Be cautious when using standard C++ style casts in combination with shared_ptr objects. Consider the following two classes:
    struct Base
    {};
    struct Derived: public Base
    {};

As with unique_ptr, when defining a shared_ptr<Base> to store a newly allocated Derived class object, the returned Base * may be cast to a Derived * using a static_cast: polymorphism isn't required, and when resetting the shared_ptr or when the shared_ptr goes out of scope, no slicing occurs, and Derived's destructor is called (cf. section 18.3).

Of course, a shared_ptr<Derived> can easily be defined. Since a Derived object is also a Base object, a pointer to Derived can be considered a pointer to Base without using casts, but a static_cast could be used for force the interpretation of a Derived * to a Base *:

    Derived d;
    static_cast<Base *>(&d);

However, a plain static_cast cannot be used when initializing a shared pointer to a Base using the get member of a shared pointer to a Derived object. The following code snipped eventually results in an attempt to delete the dynamically allocated Base object twice:

    shared_ptr<Derived> sd(new Derived);
    shared_ptr<Base> sb(static_cast<Base *>(sd.get()));
Since sd and sb point at the same object ~Base will be called for the same object when sb goes out of scope and when sd goes out of scope, resulting in premature termination of the program due to a double free error.

These errors can be prevented using casts that were specifically designed for being used with shared_ptrs. These casts use specialized constructors that create a shared_ptr pointing to memory but shares ownership (i.e., a reference count) with an existing shared_ptr. These special casts are:

18.4.6: Using `shared_ptr' objects for arrays

Different from the unique_ptr class no specialization exists for the shared_ptr class to handle dynamically allocated arrays of objects.

But like unique_ptrs, with shared_ptrs referring to arrays the dereferencing operator makes little sense while in these circumstances shared_ptr objects would benefit from index operators.

It is not difficult to create a class shared_array offering such facilities. The class template shared_array, derived from shared_ptr merely should provide an appropriate deleter to make sure that the array and its elements are properly destroyed. In addition it should define the index operator and optionally could declare the derefencing operators using delete.

Here is an example showing how shared_array can be defined and used:

    struct X
    {
        ~X()
        {
            cout << "destr\n";  // show the object's destruction
        }
    };
    template <typename Type>
    class shared_array: public shared_ptr<Type>
    {
        struct Deleter          // Deleter receives the pointer
        {                       // and calls delete[]
           void operator()(Type* ptr)
           {
              delete[] ptr;
           }
        };
        public:
            shared_array(Type *p)           // other constructors
            :                               // not shown here
                shared_ptr<Type>(p, Deleter())
            {}
            Type &operator[](size_t idx)    // index operators
            {
                return shared_ptr<Type>::get()[idx];
            }
            Type const &operator[](size_t idx) const
            {
                return shared_ptr<Type>::get()[idx];
            }
            Type &operator*() = delete;     // delete pointless members
            Type const &operator*() const = delete;
            Type *operator->() = delete;
            Type const *operator->() const = delete;
    };
    int main()
    {
        shared_array<X> sp(new X[3]);
        sp[0] = sp[1];
    }

18.5: Using `make_shared' to combine `shared_ptr' and `new'

Usually a shared_ptr is initialized at definition time with a pointer to a newly allocated object. Here is an example:
    std::shared_ptr<string> sptr(new std::string("hello world"))
In such statements two memory allocation calls are used: one for the allocation of the std::string and one used interally by std::shared_ptr's constructor itself.

The two allocations can be combined into one single allocation (which is also slightly more efficient than explicitly calling shared_ptr's constructor) using the make_shared template. The function template std::make_shared has the following prototype:

    template<typename Type, typename ...Args>
    std::shared_ptr<Type> std::make_shared(Args ...args);

Before using make_shared the <memory> header file must be included.

This function template allocates an object of type Type, passing args to its constructor (using perfect forwarding, see section 22.5.2), and returns a shared_ptr initialized with the address of the newly allocated Type object.

Here is how the above sptr object can be initialized using std::make_shared. Notice the use of auto which frees us from having to specify sptr's type explicitly:

    auto sptr(std::make_shared<std::string>("hello world"));
After this initialization std::shared_ptr<std::string> sptr has been defined and initialized. It could be used as follows:
    std::cout << *sptr << '\n';

18.6: Classes having pointer data members

Classes having pointer data members require special attention. In particular at construction time one must be careful to prevent wild pointers and/or memory leaks. Consider the following class defining two pointer data members:
    class Filter
    {
        istream *d_in;
        ostream *d_out;
        public:
            Filter(char const *in, char const *out);
    };
Assume that Filter objects filter information read from *d_in and write the filtered information to *d_out. Using pointers to streams allows us to have them point at any kind of stream like istreams, ifstreams, fstreams or istringstreams. The shown constructor could be implemented like this:
    Filter::Filter(char const *in, char const *out)
    :
        d_in(new ifstream(in)),
        d_out(new ofstream(out))
    {
        if (!*d_in || !*d_out)
            throw string("Input and/or output stream not available");
    }
Of course, the construction could fail. new could throw an exception; the stream constructors could throw exceptions; or the streams could not be opened in which case an exception is thrown from the constructor's body. Using a function try block helps. Note that if d_in's initialization throws, there's nothing to be worried about. The Filter object hasn't been constructed, its destructor is not be called and processing continues at the point where the thrown exception is caught. But Filter's destructor is also not called when d_out's initialization or the constructor's if statement throws: no object, and hence no destructor is called. This may result in memory leaks, as delete isn't called for d_in and/or d_out. To prevent this, d_in and d_out must first be initialized to 0 and only then the initialization can be performed:
    Filter::Filter(char const *in, char const *out)
    try
    :
        d_in(0),
        d_out(0)
    {
        d_in = new ifstream(in);
        d_out = new ofstream(out);

        if (!*d_in || !*d_out)
            throw string("Input and/or output stream not available");
    }
    catch (...)
    {
        delete d_out;
        delete d_in;
    }
This quickly gets complicated, though. If Filter harbors yet another data member of a class whose constructor needs two streams then that data cannot be constructed or it must itself be converted into a pointer:
    Filter::Filter(char const *in, char const *out)
    try
    :
        d_in(0),
        d_out(0)
        d_filterImp(*d_in, *d_out)    // won't work
    { ... }

    // instead:

    Filter::Filter(char const *in, char const *out)
    try
    :
        d_in(0),
        d_out(0),
        d_filterImp(0)
    {
        d_in = new ifstream(in);
        d_out = new ofstream(out);
        d_filterImp = new FilterImp(*d_in, *d_out);
        ...
    }
    catch (...)
    {
        delete d_filterImp;
        delete d_out;
        delete d_in;
    }
Although the latter alternative works, it quickly gets hairy. In situations like these smart pointers should be used to prevent the hairiness. By defining the stream pointers as (smart pointer) objects they will, once constructed, properly be destroyed even if the rest of the constructor's code throws exceptions. Using a FilterImp and two unique_ptr data members Filter's setup and its constructor becomes:
    class Filter
    {
        std::unique_ptr<std::ifstream> d_in;
        std::unique_ptr<std::ofstream> d_out;
        FilterImp d_filterImp;
        ...
    };

    Filter::Filter(char const *in, char const *out)
    try
    :
        d_in(new ifstream(in)),
        d_out(new ofstream(out)),
        d_filterImp(*d_in, *d_out)
    {
        if (!*d_in || !*d_out)
            throw string("Input and/or output stream not available");
    }
We're back at the original implementation but this time without having to worry about wild pointers and memory leaks. If one of the member initializers throws the destructors of previously constructed data members (which are now objects) are always called.

As a rule of thumb: when classes need to define pointer data members they should define those pointer data members as smart pointers if there's any chance that their constructors throw exceptions.

18.7: Lambda expressions

The C++11 standard adds lambda expressions to the language. As we'll see in chapter 19 generic algorithms often accept arguments that can either be function objects or plain functions. Examples are the sort (cf. section 19.1.58) and find_if (cf. section 19.1.16) generic algorithms. As a rule of thumb: when a called function must remember its state a function object is appropriate, otherwise a plain function can be used.

Frequently the function or function object is not readily available, and it must be defined in or near the location where it is used. This is commonly realized by defining a class or function in the anonymous namespace (say: class or function A), passing an A to the code needing A. If that code is itself a member function of the class B, then A's implementation might benefit from having access to the members of class B.

Often this scheme results in a significant amount of code (defining the class), or it results in complex code (to make available software elements that aren't automatically accessible to A's code). It may also result in code that is irrelevant at the current level of specification. Nested classes don't solve these problems either. Moreover, nested classes can't be used in templates.

Lamba expressions solve these problems. A lambda expression defines an anonymous function object, also called a closure object. When a lambda expression is evaluated it results in a temporary object (the closure object). The type of a closure object is called its closure type.

Lambda expressions may be used inside blocks, classes or namespaces (i.e., pretty much anywhere you like). Their implied closure type is defined in the smallest block, class or namespace scope which contains the lamba expression. The closure object's visibility starts at its point of definition and ends where its closure type ends.

The closure type defines a (const) public inline function call operator. Here is an example of a lambda expression:

    []                      // the `lambda-introducer'
    (int x, int y)          // the `lambda-declarator'
    {                       // a normal compound-statement
        return x * y;
    }
The function call operator of the closure object created by this lambda expression expects two int arguments and returns their product. It is an inline const member of the closure type. To drop the const attribute, the lamba expression should specify mutable, as follows:
    [](int x, int y) mutable
    ...
The lambda-declarator may be omitted, if no parameters are defined. The parameters in a lamba declarator may not be given default arguments.

A closure object as defined by the above lamda expression could be used e.g., in combination with the accumulate (cf. section 19.1.1) generic algorithm to compute the product of a series of int values stored in a vector:

    cout << accumulate(vi.begin(), vi.end(), 1,
                [](int x, int y) { return x * y; });
The above lambda function uses the implicit return type decltype(x * y). An implicit return type can be used if the lambda expression does not contain a return statement (i.e., a void lambda expression), if it contains a single return statement, or if it contains multiple return statements returning values of identical types (e.g., all int values).

If there are multiple return statements returning values of different types then the lambda expression's return type must specified be explicitly using a late-specified return type, (cf. section 3.3.5):

    [](int x, int y) -> int
    {
        if (y < 0)
            return x / static_cast<double>(y);

        return z + x;
    }

Variables that are visible at the location of a lambda expression can be accessed by the lambda expression. How these variables are accessed depends on the contents of the lambda-introducer (the area between the square brackets, called the the lambda-capture). The lambda-capture allows passing a local context to lambda expressions.

Visible global and static variables as well as local variables defined in the lambda expression's compound statement itself can directly be accessed and, if applicable, modified. Example:

    int global;
    
    void fun()
    {
        []()  // [] may contain any specification
        { 
            int localVariable = 0;
            localVariable = ++global; 
        };
    }

If the lambda expression is defined within a (non-static) class member function then an initial & or = character in the lambda-capture enables this, allowing the lambda expression access to all class members (data and functions). The class's data members can be modified.

If the lambda expression is defined inside a function then that function's local variables that are visible at the point of the lambda expression's definition can be accessed by the lambda expression.

An initial & character in the lambda-capture accesses these local variables by reference. These variables can be modified from within the lambda expression.

An initial = character in the lambda-capture creates a local copy of the referred-to local variables. Furthermore, in this case the values of these local copies can only be changed by the lambda expression if the lambda expression is defined using the mutable keyword. E.g.,

    struct Class
    {
        void fun()
        {
            int var = 0;
            [=]() mutable
            {
                ++var;  // modifies the local
            }           // copy, not fun's var
        }
    }

Fine-tuning is also possible. With an initial =, comma-separated &var specifications indicate that the mentioned local variables should be processed by reference, rather than as copies; with an initial &, comma separated var specifications indicate that local copies should be used of the mentioned local variables. Again, these copies have immutable values unless the lambda expression is provided with the mutable keyword.

Here is an example, using the for_each (cf. section 19.1.17) generic algorithm:

    void showSum(vector<int> const &vi)
    {
        int total = 0;
        for_each(
            vi.begin(), vi.end(),
            [&](int x)
            {
                total += x;
            }
        );
        std::cout << total << '\n';
    }
The variable int total is passed to the lambda expression by reference and is directly accessed by the function. Its parameter list merely defines an int x, which is initialized in sequence by each of the values stored in vi. Once the generic algorithm has completed showSum's variable total has received a value that is equal to the sum of all the vector's values. It has outlived the lambda expression and its value is displayed.

Although generic algorithms are extremely useful, they may not always be available for the task at hand. Moreover, an algorithm like for_each looks a bit unwieldy, now that the language offers range-based for-loops. So let's try this, instead of the above implementation:

    void showSum(vector<int> const &vi)
    {
        int total = 0;
        for (auto el: vi)
            [&](int x)
            {
                total += x;
            };

        std::cout << total << '\n';
    }
But when showSum is now called, its cout statement consistently reports 0. What's happening here?

When a generic algorithm is given a lambda function, its implementation instantiates a reference to a function, and that function is thereupon called from within the generic algorithm. However, in the above example the range-based for-loop's nested statement merely represents the declaration of a lamba function: nothing is actually called, and hence total remains equal to 0. So, to make the above example work we not only must define the lambda expression, but we must also call the lambda function. One way of doing that is by giving the lambda function a name, and then call the lamba function by its given name:

    void showSum(vector<int> const &vi)
    {
        int total = 0;
        for (auto el: vi)
        {
            auto lambda = [&](int x)
                            {
                                total += x;
                            };

            lambda(el);
        }
        std::cout << total << '\n';
    }

In fact, there is no need to give the lambda function a name: the auto lambda declaration merely represents the lambda function, which could also directly be called, as an extension of its definition. The syntax may look a bit weird, but there's nothing wrong with it, and it allows us to drop the compound statment, required in the last example, completely. Here goes:

    void showSum(vector<int> const &vi)
    {
        int total = 0;
        for (auto el: vi)
            [&](int x)
            {
                total += x;
            }(el);          // immediately append the 
                            // argument list to the lambda
                            // function's definition
        std::cout << total << '\n';
    }

Another fine-tuning uses this in the lambda-capture: it also allows the lambda-expression to access the surrounding class members. Example:

    class Data
    {
        std::vector<std::string> d_names;
        public:
            void show() const
            {
                int count = 0;
                std::for_each(d_names.begin(), d_names.end(),
                    [this, &count](std::string const &name)
                    {
                        std::cout << ++count << ' ' <<
                            capitalized(name) << '\n';
                    }
                );
            }
        private:
            std::string capitalized(std::string name);
    };

Lambda expressions may also be assigned to variables. An example of such an assignment (using auto to define the variable's type) is:

    auto sqr = [](int x)
               {
                   return x * x;
               };
The lifetime of such lambda expressions is equal to the lifetime of the variable receiving the lambda expression as its value. Named lambda functions nicely fit in the niche of local functions: when a function needs to perform some computations that are at a conceptually lower level than the function's task itself, then it's attractive to encapsulate these computations in a separate support function, and call the support function where needed. A support function can be defined in an anonymous namespace, but that quickly becomes awkward when the requiring function is a class member, and the support function needs access to the class's members as well. In that case a named lambda expression can be used: it can be defined within the requiring function, and may be given full access to the surrounding class. The name to which the lambda expression is assigned becomes the name of a function which can be called from the surrounding function. Here is an example, converting a numeric IP address to a dotted decimal string, which can also be accessed directly from an Dotted object (all implementations in-class to conserve space):
    class Dotted
    {
        std::string d_dotted;
        
        public:
            std::string const &dotted() const
            {
                return d_dotted;
            }
            std::string const &dotted(size_t ip)
            {
                auto octet = 
                    [](size_t idx, size_t numeric)
                    {
                        return to_string(numeric >> idx * 8 & 0xff);
                    };

                d_dotted = 
                        octet(3, ip) + '.' + octet(2, ip) + '.' +
                        octet(1, ip) + '.' + octet(0, ip);

                return d_dotted;
            }
    };

Now that lambda expressions have been covered let's see how they can be used to avoid spurious returns from condition_variable's wait calls (cf. section 20.5.3). According to the C++11 standard, condition variables may spuriously return from wait calls. Therefore it is necessary to check that the data are actually available once wait continues.

The class condition_variable allows us to do that by offering wait members expecting a lock and a predicate. The predicate checks the data's state, and returns true if the data's state allows the data's processing. Here is an alternative implementation of the down member shown in section 20.5.3, checking for the data's actual availability:

    void down()
    {
        unique_lock<mutex> lock(sem_mutex);
        condition.wait(lock, 
            [&]()
            {
                return semaphore != 0
            }
        );
        --semaphore;
    }
The lambda expression ensures that wait only returns once semaphore has been incremented.

18.8: Randomization and Statistical Distributions

Before the statistical distributions and accompanying random number generators can be used the <random> header file must be included.

The C++11 standard introduces several standard mathematical (statistical) distributions into the STL. These distributions allow programmers to obtain randomly selected values from a selected distribution.

These statistical distributions need to be provided with a random number generating object. Several of such random number generating objects are provided, extending the traditional rand function that is part of the C standard library.

These random number generating objects produce pseudo-random numbers, which are then processed by the statistical distribution to obtain values that are randomly selected from the specified distribution.

Although the STL offers various statistical distributions their functionality is fairly limited. The distributions allow us to obtain a random number from these distributions, but probability density functions or cumulative distribution functions are currently not provided by the STL. These functions (distributions as well as the density and the cumulative distribution functions) are, however, available in other libraries, like the boost math library (specifically:
http://www.boost.org/doc/libs/1_44_0/libs/math/doc/sf_and_dist/html/index.html).

It is beyond the scope of the C++ Annotations to discuss the mathematical characteristics of the various distributions that are supported by the C++11 standard. The interested reader is referred to the pertinent mathematical textbooks (like Stuart and Ord's (2009) Kendall's Advanced Theory of Statistics, Wiley) or to web-locations like http://en.wikipedia.org/wiki/Bernoulli_distribution.

18.8.1: Random Number Generators

The following generators are available:

Class template Integral/Floating point Quality Speed Size of state

linear_congruential_engine Integral Medium Medium 1
subtract_with_carry_engine Both Medium Fast 25
mersenne_twister_engine Integral Good Fast 624

The linear_congruential_engine random number generator computes

valuei+1 = OPENPAa * valuei + c) % m
It expects template arguments for, respectively, the data type to contain the generated random values; the multiplier a; the additive constant c; and the modulo value m. Example:
    linear_congruential_engine<int, 10, 3, 13> lincon;
The linear_congruential generator may be seeded by providing its constructor with a seeding-argument. E.g., lincon(time(0)).

The subtract_with_carry_engine random number generator computes

valuei = (valuei-s - valuei-r - carryi-1) % m
It expects template arguments for, respectively, the data type to contain the generated random values; the modulo value m; and the subtractive constants s and r. Example:
    subtract_with_carry_engine<int, 13, 3, 13> subcar;
The subtract_with_carry_engine generator may be seeded by providing its constructor with a seeding-argument. E.g., subcar(time(0)).

The predefined mersenne_twister_engine mt19937 (predefined using a typedef defined by the <random> header file) is used in the examples below. It can be constructed using `mt19937 mt' or it can be seeded by providing its constructor with an argument (e.g., mt19937 mt(time(0))). Other ways to initialize the mersenne_twister_engine are beyond the scope of the C++ Annotations (but see Lewis et al. ( Lewis, P.A.W., Goodman, A.S., and Miller, J.M. (1969), A pseudorandom number generator for the System/360, IBM Systems Journal, 8, 136-146.) (1969)).

The random number generators may also be seeded by calling their members seed accepting unsigned long values or generator functions (as in lc.seed(time(0)), lc.seed(mt)).

The random number generators offer members min and max returning, respectively, their minimum and maximum values (inclusive). If a reduced range is required the generators can be nested in a function or class adapting the range.

18.8.2: Statistical distributions

In the following sections the various statistical distributions that are supported by the C++11 standard are covered. The notation RNG is used to indicate a Random Number Generator and URNG is used to indicate a Uniform Random Number Generator. With each distribution a struct param_type is defined containing the distribution's parameters. The organization of these param_type structs depends on (and is described at) the actual distribution.

All distributions offer the following members (result_type refers to the type name of the values returned by the distribution):

All distributions support the following operators (distribution-name should be replaced by the name of the intended distribution, e.g., normal_distribution):

The following example shows how the distributions can be used. Replacing the name of the distribution (normal_distribution) by another distribution's name is all that is required to switch distributions. All distributions have parameters, like the mean and standard deviation of the normal distribution, and all parameters have default values. The names of the parameters vary over distributions and are mentioned below at the individual distributions. Distributions offer members returning or setting their parameters.

Most distributions are defined as class templates, requiring the specification of a data type that is used for the function's return type. If so, an empty template parameter type specification (<>) will get you the default type. The default types are either double (for real valued return types) or int (for integral valued return types). The template parameter type specification must be omitted with distributions that are not defined as template classes.

Here is an example showing the use of the statistical distributions, applied to the normal distribution:

#include <iostream>
#include <ctime>
#include <random>
using namespace std;

int main()
{
    std::mt19937 engine(time(0));
    std::normal_distribution<> dist;

    for (size_t idx = 0; idx < 10; ++idx)
        std::cout << "a random value: " << dist(engine) << "\n";

    cout << '\n' <<
        dist.min() << " " << dist.max() << '\n';
}

18.8.2.1: Bernoulli distribution

The bernoulli_distribution is used to generate logical truth (boolean) values with a certain probability p. It is equal to a binomial distribution for one experiment (cf 18.8.2.2).

The bernoulli distribution is not defined as a class template.

Defined types:

    typedef bool result_type;
    struct param_type
    {
      explicit param_type(double prob = 0.5);
      double p() const;                     // returns prob
    };

Constructor and members:

18.8.2.2: Binomial distribution

The binomial_distribution<IntType = int> is used to determine the probability of the number of successes in a sequence of n independent success/failure experiments, each of which yields success with probability p.

The template type parameter IntType defines the type of the generated random value, which must be an integral type.

Defined types:

    typedef IntType result_type;
    struct param_type
    {
      explicit param_type(IntType trials, double prob = 0.5);
      IntType t() const;                    // returns trials
      double p() const;                     // returns prob
    };

Constructors and members and example:

18.8.2.3: Cauchy distribution

The cauchy_distribution<RealType = double> looks similar to a normal distribution. But cauchy distributions have heavier tails. When studying hypothesis tests that assume normality, seeing how the tests perform on data from a Cauchy distribution is a good indicator of how sensitive the tests are to heavy-tail departures from normality.

The mean and standard deviation of the Cauchy distribution are undefined.

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType a = RealType(0),
                            RealType b = RealType(1));

        double a() const;
        double b() const;
    };

Constructors and members:

18.8.2.4: Chi-squared distribution

The chi_squared_distribution<RealType = double> with n degrees of freedom is the distribution of a sum of the squares of n independent standard normal random variables.

Note that even though the distribution's parameter n usually is an integral value, it doesn't have to be integral, as the chi_squared distribution is defined in terms of functions (exp and Gamma) that take real arguments (see, e.g., the formula shown in the <bits/random.h> header file, provided with the Gnu g++ compiler distribution).

The chi-squared distribution is used, e.g., when testing the goodness of fit of an observed distribution to a theoretical one.

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType n = RealType(1));

        RealType n() const;
    };

Constructors and members:

18.8.2.5: Extreme value distribution

The extreme_value_distribution<RealType = double> is related to the Weibull distribution and is used in statistical models where the variable of interest is the minimum of many random factors, all of which can take positive or negative values.

It has two parameters: a location parameter a and scale parameter b. See also
http://www.itl.nist.gov/div898/handbook/apr/section1/apr163.htm

Defined types:

typedef RealType result_type;

struct param_type
{
    explicit param_type(RealType a = RealType(0),
                        RealType b = RealType(1));

    RealType a() const;     // the location parameter
    RealType b() const;     // the scale parameter
};

Constructors and members:

18.8.2.6: Exponential distribution

The exponential_distribution<RealType = double> is used to describe the lengths between events that can be modelled with a homogeneous Poisson process. It can be interpreted as the continuous form of the geometric distribution.

Its parameter prob defines the distribution's lambda parameter, called its rate parameter. Its expected value and standard deviation are both 1 / lambda.

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType lambda = RealType(1));

        RealType lambda() const;
    };

Constructors and members:

18.8.2.7: Fisher F distribution

The fisher_f_distribution<RealType = double> is intensively used in statistical methods like the Analysis of Variance. It is the distribution resulting from dividing two Chi-squared distributions.

It is characterized by two parameters, being the degrees of freedom of the two chi-squared distributions.

Note that even though the distribution's parameter n usually is an integral value, it doesn't have to be integral, as the Fisher F distribution is constructed from Chi-squared distributions that accept a non-integral parameter value (see also section 18.8.2.4).

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType m = RealType(1),
                            RealType n = RealType(1));

        RealType m() const; // The degrees of freedom of the nominator
        RealType n() const; // The degrees of freedom of the denominator
    };

Constructors and members:

18.8.2.8: Gamma distribution

The gamma_distribution<RealType = double> is used when working with data that are not distributed according to the normal distribution. It is often used to model waiting times.

It has two parameters, alpha and beta. Its expected value is alpha * beta and its standard deviation is alpha * beta2.

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType alpha = RealType(1),
                            RealType beta = RealType(1));

        RealType alpha() const;
        RealType beta() const;
    };

Constructors and members:

18.8.2.9: Geometric distribution

The geometric_distribution<IntType = int> is used to model the number of bernoulli trials (cf. 18.8.2.1) needed until the first success.

It has one parameter, prob, representing the probability of success in an individual bernoulli trial.

Defined types:

    typedef IntType result_type;

    struct param_type
    {
        explicit param_type(double prob = 0.5);
        double p() const;
    };

Constructors, members and example:

18.8.2.10: Log-normal distribution

The lognormal_distribution<RealType = double> is a probability distribution of a random variable whose logarithm is normally distributed. If a random variable X has a normal distribution, then Y = eX has a log-normal distribution.

It has two parameters, m and s representing, respectively, the mean and standard deviation of ln(X).

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType m = RealType(0),
                            RealType s = RealType(1));

        RealType m() const;
        RealType s() const;
    };

Constructor and members:

18.8.2.11: Normal distribution

The normal_distribution<RealType = double> is commonly used in science to describe complex phenomena. When predicting or measuring variables, errors are commonly assumed to be normally distributed.

It has two parameters, mean and standard deviation.

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType mean = RealType(0),
                            RealType stddev = RealType(1));

        RealType mean() const;
        RealType stddev() const;
    };

Constructors and members:

18.8.2.12: Negative binomial distribution

The negative_binomial_distribution<IntType = int> probability distribution describes the number of successes in a sequence of Bernoulli trials before a specified number of failures occurs. For example, if one throws a die repeatedly until the third time 1 appears, then the probability distribution of the number of other faces that have appeared is a negative binomial distribution.

It has two parameters: (IntType) k (> 0), being the number of failures until the experiment is stopped and (double) p the probability of success in each individual experiment.

Defined types:

    typedef IntType result_type;

    struct param_type
    {
        explicit param_type(IntType k = IntType(1), double p = 0.5);

        IntType k() const;
        double p() const;
    };

Constructors and members:

18.8.2.13: Poisson distribution

The poisson_distribution<IntType = int> is used to model the probability of a number of events occurring in a fixed period of time if these events occur with a known probability and independently of the time since the last event.

It has one parameter, mean, specifying the expected number of events in the interval under consideration. E.g., if on average 2 events are observed in a one-minute interval and the duration of the interval under study is 10 minutes then mean = 20.

Defined types:

    typedef IntType result_type;

    struct param_type
    {
        explicit param_type(double mean = 1.0);

        double mean() const;
    };

Constructors and members:

18.8.2.14: Student t distribution

The student_t_distribution<RealType = double> is a probability distribution that is used when estimating the mean of a normally distributed population from small sample sizes.

It is characterized by one parameter: the degrees of freedom, which is equal to the sample size - 1.

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType n = RealType(1));

        RealType n() const;    // The degrees of freedom
    };

Constructors and members:

18.8.2.15: Uniform int distribution

The uniform_int_distribution<IntType = int> can be used to select integral values randomly from a range of uniformly distributed integral values.

It has two parameters, a and b, specifying, respectively, the lowest value that can be returned and the highest value that can be returned.

Defined types:

    typedef IntType result_type;

    struct param_type
    {
        explicit param_type(IntType a = 0, IntType b = max(IntType));

        IntType a() const;
        IntType b() const;
    };

Constructors and members:

18.8.2.16: Uniform real distribution

The uniform_real_distribution<RealType = double> can be used to select RealType values randomly from a range of uniformly distributed RealType values.

It has two parameters, a and b, specifying, respectively, the half-open range of values ([a, b)) that can be returned by the distribution.

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType a = 0, RealType b = max(RealType));

        RealType a() const;
        RealType b() const;
    };

Constructors and members:

18.8.2.17: Weibull distribution

The weibull_distribution<RealType = double> is commonly used in reliability engineering and in survival (life data) analysis.

It has two or three parameters and the two-parameter variant is offered by the STL. The three parameter variant has a shape (or slope) parameter, a scale parameter and a location parameter. The two parameter variant implicitly uses the location parameter value 0. In the two parameter variant the shape parameter (a) and the scale parameter (b) are provided. See
http://www.weibull.com/hotwire/issue14/relbasics14.htm for an interesting coverage of the meaning of the Weibull distribution's parameters.

Defined types:

    typedef RealType result_type;

    struct param_type
    {
        explicit param_type(RealType a = RealType(1),
                            RealType b = RealType(1));

        RealType a() const;     // the shape (slope) parameter
        RealType b() const;     // the scale parameter
    };

Constructors and members: