Utilities - The Standard Library - The C++ Programming Language (2013)

The C++ Programming Language (2013)

Part IV: The Standard Library

35. Utilities

The time you enjoy wasting is not wasted time.

– Bertrand Russell

Introduction

Time

duration; time_point; Clocks; Time Traits

Compile-Time Rational Arithmetic

Type Functions

Type Traits; Type Generators

Minor Utilities

move() and forward(); swap(); Relational Operators; Comparing and Hashing type_info

Advice

35.1. Introduction

The standard library provides many “utility components” that are so widely useful that they are not easily classified as part of some major standard-library component.

35.2. Time

In <chrono>, the standard library provides facilities for dealing with time durations and time points. All chrono facilities are in the std::chrono (sub)namespace, so we have to either explicitly qualify with chrono:: or add a using-directive:

using namespace std::chrono;

We often want to time things or to do things that depend on timing. For example, the standard-library mutexes and locks provide the option for a thread to wait for a period of time (a duration) or to wait until a given point in time (a time_point).

If you want to know the current time_point, you can call now() for one of three clocks: system_clock, steady_clock, high_resolution_clock. For example:

steady_clock::time_point t = steady_clock::now();
//
... do something ...
steady_clock::duration d = steady_clock::now()–t; // something took d time units

A clock returns a time_point, and a duration is the difference between two time_points from the same clock. As usual, if you are not interested in details, auto is your friend:

auto t = steady_clock::now();
//
... do something ...
auto d = steady_clock::now()–t; // something took d time units
cout << "something took " << duration_cast<milliseconds>(d).count() << "ms"; // print as milliseconds

The time facilities here are intended to efficiently support uses deep in the system; they do not provide convenience facilities to help you maintain your social calendar. In fact, the time facilities originated with the stringent needs of high-energy physics.

It turns out that “time” is far more complicated to deal with than we usually think. For example, we have leap seconds, clocks that are not accurate and must be adjusted (possibly causing time as reported by a clock to go backward), clocks of differing precision, etc. Furthermore, language facilities for dealing with short time spans (e.g., nanoseconds) must not themselves take significant time. Consequently, the chrono facilities are not simple, but many uses of those facilities can be very simple.

The C-style time utilities can be found in §43.6.

35.2.1. duration

In <chrono>, the standard library provides type duration to represent the time between two points in time (time_points §35.2.2):

template<typename Rep, typename Period = ratio<1>>
class duration {
public:
using rep = Rep;
using period = Period;
//
...
};

Image

We can define a duration with a specific period value. For example:

duration<long long,milli> d1 {7}; // 7 milliseconds
duration<double,pico> d2 {3.33}; // 3.33 picoseconds
duration<int,ratio<1,1>> d3 {}; // 0 seconds

A duration’s period holds the number of clock ticks of the period.

cout << d1.count() << '\n'; // 7
cout << d2.count() << '\n'; // 3.33
cout << d3.count() << '\n'; // 0

Naturally, the value of count() depends on the period:

d2=d1;
cout << d1.count() << '\n'; //
7
cout << d2.count() << '\n'; // 7e+009
if (d1!=d2) cerr<<"insane!";

Here, d1 and d2 are equal but report very different count() values.

Care is taken to avoid truncation or loss of precision during initialization (even if the {} notation is not used). For example:

duration<int, milli> d {3}; // OK
duration<int, milli> d {3.5}; // error: 3.5 to int is narrowing

duration<int, milli> ms {3};
duration<int, micro> us {ms}; //
OK
duration<int, milli> ms2 {us}; // error: we could lose many microseconds

The standard library provides meaningful arithmetic operations on durations:

Image

The period is a unit system, so there is no = or += taking a plain value. Allowing that would be like allowing the addition of 5 of an unknown SI unit to a length in meters. Consider:

duration<long long,milli> d1 {7}; // 7 milliseconds
d1 += 5; // error

duration<int,ratio<1,1>> d2 {7}; // 7 seconds
d2 = 5; // error
d2 += 5; // error

What would 5 mean here? 5 seconds? 5 milliseconds? Something else? If you know what you mean, be explicit about it. For example:

d1 += duration<long long,milli>{5}; // OK: milliseconds
d3 += decltype(d2){5}; // OK: seconds

Arithmetic involving durations with different representations is allowed as long as the combination makes sense (§35.2.4):

Image

Comparisons between and explicit conversion between durations with compatible representations are supported:

Image

The standard library provides some convenience aliases using the SI units from <ratio>35.3):

using nanoseconds = duration<si64,nano>;
using microseconds = duration<si55,micro>;
using milliseconds = duration<si45,milli>;
using seconds = duration<si35>;
using minutes = duration<si29,ratio<60>>;
using hours = duration<si23,ratio<3600>>;

Here, siN means “an implementation-defined signed integer type of at least N bits.”

The duration_cast is used to get a duration with a known unit of measurement. For example:

auto t1 = system_clock::now();
f(x); //
do something
auto t2 = system_clock::now();

auto dms = duration_cast<milliseconds>(t2–t1);
cout << "f(x) took " << dms.count() << " milliseconds\n";


auto ds = duration_cast<seconds>(t2–t1);
cout << "f(x) took " << ds.count() << " seconds\n";

The reason we need a cast in this example is that we are throwing away information: on the system I used, the system_clock counts in nanoseconds.

Alternatively, we can simply (try to) construct a suitable duration:

auto t1 = system_clock::now();
f(x); //
do something
auto t2 = system_clock::now();

cout << "f(x) took " << milliseconds(t2–t1).count() << " milliseconds\n"; //
error: truncation
cout << "f(x) took " << microseconds(t2–t1).count() << " microseconds\n";

The precision of a clock is implementation-dependent.

35.2.2. time_point

In <chrono>, the standard library provides type time_point to represent a point in time of a given epoch as measured by a given clock:

template<typename Clock, typename Duration = typename Clock::duration>
class time_point {
public:
using clock = Clock;
using duration = Duration;
using rep = typename duration::rep;
using period = typename duration::period;
//
...
};

An epoch is a range of time determined by a clock, measured in terms of a duration, starting at the duration::zero():

Image

For example:

void test()
{
time_point<steady_clock,milliseconds> tp1(milliseconds(100));
time_point<steady_clock,microseconds> tp2(microseconds(100*1000));


tp1=tp2; // error: would truncate
tp2=tp1; // OK

if (tp1!=tp2) cerr << "Insane!";
}

As for durations, meaningful arithmetic and comparisons are supported for time_points:

Image

For example:

void test2()
{
auto tp = steady_clock::now();
auto d1 = time_point_cast<hours>(tp).time_since_epoch().count()/24; //
days since start of epoch

using days = duration<long,ratio<24*60*60,1>>; // a day's duration
auto d2 = time_point_cast<days>(tp).time_since_epoch().count(); // days since start of epoch

if (d1!=d2) cout << "Impossible!\n";
}

The time_point operations that do not access a clock can be constexpr, but are not currently guaranteed to be so.

35.2.3. Clocks

The time_point and duration values are ultimately obtained from hardware clocks. In <chrono>, the standard library provides basic interfaces for clocks. Class system_clock represents “wall clock time” as obtained from a system’s real-time clock:

class system_clock {
public:
using rep = /*
implementation-defined signed type */;
using period = /*
implementation-defined ratio<> */;
using duration = chrono::duration<rep,period>;
using time_point = chrono::time_point<system_clock>;
//
...
};

All data and function members are static. We don’t explicitly deal with clock objects. Instead, we use clock types:

Image

For example:

void test3()
{
auto t1 = system_clock::now();
f(x); //
do something
auto t2 = system_clock::now();
cout << "f(x) took " << duration_cast<milliseconds>(t2–t1).count() << " ms";
}

A system provides three named clocks:

Image

These three clocks need not be different; a standard-library clock name may be an alias.

We can determine the basic properties of the clocks like this:

cout << "min " << system_clock::duration::min().count()
<< ", max " << system_clock::duration::max().count()
<< ", " << (treat_as_floating_point<system_clock::duration>::value ? "FP" : "integral") << '\n';


cout << (system_clock::is_steady?"steady\n": "not steady\n");

When I ran it on one of my systems, this produced:

min –9223372036854775808, max 9223372036854775807, integral
not steady

Different systems and different clocks can give different results.

35.2.4. Time Traits

Implementations of the chrono facilities depend on a few standard facilities, collectively known as time traits.

The conversion rules for duration and time_point depend on whether their representation is floating-point (so that rounding is acceptable) or integral:

template<typename Rep>
struct treat_as_floating_point : is_floating<Rep> { };

A few standard values are provided:

Image

The common type of two durations is determined by computing their greatest common denominator (GCD):

template<typename Rep1, typename P1, typename Rep2, typename P2>
struct common_type<duration<Rep1,P1>, duration<Rep2, P2>> {
using type = duration<typename common_type<Rep1,Rep2>::type, GCD<P1,P2>> ;
};

This makes type an alias for the duration with the largest possible tick period so that both duration arguments will convert to it without requiring a division operation. This implies that common_type<R1,P1,R2,P2>::type can hold any value from duration<R1,R2> and duration<R2,P2>without truncation error. However, floating-point durations may have round-off errors.

template<typename Clock, typename Duration1, typename Duration2>
struct common_type<time_point<Clock, Duration1>, time_point<Clock, Duration2>> {
using type = time_point<Clock, typename common_type<Duration1, Duration2>::type>;
};

In words, to have a common_type, two time_points must have a common clock type. Their common_type is a time_point with the common_type of their durations.

35.3. Compile-Time Rational Arithmetic

In <ratio>, we find class ratio, which provides compile-time rational arithmetic. The standard library uses ratio to provide a compile-time representation of time duration and time points (§35.2):

template<intmax_t N, intmax_t D = 1>
struct ratio {
static constexpr intmax_t num;
static constexpr intmax_t den;


using type = ratio<num,den>;
};

The basic idea is to encode the numerator and denominator of a rational number as (value) template arguments. The denominator must always be nonzero.

Image

For example:

static_asser t(ratio_add<ratio<1,3>, ratio<1,6>>::num == 1, "problem: 1/3+1/6 != 1/2");
static_asser t(ratio_add<ratio<1,3>, ratio<1,6>>::den == 2, "problem: 1/3+1/6 != 1/2");
static_asser t(ratio_multiply<ratio<1,3>, ratio<3,2>>::num == 1, "problem: 1/3*3/2 != 1/2");
static_asser t(ratio_multiply<ratio<1,3>, ratio<3,2>>::den == 2, "problem: 1/3*3/2 != 1/2");

Obviously, this is not a convenient way of expressing numbers and arithmetic. In <chrono>, we find the conventional notation (e.g., + and *) for rational arithmetic for time (§35.2). Similarly, to help express unit values, the standard library provides common SI magnitude names:

using yocto = ratio<1,1000000000000000000000000>; // conditionally supported
using zepto = ratio<1,1000000000000000000000>; // conditionally supported
using atto = ratio<1,1000000000000000000>;
using femto = ratio<1,1000000000000000>;
using pico = ratio<1,1000000000000>;
using nano = ratio<1,1000000000>;
using micro = ratio<1,1000000>;
using milli = ratio<1,1000>;
using centi = ratio<1,100>;
using deci = ratio<1,10>;
using deca = ratio<10,1>;
using hecto = ratio<100,1>;
using kilo = ratio<1000,1>;
using mega = ratio<1000000,1>;
using giga = ratio<1000000000,1>;
using tera = ratio<1000000000000,1>;
using peta = ratio<1000000000000000,1>;
using exa = ratio<1000000000000000000,1>;
using zetta = ratio<1000000000000000000000,1>; //
conditionally supported
using yotta = ratio<1000000000000000000000000,1>; // conditionally supported

For an example of use, see §35.2.1.

35.4. Type Functions

In <type_traits>, the standard library provides type functions (§28.2) to determine properties of types (type traits; §35.4.1) and to generate new types from existing ones (type generators; §35.4.2). These type functions are primarily used at compile time to support simple, and not so simple, metaprogramming.

35.4.1. Type Traits

In <type_traits>, the standard library provides a large set of type functions that allow a programmer to determine properties of a type or a pair of types. Their names are mostly self-explanatory. The primary type predicates test fundamental properties of a type:

Image

Image

A type trait returns a value that is used as a Boolean. To access that value, use the suffix ::value. For example:

template<typename T>
void f(T& a)
{
static_asser t(std::is_floating_point<T>::value ,"FP type expected");
//
...
}

If you tire of the ::value notation, define a constexpr function (§28.2.2):

template<typename T>
constexpr bool Is_floating_point<T>()
{
return std::is_floating_point<T>::value;
}


template<typename T>
void f(T& a)
{
static_asser t(Is_floating_point<T>(),"FP type expected");
//
...
}

Ideally, use a library that provides such functions for all standard library type traits.

Some type functions inquire about a combination of fundamental properties:

Image

These composite type predicates simply offer notational convenience. For example, is_reference<X> is true if X is either an lvalue reference or an rvalue reference.

Like the primary type predicates, type property predicates provide tests for fundamental aspects of a type:

Image

For example:

template<typename T>
class Cont {

T* elem; // store elements in an array pointed to by elem
int sz; // sz elements
// ...
Cont(const Cont& a) // copy constructor
:sz(a.sz), elem(new T[a.elem])
{
static_asser t(Is_copy_constructable<T>(),"Cont::Cont(): no copy");
if (Is_trivially_copyable<T>())
memcpy(elem,a.elem,sz*sizeof(T)); //
memcopy optimization
else
uninitialized_copy(a.begin(),a.end(),elem); //
use copy constructors
}
//
...
}

This optimization may be unnecessary, though, because uninitialized_copy() is likely to already have been optimized in this way.

For a class to be empty, it can have no virtual functions, no virtual bases, and no base classes for which !is_empty<Base>::value.

The type property predicates don’t do access checking depending on where they are used. Instead, they consistently give the result you would expect for a use outside members and friends. For example:

class X {
public:
void inside();
private:

X& operator=(const X&);
~X();
};


void X::inside()
{
cout << "inside =: " << is_copy_assignable<X>::value << '\n';
cout << "inside ~: " << is_destructible<X>::value << '\n';
}


void outside()
{
cout << "outside =: " << is_copy_assignable<X>::value << '\n';
cout << "outside ~: " << is_destructible<X>::value << '\n';
}

Both inside() and outside() will write 00 to report that an X is neither destructible nor copy assignable. Also, if you want to eliminate an operation, use =delete17.6.4) rather than relying as private.

Image

For example, consider how we might optimize the destructor for a container type:

template<class T>
Cont::~Cont() // destructor for a container Cont
{
if (!Is_trivially_destructible<T>())
for (T* p = elem; p!=p+sz; ++p)
p–>~T();
}

Image

Like sizeof(T), a property query returns a numeric value related to a type argument:

Image

For example:

template<typename T>
void f(T a)
{
static_asser t(Is_array<T>(), "f(): not an array");
constexpr int dn {Extent<a,2>()}; //
the number of elements in the 2nd dimension (zero based)
// ..
}

Here, I again used constexpr versions of the type functions returning numeric values (§28.2.2).

The type relations are predicated on two types:

Image

For example:

template<typename T>
void draw(T t)
{
static_assert(Is_same<Shape*,T>() || Is_base_of<Shape,Remove_pointer<T>>(), "");
t–>draw();
}

35.4.2. Type Generators

In <type_traits>, the standard library provides type functions for producing a type given other types as arguments.

Image

A type transformer returns a type. To access that type, use the suffix ::type. For example:

template<typename K, typename V>
class My_map {
{
pair<typename add_const<K>::type,V> default_node;
//
...
};

If you tire of the ::type define a type alias (§28.2.1):

template<typename T>
using Add_const = typename add_const<T>::type;


template<typename K, typename V>
class My_map {
{
pair<Add_const<K>,V> default_node;
//
...
};

Ideally, use a support library that provides such aliases systematically for the standard-library type transformers.

Image

The decay functions handles array decay as well as reference dereferencing.

The type functions for adding and removing references are important for when writing templates that should work with an argument that may be reference or not. For example:

template<typename T>
void f(T v)
{

Remove_reference<T> x = v; // copy of v
T y = v; // maybe copy of v; maybe a reference to x
++x; // increment local variable
++y;
//
...
}

Here, x really is a copy of v, but if T is a reference type, y is a reference to v:

void user()
{
int val = 7;
f(val); //
call f<int&>(): the ++y in f() will increment val
f(7); // call f<int>(): the ++y in f will increment a local copy
}

In both calls, ++x will increment a local copy.

Image

For built-in arrays, we sometimes want to get the element type or to remove a dimension:

Image

For example:

int a[10][20];
Remove_extent<decltype(a)> a10; // an array[10]
Remove_all_extents<decltype(a)> i; // an int

We can make a pointer type pointing to an arbitrary type, or find the pointed-to type:

Image

For example:

template<typename T>
void f(T x)
{

Add_pointer<T> p = new Remove_reference<T>{};
T* p = new T{}; //
would not work if T is a reference
// ...
}

When dealing with memory at the lowest levels of a system, we must sometimes consider alignment (§6.2.9):

Image

The standard mentions this as a possible implementation of aligned_storage:

template<std::size_t N, std::size_t A>
struct aligned_storage {
using type = struct { alignas(A) unsigned char data[N]; }; //
N chars aligned to A (§6.2.9)
};

The final type functions for type selection, computing common types, etc. are arguably the most useful:

Image

For examples of enable_if and conditional, see §28.3.1.1 and §28.4.

It is often useful to find a type that can be used for operations on more than one type, such as the result of an addition of two values of related but different types. The type function common_type finds such common types. A type is the common type of itself (obviously):

template<typename... T>
struct common_type;


template<typename T>
struct common_type<T> {
using type = T;
};

The common type of two types is what the rules for ?:11.1.3) give us:

template<typename T, typename U>
struct common_type<T, U> {
using type = decltype(true ? declval<T>() : declval<U>());
};

The declval<T>() type function returns the type of an unevaluated variable of type T.

The common type for N types is found by applying the rules for N==1 and N==2 recursively:

template<typename T, typename U, typename ... V>
struct common_type<T, U, V...> {
using type = typename common_type<typename common_type<T, U>::type, V...>::type;
};

For example:

template<typename T, typename U>
using Common_type = typename common_type<T,U>::type;


Common_type<int,double> x1; // x1 is a double
Common_type<int,string> x2; // error: no common type
Common_type<int,short,long,long long> x3; // x3 is a long long
Common_type<Shape*,Circle*> x4; // x4 is a Shape*
Common_type<void*,double*,Shape*> x5; // x5 is a void*

Result_of is used to extract the type of the result of a callable type:

int ff(int) { return 2; } // function

typedef bool (*PF)(int); // pointer to function

struct Fct { // function object
double operator()(string);
string operator()(int,int);
};


auto fx = [](char ch) { return tolower(ch); }; // lambda

Result_of<decltype(&ff)()> r1 = 7; // r1 is a int
Result_of<PF(int)> r2 = true; // r2 is a bool
Result_of<Fct(string)> r3 = 9.9; // r3 is a double
Result_of<Fct(int,int)> r4 = "Hero"; // r4 is a string
Result_of<decltype(fx)(char)> r5 = 'a'; // r5 is a char

Note that Result_of can distinguish between the two versions of Fct::operator()().

Curiously enough, the same does not apply to nonmember functions. For example:

int f(); // function
string f(int);
Result_of<decltype(&f)()> r1 = 7; // error: no overload resolution for pointer to function

Unfortunately, we don’t do overload resolution for pointers to functions, but why did I use Result_of in such a roundabout way, instead of:

Result_of<ff> r1 = 7; // error: no argument specification,
// and ff is a function rather than a type
Result_of<ff()> r1 = 7; // error: the argument to Result_of must be a type
Result_of<decltype(f)()> r2 = 7; // error: decltype(f) is a function type
// rather than a pointer to function type
Result_of<decltype(f)*()> r3 = 7; // OK: r3 is an int

Naturally, Result_of is usually found in templates where we can’t easily look up the answer in the program text. For example:

template<typename F, typename A>
auto temp(F f, A a) –> Result_of<F(A)>
{

// ...
}

void f4()
{
temp(ff,1);
temp(fx,'a');
temp(Fct(),"Ulysses");
}

Note that the function ff is converted to a pointer function in the call, so the reliance on pointers to functions in Result_of isn’t as odd as it may seem at first.

Image

The declval() type function is unusual in the standard library because it is actually a function (without users needing to wrap it). It returns a value that must never be used. The intent is to use declval<X> as a type where the type of a variable of type X is needed. For example:

template<typename T, size_t N>
void array<T,N> swap(array& y) noexcept(noexcept(swap(declval<T&>(), declval<T&>())))
{
for (int i=0; i<a.size(); ++i)
swap((*this)[i],a[i]);
}

See also the definition of common_type.

35.5. Minor Utilities

These utilities are minor in size, but not in importance. They don’t fit into a larger grouping.

35.5.1. move() and forward()

In <utility>, we find some of the most useful small functions:

Image

A move() is simply a cast to an rvalue:

template<typename T>
Remove_reference<T>&& move(T&& t) noexcept
{
return static_cast<Remove_reference<T>&&>(t);
}

In my opinion, move() should have been called rvalue(), because it doesn’t actually move anything. Instead, it produces an rvalue for its argument, so that the object referred to can be moved from.

A move() is used to tell the compiler that an object will not be used anymore in a context, so that its value can be moved and an empty object left behind. The simplest example is the implementation of swap()35.5.2).

A forward() produces an rvalue from an rvalue only:

template<typename T>
T&& forward(Remove_reference<T>& t) noexcept
{
return static_cast<T&&>(t);
}


template<typename T>
T&& forward(Remove_reference<T>&& t) noexcept;
{
static_assert(!Is_lvalue_reference<T>,"forward of lvalue");
return static_cast<T&&>(t);
}

This pair of forward() functions are meant always to be available together, and selection between them should be done by overload resolution. In that case, any lvalue goes to the first version and every rvalue to the second. For example:

int i = 7;
forward(i); //
call first version
forward(7); // call second version

The assert is there for programmer who are too clever for their own good and calls the second version with an explicit template argument and an lvalue.

The archetypical use of forward() is for “perfect forwarding” of an argument from one function to another (§23.5.2.1, §28.6.3). The standard-library make_shared<T>(x)34.3.2) is a good example.

Use move() when the intent is to “steal the representation” of an object with a move operation, and use forward() for forwarding. Thus, forward(x) is safe, whereas move(x) marks x for destruction so that move(x) should be used with care. The only safe use of an x after a move(x) is destruction or as a target for an assignment. Obviously a particular type could provide further guarantees, and ideally the class’s invariant is left intact. However, don’t rely on that unless you really know.

35.5.2. swap()

In <utility>, the standard library provides a general swap() and a specialization for built-in arrays:

Image

The relatively obvious implementation swap() is:

template<typename T>
void swap(T& a, T& b) noexcept(Is_nothrow_move_constructible<T>()

&& Is_nothrow_move_assignable<T>())
{

T tmp {move(a)};
a = move(b);
b = move(tmp);
}

This implies that swap() cannot be used to exchange rvalues:

vector<int> v1 {1,2,3,4};
swap(v,vecor<int>{}); //
error: second argument is an rvalue
v.clear(); // clearer (less obscure)

35.5.3. Relational Operators

In <utility>, we find relational operators for arbitrary types in a sub-namespace rel_ops:

Image

This requires that the programmer has made sure that x==y and x<y work.

For example:

struct Val {
double d;
bool operator==(Val v) const { return v.d==d; }
};


void my_algo(vector<Val>& vv)
{
using namespace std::rel_ops;


for (int i=0; i<ww.size(); ++i)
if (0>ww[i]) ww[i]=abs(ww[i]); //
OK: > from rel_ops
}

It can be hard to use rel_ops without polluting a namespace. In particular:

namespace Mine {
struct Val {
double d;
bool operator==(Val v) const { return v.d==d; }
};


using namespace std::rel_ops;
}

This could expose the perfectly general templates from rel_ops to be found by argument-dependent lookup (§14.2.4) and applied to types for which they may be inappropriate. A safer approach is to place using-directives in local scopes.

35.5.4. Comparing and Hashing type_info

In <typeindex>, the standard library provides support for comparing and hashing type_indexs. A type_index is created from a type_info22.5), specifically to allow such comparison and hashing.

Image

For example:

unordered_map<type_index,type_info*> types;
//
...
types[type_index{something}] = &typeid(something);

35.6. Advice

[1] Use <chrono> facilities, such as steady_clock, duration, and time_point for timing; §35.2.

[2] Prefer <clock> facilities over <ctime> facilities; §35.2.

[3] Use duration_cast to get durations in known units of time; §35.2.1.

[4] Use system_clock::now() to get the current time; §35.2.3.

[5] You can inquire about properties of types at compile time; §35.4.1.

[6] Use move(obj) only when the value of obj cannot be used again; §35.5.1.

[7] Use forward() for forwarding; §35.5.1.