C++11 – Part 8: Rvalue References and Move Semantics

While moving my hosting I noticed some posts that I never bothered tidying up to post. And although there has been a bit of a break, I am still writing these introduction to C++11 posts. Chances are low that I will have the C++11 posts finished before C++14 arrives! Moving on…

Consider the following code snippet:

template swap(T& a, T& b) {
  T t(a);   // #1
  a = b;    // #2
  b = t;    // #3
}

On line #1, we end up with two copies of a, line #2 gives two copies of b and line three is back to two copies of (the original) a. If T is a type that requires extensive copying this requires quite a bit of overhead. The standard library has specialized cases for std::vector and std::string to remove that overhead, but it would be good to get rid of it in general.

Lets consider another example:

T foo() {
  T t;
  // do "foo" on t...
  return t;
}
T u = foo();

Here foo() returns a temporary copy of t constructed on the stack and then that is passed to the T copy constructor to initialize u. Again this can have a substantial overhead. (I am ignoring return-type optimization here…)

From these examples, it should be clear that such overhead is reasonably common in C++ (and seems to be one of the biggest criticisms of the language). To fix this, a new non-const reference type is added in C++11, called an r-value reference and denoted T&&.

Firstly, what is an r-value? They are temporary objects that tend to fall on the right hand side of an equation. Because they are temporary objects, you can not assign to them. Also, you can not assign a r-value to a regular reference. E.g.

int& foo = bar()

will fail because bar() is returning a temporary value, which would be bad if it was able to be modified.

Using the r-value reference, we can add what is termed a “move constructor” and a “move assignment operator” to our class:

Foo::Foo(Foo&& f);
Foo& Foo::operator=(Foo&& f);

Note their arguments are both non-const, the reasons for which should become obvious.

Lets look at the copy constructor some more. For the sake of this example I will assume that Foo only contains an array and a variable storing its size. The copy constructor would look something like:

Foo::Foo(Foo&& f) {
  size=f.size;
  array=f.array;
  f.size=0;
  f.array=NULL;
}

What the move constructor has done is pilfered the resources of the temporary object, then reset the temporary object’s resources to being empty. This saves overhead of copying the array and setting the NULL prevents the memory being freed when the temporary object goes out of scope. The move assignment operator is exactly the same, except it frees any resources it currently owns first (like a normal assignment operator does).

How does this help our situation in the swap function above? We tell the compiler that it is OK to treat the right hand side of all the assignments as r-values using the std::move() function. So, the function becomes:

template swap(T& a, T& b) {
  T t(move(a));
  a = move(b);
  b = move(t);
}

Now at any time there is only one copy of a and b and the copying does not require any storage overhead.

Posted in C++11 on by Allan Comments Off on C++11 – Part 8: Rvalue References and Move Semantics

C++11 – Part 7: Constant Expressions

Constant expressions are an interesting area of the C++11 standard. They really do not really allow you to achieve anything new with the language, but they do allow it to be achieved in a more simple fashion and extend the list of things that can be done at compile time making everything faster! Lets start off with a simple example of the sort of issues that needed solved:

std::size_t three() { return 3; }

A nice simple function… What might we do with such a function? How about:

const std::size_t i = three();

This is perfectly legal in C++03, but the assignment is evaluated at runtime. That means that many optimizations involving i might be missed. Another example:

int i[three()];

This is not legal C++03, although it may work depending on your compiler. Moving on to an example that definitely breaks!

template<size_t T> struct S {};
S<three()> s;

I do not know of a compiler that accepted that. You may think of these as a bit of a contrived example, but consider that things like std::numeric_limits<int>::max() are functions and running into these sorts of issues was not uncommon. There was a work around in the last case in terms of using C-style macros (e.g. INT_MAX) at the cost of losing type safety, or declaring a constant variable as in the first usage example above with all its disadvantages.

C++11 introduces the keyword constexpr to work around these issues. This is a guarantee that result of the function is a constant, provided the function is passed constant parameters. So, the function above can be declared as

constexpr std::size_t three() { return 3; }

Now the compiler knows that this function produces a constant so it is evaluated at compile time.

There are a few restrictions on what functions can be declared as constexpr. Essentially, it needs to a function that only contains single return statement that uses only literals, constexpr variables (defined later) and other constexpr functions. There are some other minor allowances for what the function may have such as (some) typedefs and using statements, but thinking of it as a one line function is probably best. Some recursion is allowed (compiler dependent but must be up to 512 levels), so calculating a factorial at compile time can done using:

constexpr int f(int x) { return x > 1 ? x * f(x - 1) : 1; }

Evaluating a factorial at compile time could previously be done by template metaprogramming, but that has some overhead and is much more difficult to specify. One thing to note is that the parameter of the factorial function does not need to be a constexpr, but the result will then be calculated at runtime.

This brings me to the difference between const variables and constexpr variables. Variables declared as constexpr are const but with some more restrictions. They must be immediately constructed (so nothing like extern constexpr int i;) and can only be constructed using literals and other constexpr variables and functions.

Now we know that every object that is used in a constexpr function must itself be a constexpr, but what about objects that have constructors? They can be used provided that their constructor is a constexpr so that it has only member initializations (using only other constexpr constructors if needed…). For example:

class Foo
{
  constexpr Foo(int foo) : _foo(foo) {}
  constexpr foo() { return _foo; }
private:
  int _foo;
};

With that class, a variable of type Foo can be declared as a constexpr. Also the Foo.foo() function is a constexpr and thus can be used anyway one is needed.

C++11 – Part 6: Lambda Expressions

Lambda expressions provide a way to specify unnamed functions on the fly. While such a thing may seem a bit weird to those only familiar with the C family of languages, this is a fairly common feature of most programming languages.

The basic syntax of a lambda expression is:

[capture](arguments)->return-type{body}

Lets start with the common example, sorting by absolute value. Taking a std::vector<int> v, we can sort by absolute value using something like:

std::sort(v.begin(), v.end(), [](int x, int y) { return abs(x) < abs(y); } );

Walking through the parts of the lambda expression, firstly we have the capture field, []. This is a list of variables in the scope of the lambda function that are able to be accessed in the expression. In this case there is noting captured, so the capture field is empty. If we want to use variables in the scope of the lambda function, they are specified in a comma separated list within the []. For example, to calculate the sum of all items in a std::vector<int>, we could use:

int total = 0;
std::for_each(v.begin(), v.end(), [&total](int x) { total += x; } );

Note that by default variables are captured by value. The & in front of total tells the lambda function to capture it by reference and thus allow it to be changed. To capture all variables by value, use [=] and use [&] to capture all by reference. The later values in the capture field override the earlier ones, so [=, &x] captures all variables by value except for x which is captured by reference.

The arguments passed to the lambda function are just like the arguments of a normal function. Of course, the lambda function can be passed no arguments by using (). An optional return type can be provided using the suffix return syntax introduced earlier in this series. If not specified, the return type is deduced from the return statement (much like using auto), or is void if no value is returned.

That leaves the function body. Technically, any block of code can be put in the function body, but you are probably doing it wrong if the function is going to be more than a couple of lines long...

Posted in C++11 on by Allan Comments Off on C++11 – Part 6: Lambda Expressions

C++11 – Part 5: Initialization

C++11 bring with it a great improvement in initializing data. I’ll first cover initializing containers and then move on to more general variable initialization.

Initializer lists
Arrays could always be initialized using C style initialization:

int arr[] = {1,2,3,4,5};

But, that syntax could not be used with containers. That seemed a bit silly given that (e.g.) a std::vector is just a fancy array, so losing features that arrays have is bad. C++11 allows this type of initialization for all containers. You can also add this type of initialization for any of your classes, or even as an argument to a function. This works by the {} initialization works is that it creates an object of a new class std::initializer_list. So for this to be used in your class, you just need to add the relevant constructor. E.g.:

template<class t> class Vec
public:
  Vec(std::initializer_list i)
  {
  size = i.size();  // set the size of the array in Vec
  reserve(size);    // allocate the required space in the array
  uninitialized_copy(i.begin(), i.end(), array);
  }
// ...

Defining a function that takes an initializer list as an argument is similarly easy.

Uniform Initialization
In C++03, initialization of variables was all over the place. Initializer lists improve on that somewhat, but C++11 takes it one step further. Now everything can be initialized in much the same way. Some cases taken straight from the proposal:

  • Variable initialization; e.g., X x {v};
  • Initialization of a temporary; e.g, X{v}
  • Explicit type conversion; e.g. x = X{v};
  • Free store allocation; e.g. p = new X{v}

There are a few situations where I see this as being particularly useful:

1. Initialisation of dynamically allocated arrays:
int *p = new int[3]{1,2,3};

2. Initialization of an array member variable:
class C {
  int a[3];
public:
  C(int x, int y, int z) : a{x, y, z} { /* ... */ };
};

3. Implicitly initialize objects to return:
return {foo, bar};

4. Implicitly initialize a function parameter:
f({foo, bar});

There are some slight traps with the use of this initialization syntax with classes using constructors. For example, take the class C in case #2 above. The following two statements are equivalent:

C c1(1,2,3);
C c2{1,2,3};

However, for std::vector, which is able to be initialized using an initializer list, the following are different:

std::vector v1(10,3); // vector of length 10
std::vector v1{10,3}; // vector of length 2

C++11 – Part 4: Template Tidbits

C++11 saw a bunch of changes to template handling that overall are fairly minor. The first two will I cover allow what seem fairly obvious things that I am sure most C++ programmers attempted when they were learning the language. The third is not really a language change in itself, but more of a method to help the compiler and linker do less work.

Right-angle Brackets
When specifying a template within a template, there is no longer a need to put a space between the “>“s. For example, a poor man’s matrix can now be specified as:

std::vector<std::vector<double>>

Not a big feature by any means, but a great improvement!

Template Aliases
There are limitations with typedef and templates. Specifically, typedef can only be used to define fully qualified types, so does not work in cases where you want to partially specialize a template. The standard example (as in, straight from the Standard) is if you want to provide your own allocator for a std::vector. Now you can define a type for that using:

template<class T>
  using Vec = std::vector<T, Alloc<T>>;
Vec<int> v;    // same as std::vector<int, Alloc<int>> v;

Note that ordinary type aliases can be declared using the using syntax instead of typedef, and in my opinion is a far nicer syntax.

Extern Templates
To understand this feature, you first need to have some idea about how C++ compilers deal with templates. Lets see if I can explain this correctly… Consider this code snippet:

Foo<int> f;
f.bar();

When the compiler reaches the first line, it does a implicit initialization of the constructor (and destructor) of Foo<int> (if it has not been done previously in this translation block). That is, it creates the code for the int version of Foo. Generating the code on usage makes sense with templates as we do not know what types will be used when we declare the class (hence the use of templates…). The second line accesses the bar() method of Foo<int> and so that function gets implicitly initialized.

A disadvantage of implicit initialization is that we would have to use every method to let the compiler catch issues when using a class with a particular type. Also, the initialize a bit here and there approach might be slower. To work around this we can do an explicit initialization of the class:

template class Foo<int>;

The disadvantage of this is that if you class has a method that is not usable for a particular type (e.g. due to a class method requiring an operator that is not implemented for the type), then an explicit initialization will try to initialize that method and fail. With implicit initialization, the methods are initialized as called and so the unusable method is never encountered by the compiler. This is all in C++03.

OK… more details about the compiler. What happens when we have two translation units that are compiled separately then linked together that both use the Foo<int>? At compile time, the compiler has no idea that both these files use the that class, so initializes it for both files as needed. Not only is this a waste of compiler time, but then the linker spots these two identical initializations and strips one out (ideally…), so it wastes linker time too. C++11 provides a way to deal with this. In one source file, Foo<int> gets explicitly initialized. Then in all remaining source files that link with this, template initialization can be suppressed using:

extern template class Foo<int>;

One potential use for this is creating a shared library. If you know the finite set of types your template class/function is going to be used for, you can provide a header with just the declarations and the required extern lines. In the library source, you provide the definitions and explicitly initialize them. That way, any users of your library will just have to include the header and they are done. The compiler will automatically not implicitly initialize anything.

Posted in C++11 on by Allan Comments Off on C++11 – Part 4: Template Tidbits

C++11 – Part 3: Range-Based For Loops

A fairly common thing to do with an array or container is to loop over its values. Consider the following loop for loop over a std::vector<int> v:

for(std::vector<int>::const_interator i = v.begin(); i != v.end(); ++i)

Based on what is already covered in this series, we can simplify this statement to:

for(auto i = v.begin(); i != v.end(); ++i)

That is already a big improvement, but there is the tedium of always specifying the begin and end values. This is where the new range-based for loop syntax comes in. The entire expression can be reduced to:

for(auto i : v)

Note that i in this syntax is not the iterator, but the value the iterator points to so there is no need to dereference it in the loop body. All standard loop control such as break and continue can be used as in a traditional loop. If you want to modify the variable (or avoid passing around large data types by value) and the underlying iterator supports it, you should make the loop variable a reference:

for(auto& i : v)

This syntax can be used for arrays and any container from the STL. You can also use it on your own containers provided a few conditions are met. Firstly it must have either both begin() and end() member functions, or have free standing begin() and end() functions that take it as a parameter. These functions need to return an iterator, which by definition is required to implement operator++(), operator!=() and operator*().

Posted in C++11 on by Allan Comments Off on C++11 – Part 3: Range-Based For Loops

C++11 – Part 2: Suffix Return Type Syntax

Welcome to part 2 of my ramblings about C++11. Note that all of these posts are in the C++11 category, so it is easy to go an read previous entries. This post is going to focus on a new syntax for declaring the return type of functions.

Lets go back to the example of calculating a dot product of two vectors given in the first post of this series:

template<class T, class U>
void dot_product(const vector<T> vt, const vector<U> vu)

Once it is calculated, we probably want to actually return the value! However, we do not know the type of the output. Using decltype seems the way to go. For example:

template<class T, class U>
decltype(vt[0] * vu[0]) dot_product(const vector<T> vt, const vector<U> vu);

However, there is an issue here… And it is not the fact that vt[0] might not exist if you provide a zero length vector, as that does not matter (I guess because the return type of the [] operator is known). Nor is it that the result might overflow the type of an individual multiplication – stop being picky about fake code! The issue is that we do not know what vt and vu are at that stage of the function declaration. You could use:

decltype(*(T*)(0)**(U*)(0))

but the less said about that the better… This is where a new (optional) function declaration syntax comes into play:

template<class T, class U>
auto dot_product(const vector<T> vt, const vector<U> vu) -> decltype(vt[0] * vu[0]);

Although useful for templates, this syntax is really about scope. For example, consider:

class Foo
{
public:
  enum Bar { FOO, BAR, BAZ };
  Bar getBar();
private:
  Bar bar;
};

When defining the function getBar(), the following is wrong:

Bar Foo::getBar() { /* ... */ }

as Bar is out of scope – at that stage we do not know we are in a method for the Foo class. That can be easily fixed in this case by using Foo::Bar as the return type, but that can get messy in more complex cases. Better to use:

auto Foo::getBar() -> Bar { /* ... */ }

Then by the time Bar is reached, we know we are in the scope of the Foo class.

Posted in C++11 on by Allan Comments Off on C++11 – Part 2: Suffix Return Type Syntax

C++11 – Part 1: Automatic Types

My C++ skills are getting a bit rusty as I have not done much programming in that language lately. So I thought what better way to refresh my skills and learn new stuff than to go through the C++11 changes and write something about them. I will not cover all additions and changes to the standard, but instead focus on those I am likely to use, (which means they must be implemented in GCC). And even those I do focus on, will likely miss some subtleties that I find unimportant (or more likely am unaware of…). For those wanting actual detail, a late working paper that is a near final draft of the C++11 standard can be downloaded here.

This first post is going to focus on type deduction and its uses.

auto
In C++98, you have to declare the type of every variable being used. C++11 introduces the auto keyword, which lets the compiler deduce the type of a variable given its initializer. So you could write:

auto x = 5;

and you would get that x is declared to be an int. Like everything in programming, there is times when you should use a feature and times when you should not… This is an example of a time where you should not. The use of auto should be reserved for situations where you really do not know the type of the result or that the type is unwieldy to write. For example:

template<class T, class U>
void dot_product(const vector<T> vt, const vector<U> vu)
{
  //...
  auto tmp = vt[i] * vu[i]
  //...
}

A bit of a contrived example, but it should be clear that the type of the result depends on the template parameters U and V so is unknown. I will get to the return type in the next post…

A more useful example where the type of the variable is known but unwieldy is:

std::vector<std::pair<std::string, int>> v;
//...
for(auto i = v.begin(), i != v.end(), ++i) {
//...

Here the type of i is known (std::vector<std::pair<std::string,int>>::const_iterator), but writing that would quickly become tedious and error prone. I guess most situations like this were previously handled with a typedef statement.

There are other uses of auto that will be covered in later posts when the relevant features are introduced.

decltype
The decltype operator takes an expression and returns it type. A trivial example:

int x = 5;
decltype(x) y = x;

This declares the variable y to have the same type as x. Of course you could use auto here (or preferably neither in this case…), but the use of decltype comes into its own when you actually need a type – for example, a return type, which will be covered in the second post in this series.