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: 9.8.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 20 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.11.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 have been 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 23.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 have been 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 21.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: 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.2: 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.2.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.3.1 an example is given using both istreambuf_iterators and ostreambuf_iterators.

18.2.3: 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.3.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 have been included.

When pointers are used to access dynamically allocated memory strict bookkeeping is required to prevent memory leaks from happening. 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 have been included.

The shared pointer automatically destroys its contents once its reference count has decayed to zero.

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

Shared pointers cannot simply be cast using the standard C++ style casts. Consider the following two classes: 
    struct Base
    {};
    struct Derived: public Base
    {};
A shared_ptr<Derived> can easily be defined. Since a Derived is also a Base a pointer to a Derived can be cast to a pointer to a Base using a static cast: 
    Derived d;
    static_cast<Base *>(&d);
However, a plain static_cast cannot be used when initializing a shared pointer to a Base using the object pointer of a shared pointer to a Derived object. I.e., the following statement will eventually result 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 have been included.

This function template allocates an object of type Type, passing args to its constructor (using perfect forwarding, see section 21.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: Multi Threading

The C++11 standard adds multi threading to C++ through the C++ standard library.

The C++ Annotations do not cover the concepts behind multi threading. It is assumed that the reader has a basic knowledge of these concepts. Multi threading is a topic by itself and many good reference sources exist (cf. Nichols, B, et al.'s Pthreads Programming, O'Reilly for some good introductions to multi-threading).

Multi threading facilities are offered by the class std::thread.

Thread synchronization is realized using objects of the class std::mutex and condition variables are implemented by the class std::condition_variable.

Members of these classes may throw system_error objects (cf. section 10.9) when encountering a low-level error condition.

In order to use multi threading in C++ programs the Gnu g++ compiler requires the use of the -pthread flag. E.g., to compile a multi-threaded program defined in a source file multi.cc the compiler must be called as follows: 

    g++ --std=c++0x -pthread -Wall multi.cc

18.7.1: Specifying absolute and relative time

Threads may postpone their actions until a specific point in time or for a specific amount of time. A time unit is defined using the class template std::ratio. A certain amount of time is defined using the class template duration and a specific point in time is defined using the class template time_point. In the C++ Annotations these classes are covered for as much as required in combination with multi-threading. The user is referred to the C++11 standard for additional details about ratio, duration, and time_point.

Before the class ratio can be used, the <ratio> header file must have been included. Before using either duration or time_point the <chrono> header file must have been included, where the latter header file includes the former.

18.7.1.1: Defining a unit: the class 'ratio'

The time unit that is used when defining time points or time intervals is specified using types defined by std::ratio: a class template expecting one or two template arguments. E.g., ratio<1> defines a time unit of a second, ratio<60> a time unit of a minute, and ratio<1, 1000> a time unit of one milli second.

The ratio class template is defined in the <ratio> header file, which is automatically read when including the chrono header file.

Once a ratio type has been defined (e.g., typedef ratio<1, 1000> milli) or becomes available (e.g., as seconds::period, see below), then the value of the template's first argument (e.g., 1) can be retrieved as num (e.g., seconds::period::num), while the value of the template's second argument (e.g., 1000) can be retrieved as den (e.g., seconds::period::den).

A large number of predefined ratio types exist. They can be used instead of the more cumbersome ratio<x> or ratio<x, y> specification:

yocto 10-24
zepto 10-21
atto 10-18
femto 10-15
pico 10-12
nano 10-9
micro 10-6
milli 10-3
centi 10-2
deci 10-1
deca 101
hecto 102
kilo 103
mega 106
giga 109
tera 1012
peta 1015
exa 1018
zetta 1021
yotta 1024
(the definitions of the types yocto, zepto, zetta and yotta use integral constants exceeding 64 bits, and although these constants are defined in the C++11 standard, they are not available on 64 bit or smaller architectures.)

18.7.1.2: Defining an amount of time: the class 'duration'

The class duration is defined in the std::chrono namespace. Like ratio it is a class template. The class template duration requires two template type arguments: a numeric type Value (e.g., int64_t or size_t) to contain the duration's value, and a time-unit, specified using ratio.

Before using the class std::chrono::duration the <chrono> header file must have been included.

In addition to the copy constructor (and overloaded assignment operator) the following constructors are available:

Using the second constructor, a duration of 30 minutes can be defined using, e.g., duration<size_t, ratio<60>> halfHour(30). Instead of explicitly defining a duration type, it is also possible to use the following predefined duration types:

nanoseconds duration<int64_t, nano>
microseconds duration<int64_t, micro>
milliseconds duration<int64_t, milli>
seconds duration<int64_t>
minutes duration<int64_t, ratio<60>>
hours duration<int64_t, ratio<3600>>
Using, e.g., the minutes definition, a duration of 30 minutes can simply be specified using minutes halfHour(30).

The value that is stored inside a duration is obtained using the class's constexpr Value count() const member. For halfHour this would return 30, not 1800, as the time unit itself is obtained as the duration<Value, Unit>::period type.

18.7.1.3: Clocks measuring time

The C++11 standard offers several predefined clock types that can be used in combination with multi-threaded programs. It is also possible to define your own clock-type, which must then satisfy the requirements defined in clause 20.11.3 of the C++11 standard.

The predefined clocks are defined in the std::chrono namespace. Before using the predefined clocks the <chrono> header file must have been included.

Clocks define several types (like period, duration, and time_point), and a member

which may be used by multi-threaded programs.

The class system_clock represents the `wall clock' time, using the system's real time clock. In addition to now the class system_clock offers two more static members:

The class steady_clock implements a clock whose time increases in parallel with with increase of real time.

The class high_resolution_clock implements the computer's fastest clock (i.e., the clock having the shortest timer-tick period).

An example of their use is given in the next section.

18.7.1.4: Defining a point in time: the class 'time_point'

The class time_point is defined in the std::chrono namespace. Like duration it is a class template. The class template time_point requires two template type arguments: Clock and a Duration.

The Clock type can be one of the predefined clock types, e.g., chrono::system_clock. By default, the Duration is the Clock::duration type, but an explicit type may also be provided.

Before using the class std::chrono::duration the <chrono> header file must have been included.

The class time_point offers three constructors:

Duration values may be added to or subtracted from a time_point object using, respectively, the time_point &operator+=(Duration const &step) and time_point &operator-=(Duration const &step) members. The corresponding binary + and - operators are also available.

The member constexpr Duration time_since_epoch() const returns the object's Duration since the epoch.

Here are some examples showing how time_point objects can be used: 

    #include <iostream>
    #include <chrono>

    using namespace std;
    using namespace chrono;

    int main()
    {
            // the current time
        time_point<system_clock> now(system_clock::now());

            // its value in seconds:
        cout << system_clock::to_time_t(now) << '\n';

            // now + two hours:
        cout << system_clock::to_time_t(now + hours(2)) << '\n';

            // define a time_point 1 hour after the epoch:
        time_point<system_clock> oneHrLater(hours(1));

            // show the epoch and the time in seconds of oneHrLater:
        cout << system_clock::to_time_t(time_point<system_clock>()) << ' ' <<
                system_clock::to_time_t(oneHrLater) << '\n';
    }

18.7.2: The namespace `std::this_thread'

The namespace this_thread is defined within the std namespace, and contains functions that uniquely identify the current thread of execution.

It offers the following members:

18.7.3: The class `std::thread'

In C++ multi threading can be realized through the use of objects of the class std::thread. Each object of this class handles a separate thread of execution.

Before using Thread objects the <thread> header file must have been included.

Threads can be joined, i.e., wait until another thread has finished, and the states of threads may be queried and controlled by a multi-threaded program.

Each thread object represents one unique thread of execution, but its unique thread may be transferred to another thread object. In this situation there remains but a single thread object that represents the running thread.

If a threads of execution loses its association with a thread object that thread is said to be detached. Conversely, thread objects by themselves are not necessarily associated with a running thread of execution: following the default construction, a move operation in which a thread object acts as the source thread or after detaching or joining threads the thread object may still exist, albeit in a state where it is not or no longer associated with a running thread.

The class thread offers the following constructors:

When a thread object is destroyed while its thread of execution is still active, terminate is called, forcing the program's end. So, before calling a thread object's destructor its thread of execution must have been terminated. This is accomplished by ending the function which was passed to the thread object's constructor.

In the following example a thread object is created, inserting the text hello world three times into cout: 

    #include <thread>
    #include <iostream>
    #include <unistd.h>

    using namespace std;

    // do not forget to use -pthread with g++

    void fun(size_t count, char const *txt)
    {

        for (; count--; )
            cout << txt << endl;
    }
    int main()
    {                   // runs the thread following
                        // the object construction
        thread display(fun, 3, "hello world");

        display.join(); // see the text
    }

The members of the class thread are:

The class thread supports the move assignment operator:

Since the tread(Fun &&fun, Args &&...args) constructor not only accepts functions but also function objects as its argument, a local context may be passed to the function object's constructor. Here is an example of a thread to which a function object is passed which is provided with a local context: 

    #include <iostream>
    #include <thread>
    #include <array>

    using namespace std;

    class Functor
    {
        array<int, 30> &d_data;
        int d_value;

        public:
            Functor(array<int, 30> &data, int value)
            :
                d_data(data),
                d_value(value)
            {}
            void operator()(ostream *out)
            {
                for (auto &value: d_data)
                {
                    value = d_value++;
                    *out << value << ' ';
                }
                *out << '\n';
            }
    };

    int main()
    {
        array<int, 30> data;
        Functor functor(data, 5);
        thread funThread(functor, &cout);
        funThread.join();
    };
Note the argument &cout that is passed to funThread and the definition ostream *out parameter of the funThread's function call operator. Here cout cannot be used (in combination with an ostream &out parameter), since the latter parameter is not move-constructible, whereas a pointer is.

18.7.4: Synchronization (mutexes)

The C++11 standard offers a series of mutex classes to protect shared data.

Before using mutexes the <mutex> header file must have been included.

Mutexes should be used to prevent data corruption when multiple threads need access to common data. For (a very simple) example: the following could happen when two threads access a common int variable, unless mutexes are used (a context switch occurs when the operating system switches between threads. With a mult-processor system the threads can really be executed in parallel. To keep the example simple, assume multi threading is used on a single-core computer, switching between multi-threads): 

Time step:    Thread1:      var        Thread2:        description
---------------------------------------------------------------------------
    0                        5
    1           starts                                  T1 active
    2           writes var                              T1 commences writing
    3           stopped                                 Context switch
    4                                   starts          T2 active
    5                                   writes var      T2 commences writing
    6                       10          assigns 10      T2 writes 10
    7                                   stopped         Context switch
    8           assigns 12                              T1 writes 12
    9                       12
----------------------------------------------------------------------------
The above is just a very simple illustration of what may go wrong when multiple threads access the same data without using mutexes.

Thread 2 proceeds on the assumption that var equals 10. However, after step 9 var holds the value 12. Mutexes are used to prevent these kinds of problems by offering a guarantee that thata are only accessed by the thread holding a mutex for the those data.

Exclusive data access completely depends on cooperation between the threads. If thread 1 uses mutexes, but thread 2 doesn't, then thread 2 may access the common data any which way it wants to. Of course that's bad practice, and mutexes allow us to write program not behaving badly in this sense.

It is stressed that although using mutexes is the programmer's responsibility, their implementation isn't. A user-program is unable to accomplish atomic locking mutexes offer. The bottom line is that if we try to implement a mutex-like facility in our programs then each statement is compiled into several machine instructions and in between each of these instructions the operating system may do a context switch, rendering the instructions non-atomic.

Mutexes offer the necessary atomic calls: when requesting a mutex-lock the thread is suspended (i.e., the mutex statement does not return) until the lock has been obtained by the thread.

More information about mutexes can be found in the mentioned O'Reilly book and in general in the extensive literature on this topic. It is not a topic that is discussed further in the C++ Annotations. The available facilities for using mutexes, however, are covered in this section.

Apart from the class std::mutex the class std::recursive_mutex is offered. When a recursive_mutex is called multiple times by the same thread it increases its lock-count. Before other threads may access the protected data the recursive mutex must be unlocked again that number of times. Moreover, the classes std::timed_mutex and std::recursive_timed_mutex are available. Their locks expire when released, but also after a certain amount of time.

All mutex classes offer the following constructors and members:

Note: mutex classes do not offer copy constructors and overloaded assignment operators.

In addition to the abovementioned members, timed mutex classes (timed_mutex,recursive_timed_mutex) also offer:

18.7.5: Locks and lock handling

Often locks are released at the end of some action block. To simplify locking additional template classes std::unique_lock and std::lock_guard are provided. At construction time the mutex type to be used must be specified. As their constructors (usually) lock the data and their destructors unlock the data they can be defined as local variables, unlocking their data once their scopes end.

Locks by default try to acquire the ownership of the mutex type that's passed to them at construction time. However, that may not always be convenient. Therefore additional constructors are defined offering additional modes of operation. These requested modes are specified by passing a tag type to those constructors that define what should be done with the lockable object during the lock's construction. The tag types (and tags) are:

Lock types do not define copy constructors or overloaded assignment operators, nor do they define any other member function. Basically, they only allow constructions. Their destructors release the ownertship of their mutex (or, when recursive mutex was passed to them) reduce the mutex's use count.

A lock_guard may be constructed by passing it a mutex type and an optional adopt_lock_t object.

Here is a simple example showing the use of a lock_guard. Once safeProcess ends guard is destroyed, thereby releasing the lock on data: 

    std::mutex dataMutex;
    Data data;

    void safeProcess()
    {
        std::lock_guard<std::mutex> guard(dataMutex);
        process(data);
    }

The class template unique_lock is much more elaborate than the basic lock_guard class template. It does not offer a copy constructor or overloaded assignment operator, but it does offer a move constructor and move assignment operator.

Here are its constructors and members (Mutex refers to the mutex type that was specified for the unique_lock at construction time). E.g., unique_lock<timed_mutex> defines Mutex as a timed_mutex below.

Here are unique_lock's constructors:

Overloaded operators:

Ordinary members:

Here is a simple example showing a unique_lock being used trying to obtain ownership of a timed_mutex: 

    std::timed_mutex dataMutex;
    Data data;

    void safeProcess()
    {
        std::unique_lock<std::timed_mutex>
            guard(dataMutex, std::chrono::milliseconds(3));
        if (guard)
            process(data);
    }
In the above example guard tries to obtain the lock during three milliseconds. If guard's operator bool returns true the lock was obtained and data can be processed safely.

18.7.5.1: Deadlocks

Although they should be avoided, Deadlocks are frequently encountered in multi threaded programs. A deadlock occurs when two locks are required to process data, but one thread obtains the first lock and another thread obtains the second lock. The C++11 standard defines a generic std::lock function that can be used to help preventing such situations. The std::lock function can be used to lock multiple mutexes in one atomic action. Here is an example: 
    struct SafeString
    {
        std::mutex  d_mutex;
        std::string d_text;
    };

    void calledByThread(SafeString &first, SafeString &second)
    {
        std::unique_lock<std::mutex>                        // 1
                lock_first(first.d_mutex, std::defer_lock);

        std::unique_lock<std::mutex>                        // 2
                lock_second(second.d_mutex, std::defer_lock);

        std::lock(lock_first, lock_second);                 // 3

        safeProcess(first.d_text, second.d_text);
    }
At 1 and 2 unique_locks are created. Locking is deferred until calling std::lock at 3. Having obtained the lock, the two SafeString text members can both be safely processed by calledByThread.

Another problematic issue with threads involves initialization. If multiple threads are running and only the first thread calling the initialization code should actually perform the initialization then this problem should not be solved using mutexes.

Although proper synchronization is realized, the synchronization is performed time and again for every thread. The C++11 standard offers several ways to perform a proper initialization:

18.7.6: Event handling (condition variables)

In this section condition variables are introduced, allowing programs to synchronize threads on the states of data, rather than on the access to data, which is realized using mutexes.

Before using condition variables the <condition_variable> header file must have been included.

To start our discussion, we consider a classic producer-consumer scenario: the producer generates items to be consumed by a consumer. The producer can only produce a certain number of items before its storage capacity has filled up and the client cannot consume more items than the producer has produced.

At some point the producer has to wait until the client has consumed enough, thus creating space in the producer's storage. Similarly, the consumer cannot start consuming until the producer has at least produced some items.

Mutexes (data locking) don't result in elegant solutions of producer-consumer types of problems, as using mutexes requires repeated locking and polling the amount of available items/storage. This isn't a very attractive option as it wastes resources. Polling forces threads to wait until they own the mutex, even though continuation might already be possible. The polling interval could be reduced, but that too isn't an attractive option, as it results in needlessly increasing the overhead associated with handling the associated mutexes.

On the other hand, condition variables allow you to avoid polling by synchronizing threads using the states (e.g., values) of data.

As the the states of the data may be modified by multiple threads, threads still have to use mutexes, but merely to control access to the data. However, condition variables allow threads to release ownership of the mutex until a certain state has been reached, until a preset amount of time has been passed, or until a preset point in time has been reached.

The prototypical setup of these kinds of programs look like this:

Condition variables come in two flavors: objects of the class std::condition_variable are used in combination with objects of type unique_lock<mutex>. This combination allows optimizations resulting in an increased efficiency compared to the efficiency that can be obtained with objects of the class std::condition_variable_any that can be used with any (e.g., user-supplied) lock type.

The condition variable classes offer members like wait, wait_for, wait_until, notify_one and notify_all that may concurrently be called. The notify members are always atomically executed. Execution of the wait members consists of three atomic parts:

Therefore, returning from wait-members the thread calling wait owns the lock.

Programs using condition variables cannot make any assumption about the order in which any of the notify_one, notify_all, wait, wait_for, and wait_until members are executed.

In addition to the condition variable classes the following free function and enum type are provided:

18.7.6.1: The class 'condition_variable'

The class condition_variable merely offers a default constructor. No copy constructor or overloaded assignment operator are provided.

Before using the class condition_variable the <condition_variable> header file must have been included.

The class's destructor requires that no thread is blocked by the current thread. This implies that all other (waiting) threads must have been notified; those threads may, however, subsequently block on the lock specified in their wait calls.

In the following member-descriptions a type Predicate indicates that the provided Predicate argument can be called as a function without arguments, returning a bool. Also, other member functions are frequently referred to. It is tacitly assumed that all members were called using the same condition variable object.

The class condition_variable's members are:

18.7.6.2: The class 'condition_variable_any'

Different from the class condition_variable the class condition_variable_any can be used with any (e.g., user-supplied) lock type, and not just with the stl-provided unique_lock<mutex>.

Before using the class condition_variable_any the <condition_variable> header file must have been included.

The functionality that is offered by condition_variable_any is identical to the functionality offered by the class condition_variable, albeit that the lock-type that is used by condition_variable_any is not predefined. The class condition_variable_any requires specification of the lock-type that must be used by its objects.

In the interface shown below this lock-type is referred to as Lock. Most of condition_variable_any's members are defined as member templates, defining a Lock type as one of its parameters. The requirements of these lock-types are identical to those of the stl-provided unique_lock, and user-defined lock-type implementations should provide at least the interface and semantics that is also provided by unique_lock.

This section merely presents the interface of the class condition_variable_any. As its interface offers the same members as condition_variable (allowing, where applicable, passing any lock-type instead of just unique_lock to corresponding members), the reader is referred to the previous section for a description of the semantics of the class members.

Like condition_variable, the class condition_variable_any merely offers a default constructor. No copy constructor or overloaded assignment operator are provided.

Also, like condition_variable, the class's destructor requires that no thread is blocked by the current thread. This implies that all other (waiting) threads must have been notified; those threads may, however, subsequently block on the lock specified in their wait calls.

Note that, in addition to Lock, the types Clock, Duration, Period, Predicate, and Rep are template types, defined just like the identically named types mentioned in the previous section.

The class condition_variable_any's members are:

18.7.6.3: An example using condition variables

Condition variables are used to synchronize threads on the states (values) of data, rather than on access to data (for which plain mutex-objects can be used). Using condition variables, a thread simply sleeps until it is notified by another thread. In a producer-consumer type of program this is usually accomplished like this: 
    producer loop:
        - produce the next item
        - wait until there's room to store the item,
            then reduce the available storage
        - store the item
        - increment the number of items in store

    consumer loop:
        - wait until there's an item in store,
            then reduce the number of items in store
        - remove the item from the store
        - increment the number of available storage locations
        - do something with the retrieved item

It is important that the two storage administrative tasks (registering the number of available items and available storage locations) are either performed by the client or by the producer. `Waiting' in this case means:

This scheme is implemented using a condition_variable. The variable containing the actual count is called semaphore and it can be protected using, e.g. mutex sem_mutex. In addition a condition_variable condition is defined. The following code uses three non-local variables: 
    size_t semaphore;
    mutex sem_mutex;
    condition_variable condition;

The waiting process is defined by the following function down: 

    void down()
    {
        unique_lock<mutex> lock(sem_mutex);   // get the lock
        while (semaphore == 0)
            condition.wait(lock);           // see 1, below.
        --semaphore;                        // dec. semaphore count
    }                                       // the lock is released
At 1 condition.wait releases the lock, waits until receiving a notification, and re-acquires the lock just before returning. Consequently, down's code always has complete and unique control over semaphore.

What about notifying the condition variable? This is handled by the `increment the number ...' lines in the producer and consumer loops. These parts are defined by the following up function: 

    void up()
    {
        lock_guard<std::mutex> lock(sem_mutex); // get the lock
        if (semaphore++ == 0)
            condition.notify_one();             // see 2, below
    }                                           // the lock is released
At 2 semaphore is always incremented. However, by using a postfix increment it is simultaneously tested for being zero. If it was initially zero then semaphore is now one. Consequently, the thread waiting for semaphore being unequal to zero may now continue. A waiting thread is notified by calling condition.notify_one. In situations where multiple threads are waiting `notify_all' can also be used.

Handling semaphore can nicely be encapsulated in a class Semaphore, offering members down and up. For a more extensive discussion of semaphores see Tanenbaum, A.S. and Austin, T. (2013) Structured Computer Organization, Pearson Prentice-Hall.

Using the facilities of the class Semaphore whose constructor expects an initial value of its semaphore data member, the classic producer and consumer paradigm can now easily be implemented in the following multi-threaded program (A more elaborate example of the producer-consumer program is found in the yo/stl/examples/events.cc file in the C++ Annotations's source archive): 

    Semaphore available(10);
    Semaphore filled(0);
    std::queue itemQueue;

    void producer()
    {
        size_t item = 0;
        while (true)
        {
            ++item;
            available.down();
            itemQueue.push(item);
            filled.up();
        }
    }
    void client()
    {
        while (true)
        {
            filled.down();
            size_t item = itemQueue.front();
            itemQueue.pop();
            available.up();
            process(item);      // not implemented here
        }
    }

    int main()
    {
        thread produce(producer);
        thread consume(consumer);

        produce.join();
        consume.join();
    }

18.8: Lambda expressions

The C++11 standard has added lambda expressions to the language. As we've seen generic algorithms often accept an argument that can either be a function object or it can be a plain function. Examples are the sort and find_if generic algorithms. When the function called by the generic algorithm must remember its state a function object is appropriate, otherwise a plain function can be used.

The function or function object is usually not readily available. Often it must be defined in or near the location where the generic algorithm is used. Usually this is accomplished by defining a class or function in the anonymous namespace, passing an object of that class or passing that function to a generic algorithm called from some other function. If the latter function is itself a member function the need may be felt to grant the function called by the generic algorithm access to other members of its class. Often this 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 from the called function (object)). It may also result in code that is irrelevant at the current level of specification. Nested classes don't solve these problems and nested classes can't be used in templates.

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 it does not contain parameters. The parameters in a lamba declarator may not be provided with default arguments.

A closure object as defined by the above lamda expression could be used e.g., in combination with the accumulate 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 stattement (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: 

    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.

Another fine-tuning consists of specifying 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 18.7.6.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 18.7.6.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.9: Randomization and Statistical Distributions

Before the statistical distributions and accompanying random number generators can be used the <random> header file must have been 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.9.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 = (a * 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.9.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.9.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.9.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.9.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.9.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.9.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.9.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.9.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.9.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.9.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.9.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.9.2.9: Geometric distribution

The geometric_distribution<IntType = int> is used to model the number of bernoulli trials (cf. 18.9.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.9.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.9.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.9.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.9.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.9.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.9.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.9.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.9.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: