• Table of Contents
• Previous Chapter
• Next Chapter

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

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

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

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

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

The remaining components of the STL will be covered in this and the next chapter. Iterators, adaptors, smart pointers, multi threading and other features of the STL will be discussed in the 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 comparable directive is required unless it is preferred to specify the required namespace explicitly. This occurs in at least one situation: in header files no using directive should be used, so here the std:: scope specification should always be specified when referring to elements of the STL.

18.1: Predefined function objects

        sort(stringVec.begin(), stringVec.end(), greater<std::string>());

The operator()() ( function call operator) itself is not visible at this point: don't confuse the parentheses in greater<string>() with calling operator()(). When that operator is actually used inside sort(), it receives two arguments: two strings to compare for `greaterness'. Internally, the operator>() of the data type to which the iterators point (i.e., string) is called by greater<string>'s function operator (operator()()) to compare the two objects. Since greater<>'s function call operator is defined inline, the call itself is not actually present in the code. Rather, sort() calls string::operator>(), thinking it called greater<>::operator()().

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

    #include <iostream>
    #include <string>
    #include <algorithm>

    using namespace std;

    class case_less
    {
        public:
            bool operator()(string const &left, string const &right) const
            {
                return strcasecmp(left.c_str(), right.c_str()) < 0;
            }
    };

    int main(int argc, char **argv)
    {
        sort(argv, argv + argc, case_less());
        for (int idx = 0; idx < argc; ++idx)
            cout << argv[idx] << " ";
        cout << endl;
    }

The comparison function object is often a predefined function object, since these are available for many commonly used operations. In the following sections the available predefined function objects are presented, together with some examples showing their use. At the end of the section about function objects function adaptors are introduced. Before predefined function objects can be used the following preprocessor directive must have been specified:

    #include <functional>

18.1.1: Arithmetic function objects

    #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) << endl;

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

        cout << "argv[0] + argv[1] = " << sAdd(argv[0], argv[1]) << endl;
    }
    /*
        Generated output with call: a.out going

        3 + 5 = 8
        argv[0] + argv[1] = a.outgoing
    */

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

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

    int main(int argc, char **argv)
    {
        string result =
                accumulate(argv, argv + argc, string(), plus<string>());

        cout << "All concatenated arguments: " << result << endl;
    }

        string("All concatenated arguments: ")

    cout << result << endl;

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

    #include <iostream>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <functional>
    #include <numeric>

    using namespace std;

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

        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)
            :
                d_days(0),
                d_hours(hours),
                d_minutes(minutes),
                d_seconds(seconds)
            {}
            Time &operator+=(Time const &rValue)
            {
                d_seconds   += rValue.d_seconds;
                d_minutes   += rValue.d_minutes   + d_seconds / 60;
                d_hours     += rValue.d_hours     + d_minutes / 60;
                d_days      += rValue.d_days      + d_hours   / 24;
                d_seconds   %= 60;
                d_minutes   %= 60;
                d_hours     %= 24;

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

    int main(int argc, char **argv)
    {
        vector<Time> tvector;

        tvector.push_back(Time( 1, 10, 20));
        tvector.push_back(Time(10, 30, 40));
        tvector.push_back(Time(20, 50,  0));
        tvector.push_back(Time(30, 20, 30));

        cout <<
            accumulate
            (
                tvector.begin(), tvector.end(), Time(0, 0, 0), plus<Time>()
            ) <<
            endl;
    }
    /*
        produced output:

        2 days, 14 hours, 51 minutes and 30 seconds.
    */

Considering the previous discussion of the plus function object, the example is pretty straightforward. The class Time defines a constructor, it defines an insertion operator and it defines its own operator+(), adding two time objects.

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

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

The following arithmetic objects are available as predefined objects:

• plus<>(): as shown, this object's operator()() member calls operator+() as a binary operator, passing it its two parameters, returning operator+()'s return value.
• minus<>(): this object's operator()() member calls operator-() as a binary operator, passing it its two parameters and returning operator-()'s return value.
• multiplies<>(): this object's operator()() member calls operator*() as a binary operator, passing it its two parameters and returning operator*()'s return value.
• divides<>(): this object's operator()() member calls operator/(), passing it its two parameters and returning operator/()'s return value.
• modulus<>(): this object's operator()() member calls operator%(), passing it its two parameters and returning operator%()'s return value.
• negate<>(): this object's operator()() member calls operator-() as a unary operator, passing it its parameter and returning the unary operator-()'s return value.

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

    int main(int argc, char **argv)
    {
        int iArr[] = { 1, -2, 3, -4, 5, -6 };

        transform(iArr, iArr + 6, iArr, negate<int>());

        for (int idx = 0; idx < 6; ++idx)
            cout << iArr[idx] << ", ";

        cout << endl;
    }
    /*
        Generated output:

        -1, 2, -3, 4, -5, 6,
    */

18.1.2: Relational function objects

• equal_to<>(): this object's operator()() member calls operator==() as a binary operator, passing it its two parameters and returning operator==()'s return value.
• not_equal_to<>(): this object's operator()() member calls operator!=() as a binary operator, passing it its two parameters and returning operator!=()'s return value.
• greater<>(): this object's operator()() member calls operator>() as a binary operator, passing it its two parameters and returning operator>()'s return value.
• greater_equal<>(): this object's operator()() member calls operator>=() as a binary operator, passing it its two parameters and returning operator>=()'s return value.
• less<>(): this object's operator()() member calls operator<() as a binary operator, passing it its two parameters and returning operator<()'s return value.
• less_equal<>(): this object's operator()() member calls operator<=() as a binary operator, passing it its two parameters and returning operator<=()'s return value.

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

    int main(int argc, char **argv)
    {
        sort(argv, argv + argc, greater_equal<string>());

        for (int idx = 0; idx < argc; ++idx)
            cout << argv[idx] << " ";
        cout << endl;

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

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

Note that the type of the elements of argv is char *, and that the relational function object expects a string. The relational object greater_equal<string>() will therefore use the >= operator of strings, but will be called with char * variables. The promotion from char const * to string is performed silently.

18.1.3: Logical function objects

• logical_and<>(): this object's operator()() member calls operator&&() as a binary operator, passing it its two parameters and returning operator&&()'s return value.
• logical_or<>(): this object's operator()() member calls operator||() as a binary operator, passing it its two parameters and returning operator||()'s return value.
• logical_not<>(): this object's operator()() member calls operator!() as a unary operator, passing it its parameter and returning the unary operator!()'s return value.

    #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 << endl;

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

        for (size_t idx = 0; idx < bArrSize; ++idx)
            cout << bArr[idx] << " ";
        cout << endl;
    }
    /*
        generated output:

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

18.1.4: Function adaptors

• Binders are function adaptors converting binary function objects to unary function objects. They do so by binding one object to a constant function object. For example, with the minus<int>() function object, which is a binary function object, the first argument may be bound to 100, meaning that the resulting value will always be 100 minus the value of the second argument. Either the first or the second argument may be bound to a specific value. To bind the first argument to a specific value, the function object bind1st() is used. To bind the second argument of a binary function to a specific value bind2nd() is used. As an example, assume we want to count all elements of a vector of Person objects that exceed (according to some criterion) some reference Person object. For this situation we pass the following binder and relational function object to the count_if() generic algorithm:

      bind2nd(greater<Person>(), referencePerson)
  

  What would such a binder do? First of all, it's a function object, so it needs operator()(). Next, it expects two arguments: a reference to another function object and a fixed operand. Although binders are defined as templates, it is illustrative to have a look at their implementations, assuming they were straight functions. Here is such a pseudo-implementation of a binder:

      class bind2nd
      {
          FunctionObject const &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_rvalue);
      }
  

  When its operator()() member is called the binder merely passes the call to the object's operator()(), providing it with two arguments: the lvalue it itself received and the fixed operand it received via its constructor. Note the simplicity of these kind of classes: all its members can usually be implemented inline.

  The count_if() generic algorithm visits all the elements in an iterator range, returning the number of times the predicate specified as its final argument returns true. Each of the elements of the iterator range is given to the predicate, which is therefore a unary function. By using the binder the binary function object greater() is adapted to a unary function object, comparing each of the elements in the range to the reference person. Here is, to be complete, the call of the count_if() function:

      count_if(pVector.begin(), pVector.end(),
          bind2nd(greater<Person>(), referencePerson))
  

• Negators are function adaptors converting the truth value of a predicate function. Since there are unary and binary predicate functions, there are two negator function adaptors: not1() is the negator used with unary function objects, not2() is the negator used with binary function objects.

• Use a binary predicate that directly offers the required comparison:

      count_if(pVector.begin(), pVector.end(),
          bind2nd(less_equal<Person>(), referencePerson))
  

• Use not2 combined with the greater() predicate:

      count_if(pVector.begin(), pVector.end(),
          bind2nd(not2(greater<Person>()), referencePerson))
  

  Note that not2() is a negator negating the truth value of a binary operator()() member: it must be used to wrap the binary predicate greater<Person>(), negating its truth value.
• Use not1() combined with the bind2nd() predicate:

      count_if(pVector.begin(), pVector.end(),
          not1(bind2nd(greater<Person>(), referencePerson)))
  

  Note that not1() is a negator negating the truth value of a unary operator()() member: it is used to wrap the unary predicate bind2nd(), negating its truth value.

  The following little example illustrates the use of negator function adaptors, completing the section on function objects:

      #include <iostream>
      #include <functional>
      #include <algorithm>
      #include <vector>
      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)) <<
              endl;
          cout << count_if(iArr, iArr + 10, bind2nd(not2(greater<int>()), 6)) <<
              endl;
          cout << count_if(iArr, iArr + 10, not1(bind2nd(greater<int>(), 6))) <<
              endl;
      }
      /*
          produced output:
  
          6
          6
          6
      */
  

• The binder's operator()() is called;
• The operation <= is performed for int values.

• The binder's operator()() is called;
• The negator's operator()() is called;
• The operation > is performed for int values.

• The negator's operator()() is called;
• The binder's operator()() is called;
• The operation > is performed for int values.

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

18.2: Iterators

• Two iterators may be compared for (in)equality using the == and != operators. Note that the ordering operators (e.g., >, <) normally cannot be used.
• Given an iterator iter, *iter represents the object the iterator points to (alternatively, iter-> can be used to reach the members of the object the iterator points to).
• ++iter or iter++ advances the iterator to the next element. The notion of advancing an iterator to the next element is consequently applied: several containers have a reversed_iterator type, in which the iter++ operation actually reaches a previous element in a sequence.
• Pointer arithmetic may be used with containers having their elements stored consecutively in memory. This includes the vector and deque. For these containers iter + 2 points to the second element beyond the one to which iter points.
• An interator which is merely defined is comparable to a 0-pointer, as shown by the following little example:

      #include <vector>
      #include <iostream>
      using namespace std;
  
      int main()
      {
          vector<int>::iterator vi;
  
          cout << &*vi << endl;       // prints 0
      }
  

The following example shows a situation where all elements of a vector of strings are written to cout using the iterator range [begin(), end()), and the iterator range [rbegin(), rend()). The following example shows 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 explicit 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 << endl;

        for (auto iter = args.rbegin(); iter != args.rend(); ++iter)
            cout << *iter << " ";
        cout << endl;

        return 0;
    }

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

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

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

        for
        (
            vector<string>::const_iterator iter = args.begin();
                iter != args.end();
                    ++iter
        )
            cout << *iter << " ";
        cout << endl;

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

        return 0;
    }

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

• operator==(), testing two iterators for equality,
• operator++(), incrementing the iterator, as prefix operator,
• operator*(), to access the element the iterator refers to,

• InputIterators.

  InputIterators can read from a container. The dereference operator is guaranteed to work as rvalue in expressions. Instead of an InputIterator it is also possible to (see below) use a Forward-, Bidirectional- or RandomAccessIterator. With the generic algorithms presented in this chapter. Notations like InputIterator1 and InputIterator2 may be observed as well. In these cases, numbers are used to indicate which iterators `belong together'. E.g., the generic function inner_product() has the following prototype:

      Type inner_product(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, Type init);
  

  Here InputIterator1 first1 and InputIterator1 last1 are a set of input iterators defining one range, while InputIterator2 first2 defines the beginning of a second range. Analogous notations like these may be observed with other iterator types.

• OutputIterators:

  OutputIterators can be used to write to a container. The dereference operator is guaranteed to work as an lvalue in expressions, but not necessarily as rvalue. Instead of an OutputIterator it is also possible to use, see below, a Forward-, Bidirectional- or RandomAccessIterator.

• ForwardIterators:

  ForwardIterators combine InputIterators and OutputIterators. They can be used to traverse containers in one direction, for reading and/or writing. Instead of a ForwardIterator it is also possible to use a Bidirectional- or RandomAccessIterator.

• BidirectionalIterators:

  BidirectionalIterators can be used to traverse containers in both directions, for reading and writing. Instead of a BidirectionalIterator it is also possible to use a RandomAccessIterator. For example, to traverse a list or a deque a BidirectionalIterator may be useful.

• RandomAccessIterators:

  RandomAccessIterators provide random access to container elements. An algorithm such as sort() requires a RandomAccessIterator, and can therefore not be used with lists or maps, which only provide BidirectionalIterators.

18.2.1: Insert iterators

In situations like these, an inserter adaptor function may be used to create elements in the destination container when they are needed. There are three types of inserter() adaptors:

• back_inserter(): calls the container's push_back() member to add new elements at the end of the container. E.g., to copy all elements of source in reversed order to the back of destination:

      copy(source.rbegin(), source.rend(), back_inserter(destination));
  

• front_inserter() calls the container's push_front() member to add new elements at the beginning of the container. E.g., to copy all elements of source to the front of the destination container (thereby also reversing the order of the elements):

      copy(source.begin(), source.end(), front_inserter(destination));
  

• inserter() calls the container's insert() member to add new elements starting at a specified starting point. E.g., to copy all elements of source to the destination container, starting at the beginning of destination, shifting existing elements beyond the newly inserted elements:

      copy(source.begin(), source.end(), inserter(destination,
          destination.begin()));
  

    typedef DataType const &const_reference;

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

    class Y
    {
        public:
            typedef int const &const_reference;

            void push_back(int const &)
            {}
    };

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

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

18.2.2: Iterators for `istream' objects

    istream_iterator<Type> identifier(istream &inStream)

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

    istream_iterator<string> endOfStream;

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

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

    int main()
    {
        vector<string> vs;

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

        for
        (
            vector<string>::iterator from = vs.begin();
                from != vs.end();
                    ++from
        )
            cout << *from << " ";
        cout << endl;

        return 0;
    }

    istream_iterator<string> eos;

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

    #include <iterator>

18.2.3: Iterators for `istreambuf' objects

    #include <iterator>

• istreambuf_iterator<Type>():

  This constructor represents the end-of-stream iterator while extracting values of type Type from the streambuf.

• istreambuf_iterator<Type>(istream):

  This constructor constructs an istreambuf_iterator accessing the streambuf of the istream object, used as the constructor's argument.

• istreambuf_iterator<Type>(streambuf *):

  This constructor constructs an istreambuf_iterator accessing the streambuf whose address is used as the constructor's argument.

18.2.4: Iterators for `ostream' objects

    ostream_iterator<Type> identifier(ostream &outStream), // and:
    ostream_iterator<Type> identifier(ostream &outStream, char const *delim);

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

    #include <iterator>

18.2.4.1: Iterators for `ostreambuf' objects

    #include <iterator>

• ostreambuf_iterator<Type>(ostream):

  This constructor constructs an ostreambuf_iterator accessing the streambuf of the ostream object, used as the constructor's argument, to insert values of type Type.

• ostreambuf_iterator<Type>(streambuf *):

  This constructor constructs an ostreambuf_iterator accessing the streambuf whose address is used as the constructor's argument.

    #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' (C++0x)

    void fun()
    {
        new int;
    }

    void fun()
    {
        delete new int;
    }

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

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

    #include <memory>

The following should be considered when using unique_ptrs:

• when assigning a unique_ptr to another move semantics is used. If move semantics are not available compilation will fail. On the other hand, if compilation succeeds then the used containers or generic algorithms support the use of unique_ptrs. Here is an example:

      std::unique_ptr<int> up1(new int);
      std::unique_ptr<int> up2 = up1;      // compilation error
  

  The second definition fails to compile since unique_ptr's copy constructor is private (the same holds true for the assignment operator). The unique_ptr class does offer facilities to initialize and assign from rvalue references:

      class unique_ptr                        // interface partially shown
      {
          public:
              unique_ptr(unique_ptr &&other); // rvalues bind here
          private:
              unique_ptr(const unique_ptr &other);
      };
  

  Consequently, in the above example move semantics should be used. E.g.,

      std::unique_ptr<int> up1(new int);
      std::unique_ptr<int> up2 = std::move(up3);
  

• a unique_ptr object should only point to memory that was made available dynamically, as only dynamically allocated memory can be deleted.
• multiple unique_ptr objects should not be allowed to point to the same block of dynamically allocated memory. The unique_ptr's interface was designed to prevent this from happening. Once an unique_ptr object goes out of scope, it deletes the memory it points to, immediately changing any other object also pointing to the allocated memory into a wild pointer.

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. It also augments auto_ptr as it can be used with containers and algorithms; as it adds customizable deleters and as it adds the possibility to handle arrays.

18.3.1: Defining `unique_ptr' objects (C++0x)

• The basic form initializes an unique_ptr object to point to a block of memory allocated by the new operator:

      unique_ptr<type> identifier (new-expression [, deleter]);
  

  This form is discussed in section 18.3.2.
• Another form initializes an unique_ptr object using move semantics, either supported by the data type itself or forced using std::move:

      // type must support move semantics or std::move(other) must be used
      unique_ptr<type> identifier(another unique_ptr for type);
  

  This form is discussed in section 18.3.4.
• The third form simply creates an unique_ptr object that does not point to a particular block of memory:

      unique_ptr<type> identifier;
  

  This form is discussed in section 18.3.5.

18.3.2: Pointing to a newly allocated object (C++0x)

    unique_ptr<type [, deleter_type]> identifier(new-expression
            [, deleter = deleter_type()]);

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

    unique_ptr<string> strPtr(new string("Hello world"));

    unique_ptr<double> dPtr(new double(123.456));

The next example shows how an explicitly defined deleter may be used to delete a dynamically allocated array of pointers to strings. Instead of using a template value parameter the deleter's constructor could of course also be given a parameter initializing the deleter with the number of elements to delete:

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

    template <typename Type, size_t size>
    struct D2
      {
        void operator()(Type * ptr) const
        {
            for (size_t idx = 0; idx < size; ++idx)
                delete ptr[idx];
            delete ptr;
        }
    };
    int main()
    {
        unique_ptr<int *, D2<int *, 10>> sp2(new int *[10]);

        D2<int *, 10> &obj = sp2.get_deleter();
    }

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

    #include <memory>
    using namespace std;

    void fun()
    {
        unique_ptr<int> ip(new int);
    }

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

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

        cout << *sp << endl;
        sp->insert(strlen("Hello "), "C++ ");
        cout << *sp << endl;
    }
    /*
        produced output:

        Hello world
        Hello C++ world
    */

18.3.3: Using `unique_ptr' objects for arrays (C++0x)

When using smart pointers (unique_ptr and shared_ptr, see section 18.4) to handle arrays the following additional syntax is available:

• To define an smart pointer for an array, the [] notation is used. E.g.,

      unique_ptr<int[]> intArr(new int[3]);
  

• The index operator is availabe. E.g.,

      intArr[2] = intArr[0];
      it() The default deleter will use tt(delete[]).
  

18.3.4: Moving another `unique_ptr' (C++0x)

    unique_ptr<type> identifier(other unique_ptr object);

    unique_ptr<string> sp2(move(sp));

Analogously, the assignment operator can be used. An unique_ptr object may be assigned to another unique_ptr object of the same type, again using move-semantics. 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 << endl <<   // would segfault
                // *hello2 << endl <<   // same
                *hello3 << endl;
    }
    /*
        Produced output:

        Hello world
    */

• hello1 is initialized as described in the previous section.
• Next hello2 is defined, and it receives its value from hello1 using a move constructor initialization. This effectively changes hello1 into a 0-pointer.
• Then hello3 is defined as a default unique_ptr<string>, but it receives its value through a move-assignment from hello2, which then becomes a 0-pointer too.

18.3.5: Creating a plain `unique_ptr' (C++0x)

    unique_ptr<type> identifier;

    unique_ptr<int> ip;

    if (!ip)
        cout << "0-pointer with a unique_ptr object" << endl;

18.3.6: Operators and members (C++0x)

• unique_ptr &unique_ptr<Type>operator=(unique_ptr<Type> &other):

  This operator will transfer the memory pointed to by the rvalue unique_ptr object to the lvalue unique_ptr object using move semantics. So, the rvalue object loses the memory it pointed at, and turns into a 0-pointer.

• unique_ptr &unique_ptr<Type>operator bool() const:

  This operator returns false if the unique_ptr does not point to memory (i.e., its get() member, see below, returns 0). Otherwise, true is returned.

• Type &unique_ptr<Type>operator*():

  This operator returns a reference to the information stored in the unique_ptr object. It acts like a normal pointer dereference operator.

• Type *unique_ptr<Type>operator->():

  This operator returns a pointer to the information stored in the unique_ptr object. Through this operator members of a stored object can be selected. For example:

      unique_ptr<string> sp(new string("hello"));
  
      cout << sp->c_str() << endl;
  

• Type *unique_ptr<Type>::get():

  This member does the same as operator->(): it returns a pointer to the information stored in the unique_ptr object. This pointer can be inspected: if it's zero the unique_ptr object does not point to any memory. This member cannot be used to let the unique_ptr object point to (another) block of memory.

• Deleter &unique_ptr<Type>::get_deleter():

  This member returns a reference to the deleter class object used by the unique_ptr.

• Type *unique_ptr<Type>::release():

  This member returns a pointer to the information stored in the unique_ptr object, which loses the memory it pointed at (and changes into a 0-pointer). The member can be used to transfer the information stored in the unique_ptr object to a plain Type pointer. It is the responsibility of the programmer to delete the memory returned by this member function.

• void unique_ptr<Type>::reset(Type *):

  This member may also be called without argument, to delete the memory stored in the unique_ptr object, or with a pointer to a dynamically allocated block of memory, which will thereupon be the memory accessed by the unique_ptr object. This member function can be used to assign a new block of memory (new content) to an unique_ptr object.

• void unique_ptr<Type>::swap(unique_ptr<Type> &&):

  This member is used to swap two identically typed unique_ptrs.

18.3.7: The legacy class 'auto_ptr' (deprecated)

The std::unique_ptr, available since the C++0x standard does not have auto_ptr's drawbacks and consequently using auto_ptr is now deprecated.

The following restrictions apply to auto_ptrs:

• the auto_ptr class does not support move semantics;
• the auto_ptr object cannot be used to point to arrays of objects;
• the auto_ptr cannot be used as a data type of abstract containers.

No further coverage of the auto_ptr class is offered by the C++ Annotations. Existing software should be modified to use unique_ptrs, newly designed software should avoid using auto_ptr objects.

18.4: The class 'shared_ptr' (C++0x)

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

Different from unique_ptrs shared_ptrs support copy constructors and standard overloaded assignment operators. Since shared_ptrs share the memory they point at move semantics is not a requirement.

As with unique_ptr a shared_ptr may refer to a dynamically allocated array.

18.4.1: Defining `shared_ptr' objects (C++0x)

• The basic form initializes an shared_ptr object to point to a block of memory allocated by the new operator:

      shared_ptr<type> identifier (new-expression [, deleter]);
  

  This form is discussed in section 18.4.2.

• Shared pointers support copy construction. When copy constructing a shared pointer both shared_ptr objects point at the same memory, and the object's reference count is incremented.

• Another form initializes an shared_ptr object using move semantics, either supported by the data type itself or forced using std::move:

      // type must support move semantics or std::move(other) must be used
      shared_ptr<type> identifier(a temporary shared_ptr for type);
  

  This form is discussed in section 18.4.3.
• The third form simply creates an shared_ptr object that does not point to a particular block of memory:

      shared_ptr<type> identifier;
  

  This form is discussed in section 18.4.4.

18.4.2: Pointing to a newly allocated object (C++0x)

    shared_ptr<type [, deleter_type]> identifier(new-expression
            [, deleter = deleter_type()]);

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

    shared_ptr<string> strPtr(new string("Hello world"));

All member functions available for objects allocated by the new expression can be reached via the shared_ptr as if it was a plain pointer to the dynamically allocated object. For example, in the following program the text `C++' is inserted behind the word `hello'. This example also shows the use of a copy constructed shared pointer and it shows that following the copy construction both objects point at the same information:

    #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 << endl;
    }
    /*
        produced output:

        Hello C++ world
        Hello C++ world
    */

18.4.3: Initializing from a temporary `shared_ptr' (C++0x)

    std::shared_ptr<std::string> &&makeString(char const *text)
    {
        return std::move(shared_ptr<string>(new std::string(text)));
    }
    std::shared_ptr<std::string> shared(makeString("hello world"));

18.4.4: Creating a plain `shared_ptr' (C++0x)

    shared_ptr<type> identifier;

    shared_ptr<int> ip;

    if (!ip)
        cout << "0-pointer with a shared_ptr object" << endl;

18.4.5: Operators and members (C++0x)

• shared_ptr &shared_ptr<Type>operator=(shared_ptr<Type> &other):

  This operator reduces the reference count of the left-hand side object, deleting its memory when its count decays to zero, and sets its pointer to the memory pointed at by right-hand side object, incrementing its reference count.

• shared_ptr &shared_ptr<Type>operator bool() const:

  This operator returns false if the shared_ptr does not point to memory (i.e., its get() member, see below, returns 0). Otherwise, true is returned.

• Type &shared_ptr<Type>operator*():

  This operator returns a reference to the information stored in the shared_ptr object. It acts like a normal pointer dereference operator.

• Type *shared_ptr<Type>operator->():

  This operator returns a pointer to the information stored in the shared_ptr object. Through this operator members of a stored object can be selected. For example:

      shared_ptr<string> sp(new string("hello"));
  
      cout << sp->c_str() << endl;
  

The following member functions are defined for shared_ptr objects:

• Type *shared_ptr<Type>::get():

  This member does the same as operator->(): it returns a pointer to the information stored in the shared_ptr object. This pointer can be inspected: if it's zero the shared_ptr object does not point to any memory. This member cannot be used to let the shared_ptr object point to (another) block of memory.

• Deleter &shared_ptr<Type>::get_deleter():

  This member returns a reference to the deleter class object used by the shared_ptr.

• Type *shared_ptr<Type>::release():

  This member returns a pointer to the information stored in the shared_ptr object, which loses the memory it pointed at (and changes into a 0-pointer). The member can be used to transfer the information stored in the shared_ptr object to a plain Type pointer. It is the responsibility of the programmer to delete the memory returned by this member function.

• void shared_ptr<Type>::reset(Type *):

  This member may also be called without argument, to delete the memory stored in the shared_ptr object, or with a pointer to a dynamically allocated block of memory, which will thereupon be the memory accessed by the shared_ptr object. This member function can be used to assign a new block of memory (new content) to an shared_ptr object.

• void shared_ptr<Type>::swap(shared_ptr<Type> &&):

  This member is used to swap two identically typed shared_ptrs.

• bool shared_ptr<Type>unique() const:

  This member returns true if the memory is referenced by the current object only and returns false otherwise

  .

• size_t shared_ptr<Type>use_count() const:

  This member returns the number of objects sharing the memory pointed at by their data pointers.

18.4.6: Class constructors and pointer data members (C++0x)

    // required #includes

    class Map
    {
        std::map<string, Data> *d_map;
        public:
            Map(char const *filename) throw(std::exception);
    };

• It allocates a std::map object;
• It opens the file whose name is given as the constructor's argument;
• It reads the file, thereby filling the map.

    Map::Map(char const *fname)
    :
        d_map(new std::map<std::string, Data>) throw(std::exception)
    {
        ifstream istr(fname);
        if (!istr)
            throw std::exception("can't open the file");
        fillMap(istr);
    }

Shared_ptrs (as well as unique_ptrs, cf. section 18.3) may be used to prevent these kinds of problems. By defining d_map as

        std::shared_ptr<std::map<std::string, Data> >

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

18.5: Multi Threading (C++0x)

The Annotations don't aim at introducing the concepts behind multi threading. It is a topic by itself and many good reference sources exist (cf. Nichols, B, et al.'s Pthreads Programming, O'Reilly for a good introduction to multi-threading).

Multi threading facilities are offered through the class std::thread. Its constructor and assignment operator accept a function (object) that will handle the thread created by the thread object.

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

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 the source file multi.cc the compiler is called as follows:

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

Threads in C++ are very much under development. It is likely that in the near future features will be added and possibly redefined. The sections below should therefore be read with this in mind.

18.5.1: The class 'std::thread' (C++0x)

Alternatively, a function or function object may be assigned to an existing thread object causing a new thread to be launched using that function (object).

There are several ways to end a launched thread. Currently a thread ends when the function called from the thread object ends. Since the thread object not only accepts functions but also function objects as its argument, a local context may be passed on to the the thread. Here are two examples of how a thread may be started: in the first example a function is passed on to the thread, in the second example a function object:

    #include <iostream>
    #include <thread>
    #include <cstdlib>
    using namespace std;

    void hello()
    {
        cout << "hello world\n";
    }

    class Zero
    {
        int *d_data;
        size_t d_size;
        public:
            Zero(int *data, size_t size)
            :
                d_data(data),
                d_size(size)
            {}
            void operator()(int arg) const
            {
                for (int *ptr = d_data + d_size; ptr-- != d_data; )
                    *ptr = 0;
            }
    };

    int main()
    {
        int data[30];
        Zero zero(data, 30);
        int value = 0;
        std::thread t1(zero, value);
        std::thread t2(hello);
    };

Thread objects do not implement a copy constructor, but a move constructor is provided. Threads may be swapped as well, even if they're actually running a thread. E.g.,

    std::thread t1(Thread());
    std::thread t2(Thread());
    t1.swap(t2);

According to the current specifications of the thread class its constructor should also be able to accept additional arguments (in addition to the function (object) handled by the thread object), but currently that facility does not appears to be very well implemented. Any objects otherwise passed to the function call operator could of course also be passed using separate members or via the object's constructors, which is probably an acceptable makeshift solution until multiple arguments can be passed to the thread constructor itself (using perfect forwarding, cf. section 21.5.2).

The thread's overloaded assigment operator can also be used to start a thread. If the current thread object actually runs a thread it is stopped, and the function (object) assigned to the thread object becomes the new running thread. E.g.,

    std::thread thr;    // no thread runs from thr yet
    thr = Thread();     // a thread is launched

Threads (among which the thread represented by main) may be forced to wait for another threds's completion by calling the other thread's join() member. E.g., in the following example main launches two threads and wait for the completion of both:

    int main()
    {
        std::thread t1(Thread());
        std::thread t2(Thread());

        t1.join();      // wait for t1 to complete
        t2.join();      // same, t2
    }

The thread's member detach() can be called to disassociate the current thread from its starting thread. Ending a thread other than ending the activities of the function defining the thread's activities appears currently very well implemented.

18.5.2: Synchronization (mutexes) (C++0x)

In many situations locks will be released at the end of some action block. To simplify locking additional template classes std::unique_lock<> and std::lock_guard<> are provided. As their constructor locks the data and their destructor unlocks the data they can be defined as local variables, unlocking their data once their scope terminates. Here is a simple example showing its use; at the end of safeProcess 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);
    }

    std::timed_mutex dataMutex;
    Data data;

    void safeProcess()
    {
        std::unique_lock<std::timed_mutex>
            guard(dataMutex, std::chrono::milliseconds(3));
        if (guard)
            process(data);
    }

A common cause of problems with multi threaded programs is the occurrence of deadlocks. If a deadlock may occur when two locks are required to process data, but one thread obtains the first lock and another thread obtains the second lock. The C++0x standard defines a generic std::lock function that may be used to prevent problems like these. 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);
    }

Another problematic issue with threads involves initialization. If multiple threads are running and only the first thread encountering the initialization code should perform the initialization then this problem should not be solved by mutexes. Although the synchronization is accomplished, it will needlessly be accomplished time and again once the initialization phase has been completed. The C++0x standard offers several ways to perform a proper initialization:

• First, a constexpr constructor may be defined. Constexpr constructors are currently not yet supported by the g++ compiler and its discussion is therefore postponen.

• Second, a static variable defined within a compound statement may be used (e.g., a static local variable within a function body). block scope may be used. In C++ static variables defined within a compund statement are initialized the first time the function is called at the point in the code where the static variable is defined as illustrated by the following example:

          #include <iostream>
  
          struct Cons
          {
              Cons()
              {
                  std::cout << "Cons called\n";
              }
          };
  
          void called(char const *time)
          {
              std::cout << time << "time called() activated\n";
              static Cons cons;
          }
  
          int main()
          {
              std::cout << "Pre-1\n";
              called("first");
              called("second");
              std::cout << "Pre-2\n";
              Cons cons;
          }
      /*
          Generated output:
  
                  Pre-1
                  firsttime called() activated
                  Cons called
                  secondtime called() activated
                  Pre-2
                  Cons called
      */
  

  This feature causes a thread to wait automatically if another thread is still initializing the static data (note that non-static data never cause problems, as each non-static local variables have lifes that are completely restricted to their own threads).
• If the above two approaches can't be used. The combined use of std::call_once and std::once_flag result in the one-time execution of a specified function as illustrated by the next example:

      std::string *global;
      std::once_flag globalFlag;
  
      void initializeGlobal()
      {
          global = new std::string("Hello world (why not?)");
      }
  
      void safeUse()
      {
          std::call_once(globalFlag, initializeGlobal);
          process(*global);
      }
  

Mutexes may be used in C++0x after including the header file mutex.

18.5.3: Event handling (condition variables) (C++0x)

At some point the producer will therefore have to wait until the client has consumed enough and there's space available in the producer's storage. Similarly, the client will have to wait until the producer has produced some more items.

Locking and polling the amount of available items/storage at fixed time intervals usually isn't a good option as it is in principle a wasteful scheme: threads continue to wait during the full interval even though the condition to continue may already have been met; reducing the interval, on the other hand, isn't an attractive option either as it results in a relative increase of the overhead associated with handling the associated mutexes.

Condition variables may be used to solve these kinds of problems. A thread simply sleeps until it is notified by another thread. In general terms this may be accomplished as follows:

    producer loop:
        - produce the next item
        - wait until there's room to store the item,
            then reduce the available room
        - 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:

• Get a lock on the variable containing the actual count
• As long as the count is zero: wait, relase the lock until another thread has increased the count, re-acquire the lock.
• Reduce the count
• Release the lock.

    void down()
    {
        unique_lock<mutex> lk(sem_mutex);   // get the lock
        while (semaphore == 0)
            condition.wait(lk);             // see 1, below.
        --semaphore;                        // dec. semaphore count
    }                                       // the lock is released

What about notifying the condition variable? This is handled by the `increment the number ...' parts in the abovementioned produced and consumer loops. These parts are defined by the following up() function, implemented as follows:

    void up()
    {
        lock_guard<std::mutex> lk(sem_mutex);   // get the lock
        if (semaphore++ == 0)
            condition.notify_one();             // see 2, below
    }                                           // the lock is released

Handling semaphore can very well be implemented in a class Semaphore, offering members down() and up(). For a more extensive discussion of semaphores see Tanenbaum, A.S. (2006) Structured Computer Organization, Pearson Prentice-Hall.

Using the semaphore facilities, embedded in a class Semaphore whose constructor expects an initial value of its semaphore data member, the classic producer and consumer case 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();
        return 0;
    }

To use condition_variable objects the header file condition_variable must be included.

18.6: Lambda functions (C++0x)

As we've seen the generic algorithms often accept an argument which can either be a function object or 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 will do.

The function or function object is usually not readily available. Often it must be defined in or near the function using the generic algorithm. Often the software engineer will resort to anonymous namespaces in which a class or function is defined that is thereupon used in the function calling the generic algorithm. If that function is itself a member function the need may be felt to access other members of its class from the function called by the generic algorithm. Often this results in a significant amount of code (defining the class), in complex code (to make available software elements that aren't native to the called function (object)), and -at the level of the source file- code that is irrelevant at the current level of specification. Nested classes don't solve these problems and, moreover, nested classes can't be used in templates.

Solutions to the above problems exist. In section 23.8 a general approach is discussed allowing the use of members and/or local variables in the context of a function or function object called from generic algorithms.

However, the solutions given in section 23.8 are in fact makeshift solutions that need to be used as long as the language doesn't offer lambda functions. A lambda function is an anonymous function. Such a function may be defined on the spot, and will exist only during the lifetime of the statement of which it is a part.

Here is an example of the definition of a lambda function:

    [](int x, int y)
    {
        return x * y;
    }

    cout << accumulate(vi.begin(), vi.end(), 1,
                [](int x, int y) { return x * y; });

Alternatively, the return type can be explicitly specified using a late-specified return type, (cf. section 3.3.5):

    [](int x, int y) -> int
    {
        int z = x + y;
        return z + x;
    }

Variables having the same scope as the lambda function can be accessed from the lambda function using references. This allows passing the local context to a lambda function. Such variables are called a closure. Here is an example:

    void showSum(vector<int> &vi)
    {
        int total = 0;
        for_each(
            vi.begin(), vi.end(),
            [&total](int x)
            {
                total += x;
            }
        );
        std::cout << total;
    }

If a closure variable is defined without the reference symbol it becomes a simple value which is initialized by the local variable when the lambda function is passed to the generic algorithm. Usually closure variables are passed by reference. If all local variables are to be passed by reference the notation [&] can be used (to pass the full closure by value use [=]):

    void show(vector<int> &vi)
    {
        int sum = 0;
        int prod = 1;
        for_each(
            vi.begin(), vi.end(),
            [&](int x)
            {
                sum += x;
                prod *= x;
            }
        );
        std::cout << sum << ' ' << prod;
    }

Combinations of variables passed by value, but some by reference or passed by reference but some by value is possible. In that case the default is followed by a list of variables passed differently. E.g.,

    [&, value](int x)
    {
        total +=  x * value;
    };

Within a class context, members may define lambda functions as well. In those cases the lambda function has full access to all the class's members. In other words, it is defined as a friend of the class. For example:

    class Data
    {
        std::vector<std::string> d_names;

        public:
            void show() const;
            {
                int count = 0;
                std::for_each(d_names.begin(), d_end(),
                    [this, &count](std::string const &name)
                    {
                        std::cout << ++count <<
                            this->capitalized(name) << endl;
                    }
                )
            }
        private:
            std::string capitalized(std::string const &name);
    }

                    [&](std::string const &name)
                    {
                        std::cout << ++count <<
                            this->capitalized(name) << endl;
                    }

    auto lambdaFun = [this]()
                     {
                        this->member();
                     };

Lambda functions are not yet supported by the g++ compiler.

18.7: Polymorphous wrappers for function objects (C++-0x)

To accomodate for these situations the C++0x standard introduces polymorphous (function object) wrappers. Polymorphous wrappers can refer to function pointers, member functions or functors, as long as they match in type and number of their parameters.

Polymorphous wrappers are not yet fully supported by the g++ compiler.

18.8: Randomization and Mathematical Distributions (C++0x)

Using these distrbutions is based on new randum number generator functions, differing from the traditional rand(3) function provided by the C standard library. These random number generators are used to produce pseudo-random numbers, which are then filtered through a particular distribution to obtain values that are randomly selected from the specified distributino.

18.8.1: Random Number Generators (C++0x)

The linear_congruential random number generator computes

    linear_congruential<int, 10, 3, 13> lc;

The subtract_with_carry random number generator computes

    subtract_with_carry<int, 13, 3, 13> sc;

The predefined mersenne_twister mt19937 (predefined using a typedef defined by the random header file) is used in the examples below. It can be constructed using std::mt19937 mt or it can be seeded using an argument (e.g., std::mt19937 mt(time(0))). Other ways to initialize the mersenne_twister are byond 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() which accepts an unsigned long or a generator function (e.g., lc.seed(lc), lc.seed(mt)).

The random number generators implement 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 changing its range.

18.8.2: Mathematical distributions (C++0x)

All distributions offer the following members (result_type being the type name of the values returned by the distribution, distribution-name being the type name of the mathematical distribution, e.g., bernoulli_distribution):

• result_type operator()(RandomNumberGenerator): The next randomly generated value is returned.
• std::istream &operator<<(std::istream &in, distribution-name &object): A parameters of the distribution are extracted from an std::istream;
• std::ostream &operator<<(std::ostream &out, bernoulli_distribution const &bd): A parameters of the distribution are inserted into an std::ostream

Distributions:

• bernoulli_distribution
  Logical true values are generated with a certain probability p.
  Constructor:
  • bernoulli_distribution(double p = 0.5)
    

• binomial_distribution<IntType = int, RealType = double>
IntType: the type of the generated random value (by default int).
  RealType: the probability parameter of the binomial distribution.
  Random integral values are generated according to the specified binomial distributionnl() Constructor:
  • binomial_distribution<IntType, RealType>(IntType t, RealType p =RealType(0.5))

• gamma_distribution<Type = double>
Type: the parameter of the gamma distribution.
  Random values are generated according to the specified gamma distribution.
  Constructor:
  • gamma_distribution<IntType, Type>(Type alpha = Type(1))
    

• geometric_distribution<IntType = int, RealType = double>
IntType: the type of the generated random value (by default int).
  RealType: the probability parameter of the geometric distribution.
  Random integral values are generated according to the specified geometric distributionnl() Constructor:
  • geometric_distribution<IntType, RealType>(RealType p = RealType(0.5))
    

• exponential_distribution<Type = double>
Type: the parameter of the exponential distribution.
  Random integral values are generated according to the specified exponential distributionnl() Constructor:
  • exponential_distribution<IntType, Type>(Type lambda = Type(1))
    

• normal_distribution<Type = double>
Type: the type of the generated random value (by default double).
  Constructor:
  • normal_distribution<Type>(ReadType mean = Type(0), Type sigma = Type(1))
    

• poisson_distribution<IntType = int, RealType = double>
IntType: the type of the generated random value (by default int).
  RealType: the type of the parameter of the distribution (by default double).
  Random integral values are generated that are distributed according to a poisson distribution with parameter mean. Constructor:
  • poisson_distribution<IntType, RealType>(RealType mean = RealType(1))
    

• uniform_int<Type = int>
Type: the type of the generated random value (by default int).
  Random integral values are generated that are uniformly distributed over a certain range.
  Constructor:
  • uniform_int<Type>(Type min = 0, Type max = 9)
    
  Additional member:
  • Type operator()(RandomNumberGenerator), Type upper
    Random numbers are generated in the range ttrange(0)(upper) (half-inclusive).

• uniform_real<Type = real>
Type: the type of the generated random value (by default real).
  Random real values are generated that are uniformly distributed over a certain range.
  Constructor:
  • uniform_real<Type>(Type min = Type(0), Type max = Type(1))
    
  Note: the current implementation generates

          GRN * (max - min) + min
  

  which might not be what you'd expect.

Some of the distributions mentioned below appear not yet to be fully operational in the STL. This appears to be the case with the binomial_distribution, the gamma_distribution, the normal_distribution, and the poisson_distribution. These distributions will likely become fulle operational in the near future.

Here is an example showing the outcome of a statistical experiment consisting of throwing an honest coin 20 times:

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

int main()
{
    std::mt19937 mt(time(0));
    bernoulli_distribution bd;

    for (int idx = 0; idx < 20; ++idx)
        cout << (bd(mt) ? "heads" : "tail") << (idx + 1 == 10 ? '\n' : ' ');
    cout << endl;
}

• Table of Contents
• Previous Chapter
• Next Chapter