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.9.1) 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.
<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.
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:
plus<>
: calls the binary operator+
;
minus<>
: calls the binary operator-
;
multiplies<>
: calls the binary operator*
;
divides<>
: calls operator/
;
modulus<>
: calls operator%
;
negate<>
: calls the unary operator-
. This arithmetic
function object is a unary function object as it expects one argument.
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,
==, !=,
>, >=, <
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:
equal_to<>
: calls operator==
;
not_equal_to<>
: calls operator!=
;
greater<>
: calls operator>
;
greater_equal<>
: calls operator>=
;
less<>
: this object's operator()
member calls
operator<
;
less_equal<>
: calls operator<=
.
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.
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:
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 */
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:
operator()
. In this case the binder function object is a
unary function object.
operator()
receives each of the strings referred to
by the iterator range in turn.
operator()
defined by the function
object that is passed as the binder's first argument.
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));
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:
count_if(stringVector.begin(), stringVector.end(), bind2nd(less_equal<string>(), referenceText))
not2
in combination with the greater<>
predicate:
count_if(stringVector.begin(), stringVector.end(), bind2nd(not2(greater<string>()), referenceText))Here
not2
is used as it negates the truth value of a binary
operator()
, in this case the greater<string>::operator()
member
function.
not1
in combination with the bind2nd
predicate:
count_if(stringVector.begin(), stringVector.end(), not1(bind2nd(greater<string>(), referenceText)))Here
not1
is used as it negates the truth value of a unary
operator()
, in this case the bind2nd
function adaptor.
#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
:
operator()
is called;
<=
is 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
:
operator()
is called;
operator()
is called;
>
is 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
:
operator()
is called;
operator()
is called;
>
is 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.
<iterator>
header file
must have been included.
Iterators are objects acting like pointers. Iterators have the following general characteristics:
==
and
!=
operators. The ordering operators (e.g., >
, <
)
can usually not be used.
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 support reversed_iterator types,
in which the ++iter
operation actually reaches a previous element in a
sequence.
vector
and
deque
. For such containers iter + 2
points to the second element
beyond the one to which iter
points.
#include <vector> #include <iostream> using namespace std; int main() { vector<int>::iterator vi; cout << &*vi; // prints 0 }
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_iterator
s 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:
operator==
, testing two iterators for equality,
operator!=
, testing two iterators for inequality,
operator++
, incrementing the iterator, as prefix operator,
operator*
, to access the element the iterator refers to,
InputIterators are used to read from a container. The dereference operator is guaranteed to work asrvalue
in expressions. Instead of an InputIterator it is also possible to use (see below) Forward-, Bidirectional- or RandomAccessIterators. Notations likeInputIterator1
andInputIterator2
may be used as well. In these cases, numbers are used to indicate which iterators `belong together'. E.g., the generic algorithminner_product
has the following prototype:Type inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Type init);InputIterator1 first1
andInputIterator1 last1
define a pair of input iterators on one range, whileInputIterator2 first2
defines the beginning of another range. Analogous notations may be used with other iterator types.
OutputIterators can be used to write to a container. The dereference operator is guaranteed to work as anlvalue
in expressions, but not necessarily asrvalue
. Instead of an OutputIterator it is also possible to use (see below) Forward-, Bidirectional- or RandomAccessIterators.
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 (see below) Bidirectional- or RandomAccessIterators.
BidirectionalIterators can be used to traverse containers in both directions, for reading and writing. Instead of a BidirectionalIterator it is also possible to use (see below) a RandomAccessIterator.
RandomAccessIterators provide random access to container
elements. An algorithm like sort
requires a
RandomAccessIterator, and can therefore not be used to sort the elements
of lists or maps, which only provide BidirectionalIterators.
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:
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
, using the
copy
generic algorithm:
copy(source.rbegin(), source.rend(), back_inserter(destination));
front_inserter
calls the container's push_front
member, adding
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 adding 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 up existing elements to beyond the newly inserted
elements:
copy(source.begin(), source.end(), inserter(destination, destination.begin()));
typedef
s:
typedef Data value_type
, where Data
is the data type stored in
the class offering push_back, push_front
or insert
members (Example:
typedef std::string value_type
);
typedef value_type const &const_reference
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)); }
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'; }
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:
istreambuf_iterator<Type>
:The end iterator of an iterator range is created using the defaultistreambuf_iterator
constructor. It represents the end-of-stream condition when extracting values of typeType
from thestreambuf
.
istreambuf_iterator<Type>(streambuf *)
:A pointer to astreambuf
may be used when defining anistreambuf_iterator
. It represents the begin iterator of an iterator range.
istreambuf_iterator<Type>(istream)
:An istream may be also used when defining anistreambuf_iterator
. It accesses theistream
'sstreambuf
and it also represents the begin iterator of an iterator range.
istreambuf_iterators
and ostreambuf_iterators
.
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)); }
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:
ostreambuf_iterator<Type>(streambuf *)
:A pointer to astreambuf
may be used when defining anostreambuf_iterator
. It can be used as an OutputIterator.
ostreambuf_iterator<Type>(ostream)
:An ostream may be also used when defining anostreambuf_iterator
. It accesses theostream
'sstreambuf
and it can also be used as an OutputIterator.
istreambuf_iterators
and ostreambuf_iterators
when copying a stream in yet another way. Since the stream's streambuf
s
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; }
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. 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:
unique_ptr
to another move semantics is
used. If move semantics is not available compilation fails. On the other
hand, if compilation succeeds then the used containers or generic algorithms
support the use of unique_ptr
s. Here is an example:
std::unique_ptr<int> up1(new int); std::unique_ptr<int> up2(up1); // compilation errorThe second definition fails to compile as
unique_ptr
's copy
constructor is private (the same holds true for the assignment operator). But
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); };In the next example move semantics is used and so it compiles correctly:
unique_ptr<int> cp(unique_ptr<int>(new int));
unique_ptr
object should only point to memory that was made
available dynamically, as only dynamically allocated memory can be deleted.
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 a 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.
Derived
is derived from Base
, then a newly
allocated Derived
class object can be assigned to a unique_ptr<Base>
,
without having to define a virtual destructor for Base
. The Base *
pointer that is returned by the unique_ptr
object can simply be cast
statically to Derived
, as shown in the following example:
class Base { ... }; class Derived: public Base { // assume Derived has a member void process() }; int main() { shared_ptr<Base> bp(new Derived); static_cast<Derived *>(bp)->process(); // OK! } // here ~Derived is called: no polymorphism required.
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
.
unique_ptr
objects. Each definition contains the usual <type>
specifier between
angle brackets:
unique_ptr
object that
does not point to a particular block of memory. Its pointer is initialized to
0 (zero):
unique_ptr<type> identifier;This form is discussed in section 18.3.2.
unique_ptr
object.
Following the use of the move constructor its unique_ptr
argument no
longer points to the dynamically allocated memory and its pointer data member
is turned into a zero-pointer:
unique_ptr<type> identifier(another unique_ptr for type);This form is discussed in section 18.3.3.
unique_ptr
object
to the block of dynamically allocated memory that is passed to the object's
constructor. Optionally deleter
can be provided. A (free) function (or
function object) receiving the unique_ptr
's pointer as its argument can be
passed as deleter. It is supposed to return the dynamically allocated
memory to the common pool (doing nothing if the pointer equals zero).
unique_ptr<type> identifier (new-expression [, deleter]);This form is discussed in section 18.3.4.
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).
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> &¶m) { 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 worldThe example illustrates that
hello1
is initialized by a pointer to a dynamically alloctated
string
(see the next section).
unique_ptr hello2
grabs the pointer controlled by hello1
using a move constructor. This effectively changes hello1
into a
0-pointer.
hello3
is defined as a default unique_ptr<string>
. But
then it grabs its value using move-assignment from hello2
(which, as a
consequence, is changed into a 0-pointer as well)
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
.
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 */
unique_ptr
offers the following
operators:
unique_ptr<Type> &operator=(unique_ptr<Type> &&tmp)
:This operator transfers the memory pointed to by the rvalueunique_ptr
object to the lvalueunique_ptr
object using move semantics. So, the rvalue object loses the memory it pointed at and turns into a 0-pointer. An existingunique_ptr
may be assigned to anotherunique_ptr
by converting it to an rvalue reference first usingstd::move
. Example:unique_ptr<int> ip1(new int); unique_ptr<int> ip2; ip2 = std::move(ip1);
operator bool() const
:This operator returnsfalse
if theunique_ptr
does not point to memory (i.e., itsget
member, see below, returns 0). Otherwise,true
is returned.
Type &operator*()
:This operator returns a reference to the information accessible via
a unique_ptr
object . It acts like a normal pointer dereference
operator.
Type *operator->()
:This operator returns a pointer to the information accessible via aunique_ptr
object. This operator allows you to select members of an object accessible via aunique_ptr
object. Example:unique_ptr<string> sp(new string("hello")); cout << sp->c_str();
The class unique_ptr
supports the following
member functions:
Type *get()
:A pointer to the information controlled by theunique_ptr
object is returned. It acts likeoperator->
. The returned pointer can be inspected. If it is zero theunique_ptr
object does not point to any memory.
Deleter &unique_ptr<Type>::get_deleter()
:A reference to the deleter object used by the unique_ptr
is
returned.
Type *release()
:A pointer to the information accessible via aunique_ptr
object is returned. At the same time the object itself becomes a 0-pointer (i.e., its pointer data member is turned into a 0-pointer). This member can be used to transfer the information accessible via aunique_ptr
object to a plainType
pointer. After calling this member the proper destruction of the dynamically allocated memory is the responsibility of the programmer.
void reset(Type *)
:The dynamically allocated memory controlled by theunique_ptr
object is returned to the common pool; the object thereupon controls the memory to which the argument that is passed to the function points. It can also be called without argument, turning the object into a 0-pointer. This member function can be used to assign a new block of dynamically allocated memory to aunique_ptr
object.
void swap(unique_ptr<Type> &)
:Two identically typed unique_ptrs
are swapped.
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:
[]
) notation is used to specify that the smart
pointer controls a dynamically allocated array. Example:
unique_ptr<int[]> intArr(new int[3]);
intArr[2] = intArr[0];
delete[]
rather than delete
.
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.
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. As with unique_ptr
, when defining a
shared_ptr<Base>
to store a newly allocated Derived
class object, the
returned Base *
may be cast to a Derived *
using a static_cast
:
polymorphism isn't required, and when resetting the shared_ptr
or when the
shared_ptr
goes out of scope, no slicing occurs, and Derived
's
destructor is called (cf. section 18.3).
Shared_ptr
s 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.
shared_ptr
objects. Each definition contains the usual <type>
specifier between
angle brackets:
shared_ptr
object that
does not point to a particular block of memory. Its pointer is initialized to
0 (zero):
shared_ptr<type> identifier;This form is discussed in section 18.4.2.
shared_ptr
so that both
objects share the memory pointed at by the existing object. The copy
constructor also increments the shared_ptr
's reference count. Example:
shared_ptr<string> org(new string("hi there")); shared_ptr<string> copy(org); // reference count now 2
shared_ptr
with the pointer
and reference count of a temporary shared_ptr
. The temporary
shared_ptr
is changed into a 0-pointer. An existing shared_ptr
may
have its data moved to a newly defined shared_ptr
(turning the existing
shared_ptr
into a 0-pointer as well). In the next example a temporary,
anonymous shared_ptr
object is constructed, which is then used to
construct grabber
. Since grabber
's constructor receives an anonymous
temporary object, the compiler uses shared_ptr
's move constructor:
shared_ptr<string> grabber(shared_ptr<string>(new string("hi there")));
shared_ptr
object
to the block of dynamically allocated memory that is passed to the object's
constructor. Optionally deleter
can be provided. A (free) function (or
function object) receiving the shared_ptr
's pointer as its argument can be
passed as deleter. It is supposed to return the dynamically allocated
memory to the common pool (doing nothing if the pointer equals zero).
shared_ptr<type> identifier (new-expression [, deleter]);This form is discussed in section 18.4.3.
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).
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 */
shared_ptr
offers the following
operators:
shared_ptr &operator=(shared_ptr<Type> const &other)
:Copy assignment: the reference count of the operator's left hand side operand is reduced. If the reference count decays to zero the dynamically allocated memory controlled by the left hand side operand is deleted. Then it shares the information with the operator's right hand side operand, incrementing the information's reference count.
shared_ptr &operator=(shared_ptr<Type> &&tmp)
:Move assignment: the reference count of the operator's left hand side operand is reduced. If the reference count decays to zero the dynamically allocated memory controlled by the left hand side operand is deleted. Then it grabs the information controlled by the operator's right hand side operand which is turned into a 0-pointer.
operator bool() const
:If theshared_ptr
actually points to memorytrue
is returned, otherwise,false
is returned.
Type &operator*()
:A reference to the information stored in the
shared_ptr
object is returned. It acts like a normal pointer.
Type *operator->()
:A pointer to the information controlled by theshared_ptr
object is returned. Example:shared_ptr<string> sp(new string("hello")); cout << sp->c_str() << '\n';
The following member function member functions are supported:
Type *get()
:A pointer to the information controlled by theshared_ptr
object is returned. It acts likeoperator->
. The returned pointer can be inspected. If it is zero theshared_ptr
object does not point to any memory.
Deleter &get_deleter()
:A reference to the shared_ptr
's deleter (function or function
object) is returned.
void reset(Type *)
:The reference count of the information controlled by theshared_ptr
object is reduced and if it decays to zero the memory it points to is deleted. Thereafter the object's information will refer to the argument that is passed to the function, setting its shared count to 1. It can also be called without argument, turning the object into a 0-pointer. This member function can be used to assign a new block of dynamically allocated memory to ashared_ptr
object.
void shared_ptr<Type>::swap(shared_ptr<Type> &&)
:Two identically typed shared_ptrs
are swapped.
bool unique() const
:If the current object is the only object referring to the memory controlled by the objecttrue
is returned otherwise (including the situation where the object is a 0-pointer)false
is returned.
size_t use_count() const
:The number of objects sharing the memory controlled by the object is returned.
shared_ptr
objects. Consider the following two classes:
struct Base {}; struct Derived: public Base {};
As with unique_ptr
, when defining a shared_ptr<Base>
to store a
newly allocated Derived
class object, the returned Base *
may be cast
to a Derived *
using a static_cast
: polymorphism isn't required, and
when resetting the shared_ptr
or when the shared_ptr
goes out of
scope, no slicing occurs, and Derived
's destructor is called (cf. section
18.3).
Of course, a shared_ptr<Derived>
can easily be defined. Since a
Derived
object is also a Base
object, a pointer to Derived
can
be considered a pointer to Base
without using casts, but a static_cast
could be used for force the interpretation of a Derived *
to a Base *
:
Derived d; static_cast<Base *>(&d);
However, a plain static_cast
cannot be used when initializing a shared
pointer to a Base
using the get
member of a shared pointer to a
Derived
object. The following code snipped eventually results in an
attempt to delete the dynamically allocated Base
object twice:
shared_ptr<Derived> sd(new Derived); shared_ptr<Base> sb(static_cast<Base *>(sd.get()));Since
sd
and sb
point at the same object ~Base
will be called
for the same object when sb
goes out of scope and when sd
goes out of
scope, resulting in premature termination of the program due to a
double free error.
These errors can be prevented using casts that were specifically designed
for being used with shared_ptrs
. These casts use specialized constructors
that create a shared_ptr
pointing to memory but shares ownership (i.e.,
a reference count) with an existing shared_ptr
. These special casts are:
std::static_pointer_cast<Base>(std::shared_ptr<Derived> ptr)
:Ashared_ptr
to aBase
class object is returned. The returnedshared_ptr
refers to the base class portion of theDerived
class to which theshared_ptr<Derived> ptr
refers. Example:shared_ptr<Derived> dp(new Derived()); shared_ptr<Base> bp = static_pointer_cast<Base>(dp);
std::const_pointer_cast<Class>(std::shared_ptr<Class const> ptr)
:Ashared_ptr
to aClass
class object is returned. The returnedshared_ptr
refers to a non-constClass
object whereas theptr
argument refers to aClass const
object. Example:shared_ptr<Derived const> cp(new Derived()); shared_ptr<Derived> ncp = const_pointer_cast<Derived>(cp);
std::dynamic_pointer_cast<Derived>(std::shared_ptr<Base> ptr)
:Ashared_ptr
to aDerived
class object is returned. TheBase
class must have at least one virtual member function, and the classDerived
, inheriting fromBase
may have overriddenBase
's virtual member(s). The returnedshared_ptr
refers to aDerived
class object if the dynamic cast fromBase *
toDerived *
succeeded. If the dynamic cast did not succeed theshared_ptr
'sget
member returns 0. Example (assumeDerived
andDerived2
were derived fromBase
):shared_ptr<Base> bp(new Derived()); cout << dynamic_pointer_cast<Derived>(bp).get() << ' ' << dynamic_pointer_cast<Derived2>(bp).get() << '\n';The firstget
returns a non-0 pointer value, the secondget
returns 0.
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]; }
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';
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.
The STL offers dedicated classes which work well in combination with threads, the topic of the next section, but which can also used in many other situations.
--------------------
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 using either duration
or time_point
the
<chrono>
header file must have been included, where the latter header file
includes the former.
and a specific point in time is defined using the class template
time_point
.
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
).
std::ratio
.
Before the class ratio
can be used, the <ratio>
header file must have
been included. However, the ratio
header file is automatically included
when including the <chrono>
header file.
The class template ratio
expects two integral (for all practical purposes:
positive) template arguments, defining, respectively, the numerator and
denominator of a time unit. By default, the denomincator equals
1, resulting in the ratio's
first argument (the numerator) being
interpreted as the ratio's
number of seconds.
E.g., ratio<1>
defines a time unit of one second; ratio<60>
defines a
time unit of 60 seconds, so it defines a unit of a minute; and ratio<1,
1000>
defines a unit of 1/1000 second, so it defines a unit of one milli
second.
A ratio's
numerator is directly accessible as its num
field. A ratio's
denominator is directly accessible as its
den
field.
A rather large number of predefined ratio
types exist. They can be used
instead of the more cumbersome ratio<x>
or ratio<x, y>
specification:
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.)
duration
is defined in the std::chrono
namespace.
Objects of the class duration
define a certain amount of time.
Before using the class std::chrono::duration
the <chrono>
header file
must have been included. When including chrono
the header file <ratio>
is also included.
The class template duration
requires two template type arguments: a
numeric type (commonly int64_t
) to contain the duration's value, and a
time-unit, called its Period, usually specified using the class template
ratio
.
Using predefined ratio
types amounts of time of various granularities can
be defined. E.g., to define a time interval of 30 minutes you could use
std::chrono::duration<int64_t, std::deca> halfHour(30)but even if you're
using namespace std
and using namespace chrono
this is a rather complex and non-intuitive definition. Fortunately, various
duration types have been predefined:
Using these types, a duration of 30 minutes can now simply
be defined as std::chrono::minutes halfHour(30)
.
Duration types themselves define the following types:
std::chrono::duration<Value, Period>::rep
:theValue
type used by theduration
type (e.g.,int64_t
)
std::chrono::duration<Value, Period>::period
:thePeriod
type used by theduration
type (e.g.,std::ratio::nano
)
In addition to the copy constructor (and overloaded assignment operator) the
class template duration
offers the following constructors:
constexpr duration()
:
the default duration defines a duration of zero time units.
constexpr explicit duration(Value const &value)
:
a specific duration of value
time units. Here Value
refers to
the duration's numeric type (e.g., int64_t
). So, when defining
std::chrono::minutes halfHour(30);the argument 30 is stored inside a
int64_t
.
The class template duration
offers the following members:
Duration objects may be added, subtracted, multiplied, divided and they support the modulo operator (the binary arithmetic and the binary arithmetic assignment operators are available).
constexpr Value count() const
:returns the value that is stored inside aduration
object. ForhalfHour
this would return 30, not 1800, as the time unit itself is obtained as theduration<Value, Unit>::period
type.
static constexpr duration zero()
:this is a static member, returning a duration object representing a duration of zero time units.
static constexpr duration min()
:this is a static member, returning a duration object
representing numeric_limits<Rep>::lowest()
.
static constexpr duration max()
:this is a static member, returning a duration object
representing numeric_limits<Rep>::max()
.
Different duration
types may be combined, unless time precision would be
lost. When the binary arithmetic operators are used the resulting duration
uses the finer of the two granularities. When the binary arithmetic assignment
operator is used the granulatity of the left-hand side operand must at least
be equal to the granularity of the right-hand side operand, or a compilation
error is issued. E.g.,
std::chrono::minutes halfHour(30); std::chrono::seconds half_a_minute(30); cout << (halfHour + half_a_minute).count(); // displays 1830 //halfHour += half_a_minute; won't compile: precision is lost half_a_minute += halfHour; cout << half_a_minute.count(); // displays 1830
std::chrono
namespace.
Before using the predefined clocks the <chrono>
header file must have been
included. When including chrono
the header file <ratio>
is also
included.
A clock type must be specified when defining points in time using
time_point
(covered by the next section). 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. Defining your own clock type is not
covered by the C++ Annotations.
All predefined clocks provide type definitions and a member now
. If
ClockType
is a predefined clock type, then
std::chrono::ClockType::duration
:theduration
type (e.g.,std::chrono::nanoseconds
used byClockType
)
std::chrono::ClockType::period
:the time period used byClockType
(e.g.,std::ratio::nano
)
std::chrono::ClockType::rep
:defining the value type used byClockType
to store duration values (e.g.,int64_t
)
std::chrono::ClockType::time_point
:time points used byClockType
(e.g.,std::chrono::time_point<system_clock, duration>
)
In addition to these types predefined clocks offer a member
static std::chrono::time_point
std::chrono::ClockType::now()
:returns the time_point
representing the current time
The following predefined clock types are available:
std::chrono::system_clock
:the `wall clock' time, using the system's real time clock. In addition tonow
the classsystem_clock
offers these two static members:
static time_t std::chrono::system_clock::to_time_t
(std::chrono::time_point const & timePoint)
atime_t
value representing the same point in time astimePoint
;static std::chrono::time_point std::chrono::system_clock::from_time_t
(time_t seconds)
atime_point
value representing the same point in time astime_t
.
std::chrono::steady_clock
:a clock whose time increases in parallel with the increase of real time.
std::chrono::high_resolution_clock
:the computer's fastest clock (i.e., the clock having the shortest
timer-tick period). In practice this is the clock used to implement
the system_clock
.
As an example: to access the current time you could use:
auto point = std::chrono::system_clock::now();
time_point
is defined in the std::chrono
namespace.std::chrono::time_point
define a moment in time.
Before using the class std::chrono::time_point
the <chrono>
header
file must have been included. When including chrono
the header file
<ratio>
is also included.
The class time_point
is a class template,
requires two template type arguments: a Clock
type and a Duration
type.
The Clock
type usually is one of the predefined clock types, e.g.,
chrono::system_clock
. The Duration
type may be omitted, in which case
the Clock's duration
type is used. An explicit duration
type may also
be provided.
In the previous section auto
was used to specify the type of the return
value of system_clock::now
. The explicit definition looks like this:
std::chrono::time_point<std::chrono::system_clock> now = std::chrono::system_clock::now();
The class std::chrono::time_point
offers three constructors:
time_point()
:the default constructor represents the beginning of the clock's epoch (E.g., Jan, 1, 1970, 00:00h);
time_point(time_point<Clock, Duration> const &timeStep)
:initializes atime_point
object representing a point in timetimeStep Duration
units byond the clock's epoch;
time_point(time_point<Clock, Duration2> const &timeStep)
:this constructor is defined as a member template, using the template headertemplate <typename Duration2>
. The typeDuration2
is astd::chrono::duration
(or comparable) type, using a possibly larger period for its unit thantime_point's Duration
type. It initializes atime_point
object representing a point in timetimeStep Duration2
units byond the clock's epoch.
The class std::chrono::time_point
offers these operators and members:
std::chrono::time_point &operator+=(Duration const &duration)
:this operator is also available as binary arithmetic operator, expecting astd::chrono::time_point const &
and aDuration const &
argument (in any order). The amount of time represented byduration
is added to the currenttime_point
value. Example:std::chrono::system_clock::now() + seconds(5);
std::chrono::time_point &operator-=(Duration const &duration)
:this operator is also available as binary arithmetic operator, expecting astd::chrono::time_point const &
and aDuration const &
argument (in any order). The amount of time represented byduration
is subtracted from the currenttime_point
value. Example:auto point = std::chrono::system_clock::now(); point -= seconds(5);
constexpr Duration time_since_epoch() const
:returns the object's Duration
since the epoch.
static constexpr time_point min()
:a static member returning the value returned by the time point's
duration::min
value.
static constexpr time_point max()
:a static member returning the value returned by the time point's
duration::max
value.
All predefined clocks use nanoseconds as their time unit. To obtain the
time expressed in a larger time unit, divide the value returned by the
time_point's count
value by larger time unit
converted to nanoseconds. E.g., the number of hours passed since the beginning
of the epoch is:
using namespace std; using namespace chrono; // for brevity cout << system_clock::now().time_since_epoch().count() / nanoseconds(hours(1)).count() << " hours since the epoch\n";
To convert the time to a textual representation standard C functions can
be used. These functions usually expect arguments in seconds, as returned by
the time(2), function. Given that a time_point
is available, the
system clock's static member to_time_t
can be used to convert a
time_point
value to a time_t
value, after which the time in seconds
can, e.g., be converted to a textual representation. E.g.,
using namespace std; using namespace chrono; // for brevity time_t tm = system_clock::to_time_t(system_clock::now() + hours(1)); cout << asctime(localtime(&tm));
Here are some more examples showing how time_point
objects can be used:
#include <iostream> #include <chrono> using namespace std; using namespace chrono; int main() { // the current time (or use `auto') 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'; }
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++11 -pthread -Wall multi.cc
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:
thread::id get_id() noexcept
:returns an object of typethread::id
that uniquely identifies the currently active thread of execution. For an active thread the returnedid
s is unique in that it 1:1 maps to the currently active thread, and is not returned for any other thread. A defaultid
is returned whenget_id
is called for a thread that is currently not running.
void yield() noexcept
:the implementation may callyield
to reschedule. Cf.thread::yield
in section 18.8.2.
void sleep_for(chrono::duration<Rep, Period> const &relTime)
noexcept
:this function is defined as a function template, defining the template headertemplate <typename Rep, typename Period>
. The template's types are derived from the actualrelTime
argument that is passed to the function, and should not explicitly be specified. This function could be called as, e.g.,sleep_for(seconds(5));Calling this function blocks the thread calling this function during the specified time interval, starting at the point in time the function is called.
void sleep_until(chrono::time_point<Clock, Duration> const &absTime)
noexcept
:this function is also defined as a function template, defining the template headertemplate <typename Clock, typename Duration>
. TheClock
andDuration
types are derived from the actualabsTime
argument that is passed to the function, and should not explicitly be specified. This function could be called as, e.g.,sleep_until(system_clock::now() + seconds(5));Calling this function blocks the thread until the specified absolute point in time.
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:
thread() noexcept
:the default constructor creates a thread
object that is not (yet)
associated with a running thread of execution;
explicit thread(Fun &&fun, Args &&...args)
:this constructor is defined as a member template (cf. section 21.1.3), using the template headertemplate <typename Fun, typename ...Args>
. Its first argument is a function that implements the thread's actions. The notationArgs &&...args
indicates that any number of additional arguments may followfun
. These arguments are then passed with their proper types and values tofun
. The argument passed tofun
may also be a function object, whose function call operator then receives the...args
arguments.Function (or function object) and arguments must be move constructible (i.e., after assignment or initialization the target object is equivalent to the original source, while following the assignment or construction the source's state is not specified). After (move-)constructing copies of
fun
and...args
thethread
object has been constructed. Following thethread
object construction (but not as part of the construction), a separately running thread of execution, associated with the just constructedthread
object, is started.If the requested thread cannot be created a
system_error
is thrown.
thread(thread &&tmp) noexcept
:the move constructor usestmp
to construct the targetthread
object and putstmp
in thethread
's default state.
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:
void detach()
:requiresjoinable
to returntrue
. The thread for whichdetach
is called continues its execution. The (e.g., parent) thread callingdetach
continues its execution immediately beyond thedetach
-call. After callingobject.detach()
, `object
' no longer represents the, possibly still continuing but now detached, thread of execution. It is the detached thread's implementation's responsibility to release its resources when its execution ends.Since
detach
disconnects a thread from the running program, e.g.,main
no longer can wait for the thread's completion. As a program ends whenmain
ends, its still running threads also stop, and program may not properly complete all its threads, as demonstrated by the following program:#include <thread> #include <iostream> #include <unistd.h> using namespace std; // do not forget to use -lpthread with g++ void fun(size_t count, char const *txt) { for (; count--; ) cout << count << ": " << txt << endl; } int main() { // runs the threads following // the object construction thread display(fun, 3, "hello world"); display.detach(); thread second(fun, 3, "a second thread"); second.detach(); cout << "leaving" << endl; }When this program is run, only part of the potentially generated output is inserted intocout
, like:leaving22: hello world
id get_id() const noexcept
:If the current object does not represent a a running thread a defaultid
object is returned. Otherwise,this_thread::get_id()
is returned for the running thread that is associated with the object for whichget_id
is called is returned.
void join()
:requiresjoinable
to returntrue
. Blocks the thread callingjoin
until the thread for whichjoin
is called has completed. Following its completion the object whosejoin
member was called no longer represents a running thread, and itsget_id
member will return the defaultid
.
An example of its use is provided by the above example. In that examplejoin
is called to preventdisplay
from being destroyed at the end ofmain
. Without callingjoin
display
's thread would still have been running by the timemain
's execution would have reached its end. At that pointdisplay
's destructor would have been called. However, when the destructor of a joinable thread is called,terminate
is called, forcing the program's abort.
bool joinable() const noexcept
:returnsobject.get_id() != id()
, whereobject
is thethread
object for whichjoinable
was called.
void swap(thread &other) noexcept
:The states of thethread
object for whichswap
was called andother
are swapped. Note that threads may be swapped as well, even when their threads of execution are currently active.
The class thread
supports the move assignment operator:
thread &operator=(thread &&tmp) noexcept
:
If the operator's left-hand side operand (lhs) is a joinable thread,
then terminate
is called. Otherwise, other
's state is assigned to the
operator's lhs and sets other
to the thread's default constructed state.
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.
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:
constexpr
constructor;
void lock()
:the calling thread is blocked until it has obtained ownership of the mutex. Unlesslock
is called for a recursive mutex asystem_error
is thrown if, e.g., the thread already owns the lock. Recursive mutexes increment their interal lock count;
bool try_lock() noexcept
:the calling thread tries to obtain ownership of the mutex without blocking. If ownership is obtained,true
is returned, otherwisefalse
. If the lock was already obtained by the calling thread,true
is also returned, and with a recursive mutex its interal lock count is also incremented;
void unlock() noexcept
:the calling thread releases ownership of the mutex. A
system_error
is thrown if, e.g., the thread does not own the
lock. Recursive mutexes decrement their interal lock count, releasing
ownership of the mutex once the lock count has decayed to zero;
In addition to the abovementioned members, timed mutex classes
(timed_mutex,
recursive_timed_mutex
) also offer:
bool try_lock_for(chrono::duration<Rep, Period> const
&relTime) noexcept
:this function is defined as a function template, defining the template headertemplate <typename Rep, typename Period>
. The template's types are derived from the actualrelTime
argument that is passed to the function, and should not explicitly be specified. This function could be called for atimed_mutex_lock tml
as, e.g.,tml.try_lock_for(seconds(5));If the ownership is obtained within the specified time intervaltrue
is returned, otherwisefalse
. If the lock was already obtained by the calling thread,true
is also returned, and with a recursive timed mutex its interal lock count is also incremented;
bool try_lock_until(chrono::time_point<Clock,
Duration> const &absTime) noexcept
:this function is also defined as a function template, defining the template headertemplate <typename Clock, typename Duration>
. TheClock
andDuration
types are derived from the actualabsTime
argument that is passed to the function, and should not explicitly be specified. This function could be called for atimed_mutex_lock tml
as, e.g.,tml.try_lock_until(system_clock::now() + seconds(5));If the ownership is obtained before the specified point in timetrue
is returned, otherwisefalse
. If the lock was already obtained by the calling thread,true
is also returned, and with a recursive timed mutex its interal lock count is also incremented;
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:
struct std::defer_lock_t
:the lock is not trying to acquire ownership of the mutex. The
ownership may be requested later during the lock's lifetime. A
predefined defer_lock
object which may be passed as tag is also
available;
struct std::try_to_lock_t
:the lock is trying to acquire ownership of the mutex, but won't block
if this fails. A predefined try_to_lock
object which may be passed
as tag is also available;
struct std::adopt_lock_t
:the lock won't try to acquire ownership of the lock, but instead
assumes that the calling thread has already obtained ownership. The
lock will be released (or the lock-count will be reduced) when the
lock is destroyed. A predefined adopt_lock
which may be passed as
tag is also available.
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:
unique_lock() noexcept
:the default constructor is not associated with amutex
type. It must be assigned amutex
(e.g., using move-assignment) before it can do anything useful;
explicit unique_lock(Mutex& mutex)
:initializes aunique_lock
with an existingMutex
object, resulting in the lock object obtaining ownership of theMutex
;
unique_lock(Mutex& mutex, defer_lock_t) noexcept
:initializes aunique_lock
with an existingMutex
object, but will not try to obtain ownership of theMutex
;
unique_lock(Mutex& mutex, try_to_lock_t) noexcept
:initializes aunique_lock
with an existingMutex
object, and will try to obtain ownership of theMutex
, but won't block if it does not succeed;
unique_lock(Mutex& mutex, adopt_lock_t) noexcept
:initializes aunique_lock
with an existingMutex
object, assuming that the current thread has already obtained ownership of theMutex
;
unique_lock(Mutex& mutex, chrono::duration<Rep, Period> const
&relTime) noexcept
:this constructor is defined as a member template, using the template headertemplate <typename Rep, typename Period>
. The template's types are derived from the actualrelTime
argument that is passed to the constructor, and should not explicitly be specified. The constructor will try to obtain ownership of theMutex
object by callingmutex.try_lock_for(relTime)
. IfMutex mutex
is available, this constructor could be called like this:unique_lock<Mutex> ulock(mutex, seconds(5));
unique_lock(Mutex& mutex, chrono::time_point<Clock, Duration> const
&absTime) noexcept
:this constructor is also defined as a member template, using the template headertemplate <typename Clock, typename Duration>
. TheClock
andDuration
types are derived from the actualabsTime
argument that is passed to the constructor, and should not explicitly be specified. The constructor will try to obtain ownership of theMutex
object by callingmutex.try_lock_until(absTime)
. IfMutex mutex
is available, this constructor could be called like this:unique_lock<Mutex> ulock(mutex, system_clock::now() + seconds(5));
Overloaded operators:
explicit operator bool() const noexcept
:returnstrue
if theunique_lock
owns the mutex, otherwisefalse
;
unique_lock& operator=(unique_lock &&tmp) noexcept
:with the move-assignment operator, if the left-hand operand owns a lock, it will call its mutex'sunlock
member, whereaftertmp
's state is transferred to the left-hand operand
Ordinary members:
void lock()
:blocks the current thread until ownership of the mutex that is managed by theunique_lock
is obtained. If no mutex is currently managed, then asystem_error
exception is thrown.
bool owns_lock() const noexcept
:returnstrue
if theunique_lock
owns the mutex, otherwisefalse
;
Mutex *release() noexcept
:returns a pointer to the mutex object previously stored inside theunique_lock
object, setting its ownMutex *
data member to 0;
void swap(unique_lock& other) noexcept
:swaps the states of the currentunique_lock
andother
;
bool try_lock()
:tries to obtain ownership of the mutex that is managed by theunique_lock
, returningtrue
if this succeeds, andfalse
otherwise. If no mutex is currently managed, then asystem_error
exception is thrown.
bool try_lock_for(chrono::duration<Rep, Period> const
&relTime)
:this member is defined as a member template, using the template headertemplate <typename Rep, typename Period>
. The template's types are derived from the actualrelTime
argument that is passed to this member, and should not explicitly be specified. This member function will try to obtain ownership of theMutex
object managed by theunique_lock
object by calling the mutex'stry_lock_for(relTime)
member.
bool try_lock_until(chrono::time_point<Clock,
Duration> const &absTime)
:this member is also defined as a member template, using the template headertemplate <typename Clock, typename Duration>
. TheClock
andDuration
types are derived from the actualabsTime
argument that is passed to th is member function, and should not explicitly be specified. This member function will try to obtain ownership of theMutex
object managed by theunique_lock
object by calling the mutex'smutex.try_lock_until(absTime)
member.
void unlock()
:releases ownership of the mutex (or reduces the mutex's lock count). Asystem_error
exception is thrown if theunique_lock
does not own the mutex.
Mutex *mutex() const noexcept
:returns a pointer to the mutex object stored inside theunique_lock
(anullptr
is returned if no mutex object is currently stored inside theunique_lock
object.)
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.
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:
constexpr
keyword (cf. section 8.1.4.1), satisfying the requirements for constant
initialization. In this case, an object of static storage lifetime,
initialized using that constructor, is guaranteed to be initialized before any
code is run as part of the static initialization phase. This is the option
chosen for std::mutex
, because it eliminates the possibility of race
conditions with initialization of mutexes at a global scope. Here is an
example, using in-class implementations for brevity:
class MyClass { int d_i; public: constexpr MyClass(int i = 0) : d_i(0) {} void action(); }; MyClass myObject; // static initialization with constexpr constructor int foo(); myClass other(42 + foo()); // dynamic initialization void f() { other.action(); // is other initialized in some thread? }
#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; } /* Displays: 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).
std::call_once
and std::once_flag
result
in 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); }
Before condition variables can be used the <condition_variable>
header
file must have been included.
To start our discussion, consider a classic producer-consumer scenario: the producer generates items which are 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's storage capacity has filled to the brim, and the producer has to wait until the client has at least consumed some items, thereby creating space in the producer's storage. Similarly, the consumer cannot start consuming until the producer has at least produced some items.
Implementing this scenario only using mutexes (data locking) is not an attractive option, as merely using mutexes forces a program to implement the scenario using polling: processes must continuously (re)acquire the mutex's lock, determine whether they can perform some action, followed by the release of the lock. Often there's no action to perform, and the process is busy acquiring and releasing the mutex's lock. Polling forces threads to wait until they can lock 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 (a situation also known as `busy waiting').
Contrary to merely using mutexes, polling can be prevented using condition variables. Using condition variables threads may notify waiting threads that there is something for them to do. Thus threads synchronized on the states (e.g., values) of data.
As the states of data may be modified by multiple threads, threads still need to use mutexes, but merely to control access to the data. In addition, however, condition variables allow threads to release ownership of mutexes 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 threads using condition variables looks like this:
lock the mutex while the required condition is false: wait until being notified (automatically releasing the mutex's lock). the mutex's lock has been reacquired, and the condition is true: process the data release the mutex's lock.
lock the mutex while the condition is false: process the data notify waiting threads that the condition is true release the mutex's lock.
notify_one, notify_all, wait,
wait_for
, and wait_until
members are executed.
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 allows for certain
optimizations resulting in an increased efficiency compared to the efficiency
that can be obtained with objects of the class
std::condition_variable_any
, which may be
used with any (e.g., user supplied) lock type.
Condition variable classes offer members like wait, wait_for,
wait_until, notify_one
and notify_all
that may concurrently be called.
The notifying members are always atomically executed. Execution of the
wait
members consists of three atomic parts:
wait
call).
wait
-members the previously waiting thread
has reacquired the mutex's lock.
In addition to the condition variable classes the following free function and
enum
type is provided:
void
std::notify_all_at_thread_exit(condition_variable &cond,
unique_lock<mutex> lockObject)
:once the current thread has ended, all other threads waiting oncond
are notified. It is good practice to exit the thread as soon as possible after callingnotify_all_at_thread_exit
.Waiting threads must verify that the thread they were waiting for has indeed ended. This is usually realized by first obtaining the lock on
lockObject
, followed by verifying that the condition they were waiting for is true and that the lock was not reacquired beforenotify_all_at_thread_exit
was called.
std::cv_status
:thecv_status
enum is used by several member functions of the condition variable classes (cf. sections 18.8.5.1 and 18.8.5.2):namespace std { enum class cv_status { no_timeout, timeout }; }
std::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 threads waiting on a condition_variable
must
have been notified before a condition_variable
object's lifetime
ends. Calling notify_all
(see below) before a condition_variable
ceases to exists takes care of that.
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 member referred to below were called using
the same condition variable object.
The class condition_variable
supports several wait
members, which will
block the thread until notified by another thread (or after a configurabel
waiting time). However, these wait
members may also spuriously unblock,
without having reacquired the lock. Therefore, returning from these wait
members threads should verify that the required data condition has actually
been met. If not, again calling wait
may be appropriate, as illustrated by
the next piece of pseudo code:
while (conditionNotYetMet()) condVariable.wait(&uniqueLock);
The class condition_variable
's members are:
void notify_one() noexcept
:one wait
member called by other threads returns. Which one
actually returns cannot be predicted.
void notify_all() noexcept
:all wait
members called by other threads unblock their wait
states. Of course, only one of them will subsequently succeed in
reacquiring the condition variable's lock object.
void wait(unique_lock<mutex>& uniqueLock)
:before callingwait
the current thread must have acquired the lock ofuniqueLock
. Callingwait
releases the lock, and the current thread is blocked until it has received a notification from another thread, and has reacquired the lock.Threads should verify that the required data condition has been met after
wait
has returned.
void wait(unique_lock<mutex>& uniqueLock, Predicate pred)
:this is a member template, using the template headertemplate <typename Predicate>
. The template's type is automatically derived from the function's argument type and does not have to be specified explicitly.Before calling
wait
the current thread must have acquired the lock ofuniqueLock
. As long as `pred
' returnsfalse
wait(lock)
is called.Threads should verify that the required data condition has been met after
wait
has returned.
cv_status wait_for(unique_lock<mutex> &uniqueLock,
std::chrono::duration<Rep, Period> const &relTime)
:this member is defined as a member template, using the template headertemplate <typename Rep, typename Period>
. The template's types are automatically derived from the typs of the function's arguments and do not have to be specified explicitly. E.g., to wait for at most 5 secondswait_for
can be called like this:cond.wait_for(&unique_lock, std::chrono::seconds(5));This member returns when being notified or when the time interval specified byrelTime
has passed.When returning due to a timeout,
std::chrono::cv_status::timeout
is returned, otherwisestd::chrono::cv_status::no_timeout
is returned.Threads should verify that the required data condition has been met after
wait_for
has returned.
bool wait_for(unique_lock<mutex> &uniqueLock,
chrono::duration<Rep, Period> const &relTime, Predicate
pred)
:this member is defined as a member template, using the template headertemplate <typename Rep, typename Period, typename Predicate>
. The template's types are automatically derived from the typs of the function's arguments and do not have to be specified explicitly.As long as
pred
returns false, the previouswait_for
member is called. If the previous member returnscv_status::timeout
, thenpred
is returned, otherwisetrue
.Threads should verify that the required data condition has been met after
wait_for
has returned.
cv_status wait_until(unique_lock<mutex>& uniqueLock,
chrono::time_point<Clock, Duration> const &absTime)
:this member is defined as a member template, using the template headertemplate <typename Clock, typename Duration>
. The template's types are automatically derived from the typs of the function's arguments and do not have to be specified explicitly. E.g., to wait until 5 minutes after the current timewait_until
can be called like this:cond.wait_until(&unique_lock, chrono::system_clock::now() + std::chrono::minutes(5));This function acts identically to thewait_for(unique_lock<mutex> &uniqueLock, chrono::duration<Rep, Period> const &relTime)
member described earlier, but uses an absolute point in time, rather than a relative time specification.This member returns when being notified or when the time interval specified by
relTime
has passed. When returning due to a timeout,std::chrono::cv_status::timeout
is returned, otherwisestd::chrono::cv_status::no_timeout
is returned.Threads should verify that the required data condition has been met after
wait_until
has returned.
bool wait_until(unique_lock<mutex> &lock,
chrono::time_point<Clock, Duration> const &absTime,
Predicate pred)
:this member is defined as a member template, using the template headertemplate <typename Clock, typename Duration, typename Predicate>
. The template's types are automatically derived from the types of the function's arguments and do not have to be specified explicitly.As long as
pred
returns false, the previouswait_until
member is called. If the previous member returnscv_status::timeout
, thenpred
is returned, otherwisetrue
.Threads should verify that the required data condition has been met after
wait_until
has returned.
condition_variable
the class
std::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
therefore requires the
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
only
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.
Assuming that MyMutex
is a user defined mutex type, and that MyLock
is
a user defined lock-type (cf. section 18.8.4 for details about
lock-types), then a condition_variable_any
object can be defined and used
like this:
MyMutex mut; MyLock<MyMutex> ul(mut); condition_variable_any cva; cva.wait(ul);
Here are the class condition_variable_any's
members:
void notify_one() noexcept;
void notify_all() noexcept;
void wait(Lock& lock);
void wait(Lock& lock, Predicate pred);
cv_status wait_until(Lock& lock, const
chrono::time_point<Clock, Duration>& absTime);
bool wait_until(Lock& lock, const chrono::time_point<Clock, Duration>&
absTime, Predicate pred);
cv_status wait_for(Lock& lock, const chrono::duration<Rep,
Period>& relTime);
bool wait_for(Lock& lock, const chrono::duration<Rep, Period>&
relTime,)
Predicate pred
;
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:
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 releasedAt 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 releasedAt 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(); }
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.8.5.3). According to the C++11 standard, condition
variables may spuriously return from wait
calls. Therefore it is necessary
to check that the data are actually available once wait
continues.
The class condition_variable
allows us to do that by offering wait
members expecting a lock and a predicate. The predicate checks the data's
state, and returns true
if the data's state allows the data's
processing. Here is an alternative implementation of the down
member shown
in section 18.8.5.3, checking for the data's actual availability:
void down() { unique_lock<mutex> lock(sem_mutex); condition.wait(lock, [&]() { return semaphore != 0 } ); --semaphore; }The lambda expression ensures that
wait
only returns once
semaphore
has been incremented.
<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.
The linear_congruential_engine
random number generator computes
value
i+1 = OPENPAa * value
i +
c) % m
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
value
i = (value
i-s -
value
i-r - carry
i-1) % m
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.
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):
result_type max() const
result_type min() const
param_type param() const
param_type
struct;
void param(const param_type ¶m)
redefines the parameters of the distribution;
void reset():
clears all of its cached values;
All distributions support the following operators (distribution-name
should be replaced by the name of the intended distribution, e.g.,
normal_distribution
):
template<typename URNG> result_type operator()(URNG &urng)
urng
returning the next random number selected
from a uniform random distribution;
template<typename URNG> result_type operator()
(URNG &urng, param_type ¶m)
param
struct. The function object urng
returns the next random number selected from a uniform random
distribution;
std::istream &operator>>(std::istream &in,
distribution-name &object):
The parameters of the distribution are extracted from an
std::istream
;
std::ostream &operator<<(std::ostream &out,
distribution-name const &bd):
The parameters of the distribution are inserted into an
std::ostream
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'; }
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.10.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:
bernoulli_distribution(double prob = 0.5)
prob
of
returning true
;
double p() const
prob
;
result_type min() const
false
;
result_type max() const
true
;
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:
binomial_distribution<>(IntType trials = 1, double prob = 0.5)
constructs a binomial distribution for trials
experiments, each
having probability prob
of success.
binomial_distribution<>(param_type const ¶m)
constructs a binomial distribution according to the values stored in
the param
struct.
IntType t() const
trials
;
double p() const
prob
;
result_type min() const
result_type max() const
trials
;
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:
cauchy_distribution<>(RealType a = RealType(0),
RealType b = RealType(1))
constructs a cauchy distribution with specified a
and b
parameters.
cauchy_distribution<>(param_type const ¶m)
constructs a cauchy distribution according to the values stored in
the param
struct.
RealType a() const
a
parameter;
RealType b() const
b
parameter;
result_type min() const
result_type
value;
result_type max() const
result_type
;
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:
chi_squared_distribution<>(RealType n = 1)
constructs a chi_squared distribution with specified number of degrees
of freedom.
chi_squared_distribution<>(param_type const ¶m)
constructs a chi_squared distribution according to the value stored in
the param
struct;
IntType n() const
result_type min() const
result_type max() const
result_type
;
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:
extreme_value_distribution<>(RealType a = 0, RealType b = 1)
constructs an extreme value distribution with specified a
and
b
parameters;
extreme_value_distribution<>(param_type const ¶m)
constructs an extreme value distribution according to the values
stored in the param
struct.
RealType a() const
RealType stddev() const
result_type min() const
result_type
;
result_type max() const
result_type
;
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:
exponential_distribution<>(RealType lambda = 1)
constructs an exponential distribution with specified lambda
parameter.
exponential_distribution<>(param_type const ¶m)
constructs an exponential distribution according to the value stored in
the param
struct.
RealType lambda() const
lambda
parameter;
result_type min() const
result_type max() const
result_type
;
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.10.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:
fisher_f_distribution<>(RealType m = RealType(1),
RealType n = RealType(1))
constructs a fisher_f distribution with specified degrees of freedom.
fisher_f_distribution<>(param_type const ¶m)
constructs a fisher_f distribution according to the values stored in
the param
struct.
RealType m() const
RealType n() const
result_type min() const
result_type max() const
result_type
;
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 * beta
2.
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:
gamma_distribution<>(RealType alpha = 1, RealType beta = 1)
constructs a gamma distribution with specified alpha
and beta
parameters.
gamma_distribution<>(param_type const ¶m)
constructs a gamma distribution according to the values stored in
the param
struct.
RealType alpha() const
alpha
parameter;
RealType beta() const
beta
parameter;
result_type min() const
result_type max() const
result_type
;
geometric_distribution<IntType = int>
is used to model the number
of bernoulli trials (cf. 18.10.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:
geometric_distribution<>(double prob = 0.5)
constructs a geometric distribution for bernoulli trials each having
probability prob
of success.
geometric_distribution<>(param_type const ¶m)
constructs a geometric distribution according to the values stored in
the param
struct.
double p() const
prob
parameter;
param_type param() const
param_type
structure;
void param(const param_type ¶m)
redefines the parameters of the distribution;
result_type min() const
0
);
result_type max() const
template<typename URNG> result_type operator()(URNG &urng)
template<typename URNG> result_type operator()
(URNG &urng, param_type ¶m)
param
struct.
#include <iostream> #include <ctime> #include <random> int main() { std::linear_congruential_engine<unsigned, 7, 3, 61> engine(0); std::geometric_distribution<> dist; for (size_t idx = 0; idx < 10; ++idx) std::cout << "a random value: " << dist(engine) << "\n"; std::cout << '\n' << dist.min() << " " << dist.max() << '\n'; }
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 = e
X 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:
lognormal_distribution<>(RealType m = 0, RealType s = 1)
constructs a log-normal distribution for a random variable whose mean
and standard deviation is, respectively, m
and s
.
lognormal_distribution<>(param_type const ¶m)
constructs a
log-normal distribution according to the values stored in the
param
struct.
RealType m() const
m
parameter;
RealType stddev() const
s
parameter;
result_type min() const
result_type max() const
result_type
;
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:
normal_distribution<>(RealType mean = 0, RealType stddev = 1)
constructs a normal distribution with specified mean
and stddev
parameters. The default parameter values define the
standard normal distribution;
normal_distribution<>(param_type const ¶m)
constructs a normal distribution according to the values stored in
the param
struct.
RealType mean() const
mean
parameter;
RealType stddev() const
stddev
parameter;
result_type min() const
result_type
;
result_type max() const
result_type
;
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:
negative_binomial_distribution<>(IntType k = IntType(1),
double p = 0.5)
constructs a negative_binomial distribution with specified k
and
p
parameters;
negative_binomial_distribution<>(param_type const ¶m)
constructs a negative_binomial distribution according to the values
stored in the param
struct.
IntType k() const
k
parameter;
double p() const
p
parameter;
result_type min() const
result_type max() const
result_type
;
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:
poisson_distribution<>(double mean = 1)
constructs a poisson distribution with specified mean
parameter.
poisson_distribution<>(param_type const ¶m)
constructs a poisson distribution according to the values stored in
the param
struct.
double mean() const
mean
parameter;
result_type min() const
result_type max() const
result_type
;
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:
student_t_distribution<>(RealType n = RealType(1))
constructs a student_t distribution with indicated degrees of freedom.
student_t_distribution<>(param_type const ¶m)
constructs a student_t distribution according to the values stored in
the param
struct.
RealType n() const
result_type min() const
result_type max() const
result_type
;
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:
uniform_int_distribution<>(IntType a = 0, IntType b = max(IntType))
constructs a uniform_int distribution for the specified range of
values.
uniform_int_distribution<>(param_type const ¶m)
constructs a uniform_int distribution according to the values stored in
the param
struct.
IntType a() const
a
parameter;
IntType b() const
b
parameter;
result_type min() const
a
parameter;
result_type max() const
b
parameter;
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:
uniform_real_distribution<>(RealType a = 0, RealType b = max(RealType))
constructs a uniform_real distribution for the specified range of
values.
uniform_real_distribution<>(param_type const ¶m)
constructs a uniform_real distribution according to the values stored in
the param
struct.
RealType a() const
a
parameter;
RealType b() const
b
parameter;
result_type min() const
a
parameter;
result_type max() const
b
parameter;
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:
weibull_distribution<>(RealType a = 1, RealType b = 1)
constructs a weibull distribution with specified a
and b
parameters;
weibull_distribution<>(param_type const ¶m)
constructs a weibull distribution according to the values stored in
the param
struct.
RealType a() const
RealType stddev() const
result_type min() const
result_type max() const
result_type
;