class Alon : public CPP, public Architecture

Introduction to C++ 11 Series – Part 10, Ranged-Based for-Loops

Alon Fliess — Tue, 09 Apr 2013 23:21:06 GMT

Yes, this is post #10 in the C++ 11 series. The last post was long and complicated. In this post, I would like to write about something simpler - Ranged base loops. Ranged Based Loops, are like the C# foreach loop. The idea is to simplify iteration syntax on containers that have a beginning, an ending, and a forward iterator.

Suppose we have this vector:

vector<int> v;

for (int i = 1; i <= 10; ++i)

v.push_back(i);

To iterate through the vector elements, use:

for (auto i: v)

cout << i << ", ";

This is somewhat similar to the old for-loop:

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

cout << *i << ", ";

or the STL algorithm for_each:

for_each(begin(v), end(v), [](int i)

{

cout << i << ", ";

});

You can also change the container element values:

for (auto &i: v)

i *= i;

The full example:

#include "stdafx.h"

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

vector<int> v;

for (int i = 1; i <= 10; ++i)

v.push_back(i);

for (auto i: v)

cout << i << ", ";

cout << endl;

for (auto &i: v)

i *= i;

for (auto i: v)

cout << i << ", ";

cout << endl;

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

cout << *i << ", ";

cout << endl;

for_each(begin(v), end(v), [](int i)

{

cout << i << ", ";

});

cout << endl;

return 0;

}

The result:

* One thing that you should be aware of: Using for (auto e : CollectionOfHeavyObjects)) results in a copy of each of the instances. In such cases you should prefer this:
for (const auto &e : CollectionOfHeavyObjects))

Custom Iterators:

To implement your own iterator, you just need to create a class that provides the: begin and end methods that return const-iterator and the iterator class that can iterate through the container. You can also implement the global begin and end that will return the needed iterator.

Instead of creating my own container, I have created a sample that enables range iteration:

#include "stdafx.h"

#include <iostream>

#include <chrono>

#include <string>

using namespace std;

template<class T, class S = T>

class Range

{

private:

class LoopIterator;

const T _from;

const T _to;

const S _step;

public:

Range(T from, T to, S step) : _from(from), _to(to), _step(step) {}

LoopIterator begin() const

{

return LoopIterator(*this);

}

LoopIterator end() const

{

return LoopIterator(*this, true);

}

class LoopIterator

{

private:

T _index;

const Range _range;

friend class Range;

LoopIterator(const Range &range, bool isEnd = false) :
_range(range), _index(isEnd ? range._to : range._from)

{

}

public:

bool operator!=(const LoopIterator& o) const

{

return _index < o._index;

}

const T& operator*() const

{

return _index;

}

LoopIterator& operator++()

{

_index += _range._step;

return *this;

}

};

int _tmain(int argc, _TCHAR* argv[])

{

for (auto i : Range<int>(1,11, 1))

cout << i << " , ";

cout << endl;

for (auto i : Range<double>(0.1, 1.0, 0.1))

cout << i << " , ";

cout << endl;

for (auto i : Range<string, char>("", "*******************", '*'))

cout << i << endl;

cout << endl;

       for (auto i : Range<chrono::system_clock::time_point,
              chrono::seconds>(chrono::system_clock::now(),
              chrono::system_clock::now() + chrono::minutes(1),
              chrono::seconds(1)))

{

auto time = chrono::system_clock::to_time_t(i);

tm lt;

localtime_s(&lt, &time);

cout << lt.tm_hour << ':' << lt.tm_min << ':' << lt.tm_sec << " \t";

}

cout << endl;

return 0;

}

The result:

As you can see, in the example, the Range template class gets a: from, to and step arguments. The T type has to support the T+=S operation as well as the T < T operation.

* Usually to check if the iterator has reached the end, the type has to provide the != operation, however since my Range::LoopIterator class supports step, I need to check also cases in which the end is beyond the normal end.

The: for (auto i : Range(1,11,1)) first calls the Range::begin method. This method in turn creates a LoopIterator instance with the current index equal to 1. Then the Range::end is called. This creates a LoopIterator instance with the index set to the: to argument – the end of the loop. Next the loop statement calls the operator != which in our case checks if the current index is still below the end of the loop. Only then the body of the loop is called followed by the operator++() that increments the index by step.

Using the custom Range class we can iterate different types that adhere the += and < conditions. In our case an integer, double, string + char and chrono::time_point with chrono::duration.

Read more about range-base-loops here. Look here for different Range implementation.

Introduction to C++ 11 Series – Part 9, R-Value, L-Value, Move Semantics and Perfect Forwarding

Alon Fliess — Thu, 04 Apr 2013 01:23:48 GMT

Take a deep breath; this is a long post about one of the most important and most complex features of C++ 11.

One of the most performance-boost features of C++ 11 is the new move semantics addition to the language. This feature is based on a new reference – an R-Value reference. In this post, I am going to explain what R-Value (and L-Value) is, why we need it, and how we can use it to enable move constructor & move assignment operator. We will also see the std::move function and talk about perfect forwarding and the std::forward function.

Motivation

C++ as opposed to C# & Java provides the ability to create a copy constructor and assignment operator for an object. This enables a user-defined deep copy of an instance, somewhat similar to a C#/Java clone method. The main difference from a clone method is that the compiler calls the Copy-constructor function implicitly when an instance of the object is passed by value as a parameter to a method or as a return value from the method. This is a very important behavior for application correctness for several reasons:

When returning a pointer or a reference of a function local variable, its memory location on the stack is freed, hence it is important to return a copy of this variable (or don’t use the stack but a heap based object)
When passing an object by pointer or reference, anyone can change the object’s values. If this object is a part (field) of another object, it may change without the supervision of its owner. I name a function that returns an inner state of an object a revealer. This is a major problem in C# and Java, and the correct implementation is to use the immutable pattern. In C++ sometimes, a const qualifier can help, but a clone provides better decoupling. Future changes of the original object will not affect an older copy and vice versa.
Copy-constructor is a necessary mechanism for stack based instance lifetime management.

These are good reasons for using copy constructor and assignment operator, however copying objects has a major performance impact. Especially for large objects or those that allocate heap memory in their constructor and free it in the destructor, such as the case of STL containers.

Example:

#include "stdafx.h"

#include <iostream>

#include <vector>

#include <crtdbg.h>

#include <random>

#include <algorithm>

#include <iterator>

#include <chrono>

using namespace std;

using namespace chrono;

class CCtorCounter

{

public:

CCtorCounter()

{

generate_n(back_inserter(payload), 10000, rand);

}

CCtorCounter(const CCtorCounter &o)

{

++counter;

cout << "CCtor:" << counter << endl;

copy(begin(o.payload), end(o.payload), back_inserter(payload));

}

private:

static int counter;

static mt19937 rand;

vector<int> payload;

};

int _tmain(int argc, _TCHAR* argv[])

{

_CrtSetReportMode(_CRT_WARN, _CRTDBG_MODE_FILE);

_CrtSetReportFile(_CRT_WARN, _CRTDBG_FILE_STDOUT);

_CrtMemState mem_start, mem_end, mem_diff;

_CrtMemCheckpoint(&mem_start);

CCtorCounter in;

auto start_time(steady_clock::now());

auto o(Foo(in));

auto end_time(steady_clock::now());

       cout << "Execution time: " <<
              duration<double, milli>(end_time - start_time).count()
                                                      << " ms" << endl;

_CrtMemCheckpoint(&mem_end);

if (_CrtMemDifference(&mem_diff, &mem_start, &mem_end))

_CrtMemDumpStatistics(&mem_diff);

return 0;

}

The result (Debug Build):

We can eliminate one copy by passing the input parameter as const reference:

CCtorCounter Foo(const CCtorCounter &in)

{

CCtorCounter x;

return x;

}

The result (Debug Build):

To avoid copying a temporary object – an object that serves as a return value from a function, one can create the object in the caller context and pass it as an out parameter, or better, one can use a smart pointer (shared or unique) which will result a heap allocation. However, this kind of code is harder to write and maintain and heap allocation is less effective compared to stack, especially in a heavy concurrent application.

C++ 11 provides a way of using stack based passing by value instance semantics, without the overhead of deep copy of temporary objects. In the sample above, we know that x is a temporary object. We also know that after the call returns from Foo, this object will be destroyed. The compiler generates code that copies the guts of x and then destroys x! Wouldn’t it be better if we can take the guts of x and put it in o:

auto o(Foo(in));

To be able to do so, we need a way to distinct passing temporary objects vs. non-temporary objects. This is the main reason to the addition of a new reference type to the language, the R-Value reference (&&). I will explain all the details later, but for now, let’s create another constructor, a move constructor which takes a temporary object and moves its guts to the new object:

CCtorCounter(const CCtorCounter &&o)

{

cout << "Move Ctor" << endl;

payload = std::move(o.payload);

}

The result:

As you can see, we have eliminated all the calls to the copy constructor.

This is a very simple example and in fact, compiling the same code in release mode would had resulted the same performance, even without the new move-constructor, since the compiler can use the return-value-optimization and VS C++ compiler uses it. However, there are many complex cases which move semantics provide huge performance gain, such is the case of manipulating strings, or using algorithm that copies elements in STL containers.

L-Value and R-Value References

L-Values & R-Values got their names from the left side and the right side of the assignment expression. This is the wrong way to think about them. The better way to distinguish between the two is to understand their lifetime and memory persistence. An L-Value is an expression with memory persistence while an R-Value is a temporary expression.

Before C++ 11, there was no way to refer to an R-Value. Trying to do so yielded an L-Value. Any assignment, or passing an argument by value or even by reference (single & - now called an L-Value reference) causes the expression to be copied (persisted in memory) and become an L-Value, This makes sense since you need the temporary expression to be valid longer than the compiler needs it. In C++ 98/03 it is valid to take the address of a parameter, even if the parameter is a reference (L-Value reference) or a const reference. Actually even with R-Value reference parameter in C++ 11, the compiler treats the parameter as an L-Value in the body of the function, mainly because you can refer to it in many places and R-Value references tend to be destroyed.

As you can see, keeping an R-Value as an R-Value is tricky, in many cases it will become an L-Value.

The following code snippet shows how the compiler treats R-Values and L-Values:

void print_reference(const string& str)

{

cout << "const string& :" << str << endl;

}

void print_reference(string&& str)

{

cout << "string&& :" << str << endl;

}

void rvalue_references_overload()

{

string s("s: alon");

print_reference(string("alon"));

print_reference(s);

}

The result is:

The compiler knows which method to call. Now that we know how to distinguish between temporary (R-Value) and non-temporary (L-Value), we can write a move constructor and move assignment operator. Let’s create our own simple and naïve string class and implement both:

class my_string

{

private:

char* _string;

int _length;

public:

explicit my_string(const char* str)

{

if (str == nullptr)

{

_length = 0;

_string = nullptr;

return;

}

_length = strlen(str) + 1;

_string = new char[_length];

strcpy_s(_string, _length, str);

}

my_string(const my_string& other)

{

_length = other._length;

if (other._string == nullptr)

{

_string = nullptr;

return;

}

_string = new char[_length];

strcpy_s(_string, _length, other._string);

}

my_string& operator=(const my_string& other)

{

if (this == &other)

return *this;

delete[] _string;

_string = nullptr;

_length = other._length;

if (other._string != nullptr)

{

_string = new char[_length];

strcpy_s(_string, _length, other._string);

}

~my_string()

{

delete[] _string;

_string = nullptr;

_length = 0;

}

//move functions:

my_string(my_string&& other)

{

*this = std::move(other); //std::move preserves &&

//semantics so operator=(&&) is called

}

my_string& operator=(my_string&& other)

{

if (this == &other)

return *this;//handle self-assignment

_string = other._string;

_length = other._length;

other._string = nullptr;

other._length = 0;

return *this;

}

};

my_string is a simple string class implementation. There are two new methods, the move constructor and the move assignment operator. The move constructor gets the temporary (R-Value reference) and builds the object using the assignment operator. It uses the std::move to force this call. I will talk about std::move later. The move assignment operator first checks if we are assigning from the same instance, a case that you should handle also with the regular assignment operator. When calling from the move constructor this will never be the case. Now the move assignment operator copies the internals of the R-Value object. The last step is to make sure that the temporary object destructor will not free the stolen values, simply by nullifying them. That is it; our my_string class can be used in a very efficient way when passing temporaries by value.

The std::move function

template< class T >

typename std::remove_reference<T>::type&& move( T&& t );

std::move is a template function that converts an L-Value into an R-Value. The std::remove_reference<T>::type is a tricky function that removes any reference from T if exists. It does it by using three overloads; all of them use a typedef to create the non-reference type:

template< class T > struct remove_reference {typedef T type;};

template< class T > struct remove_reference<T&> {typedef T type;};

template< class T > struct remove_reference<T&&> {typedef T type;};

So the line typename std::remove_reference<T>::type&& defines an R-Value return type, no matter if the original type was a value, an L-Value reference or an R-Value reference. Move takes an argument of an R-Value reference; however, it is ok to pass a value, or an L-Value reference as an R-Value reference, because R-Value reference preserves the original type and in any case, in the body of the method an R-Value reference becomes an L-Value reference. The body of the function is just a simple casting to the return type, which makes the object a temporary:

template<class T> inline

typename remove_reference<T>::type&& move(T&& t)

{

return ((typename remove_reference<T>::type &&)t);

}

With this knowledge, when we look at the implementation of the move constructor:

*this = std::move(other);

We understand that we assign an R-Value reference, hence invoking the move assignment operator. You might think: “The original parameter for the move constructor is an R-Value reference, why do we need to cast it again to be an R-Value by the std::move function?” If you recall I have mentioned that the compiler treats R-Values inside the body of the method as L-Values, hence we need to force it to be an R-Value again. Also sometimes, you may want to convert an L-Value explicitly to become an R-Value. This is what the uniqe_ptr<T> class does.

Perfect Forwarding

Another interesting feature that came from the introduction of R-Value references is the ability to pass a parameter between functions without losing its type. As I showed you in this post, the compiler converts an R-Value reference to become an L-Value reference in the body of the function. This means that if you use an intermediate function, you may lose the performance gain of the move semantics because the R-Value reference will be converted to an L-Value one. Perfect forwarding forces the compiler to keep the original type of the object, be it a value, an L-Value reference, an R-Value reference or any combination of those with the const qualifier. It is achieved by using a set of reference collapsing rules, to be discussed soon.

To pass a parameter with a perfect forwarding, use the std::forward<T> function:

template< class T >

T&& forward( typename std::remove_reference<T>::type& t );

template< class T >

T&& forward( typename std::remove_reference<T>::type&& t );

The function has two overloads and they are somewhat similar to std::move. When you use it, you must provide the template parameter type.

For Example:

template<typename T>

class Target

{

public:

void Action(typename remove_reference<T>::type &) { cout << "Action(T&)" << endl; };

void Action(typename remove_reference<T>::type &&) { cout << "Action(T&&)" << endl; };

};

template <typename T>

void old_forward(T& value)

{

cout << "old_forward(T& value) ==> ";

Target<T> target;

target.Action(value);

}

template <typename T>

void wrong_new_forward(T&& value)

{

cout << "new_forward(T&& value) ==> ";

Target<T> target;

target.Action(value);

}

template <typename T>

void new_forward(T&& value)

{

cout << "new_forward(T&& value) ==> ";

Target<T> target;

target.Action(std::forward<T>(value));

}

void rvalue_references_forward()

{

string s("Alon");

cout << "old forward:" << endl;

cout << "------------" << endl;

cout << "string s(\"Alon\"); ==> ";

old_forward(s);

cout << "old_forward(string(\"Alon\")) ==> ";

old_forward(string("Alon"));

cout << endl;

cout << "wrong new forward - not a perfect forwarding:" << endl;

cout << "---------------------------------------------" << endl;

cout << "string s(\"Alon\"); ==> ";

wrong_new_forward(s);

cout << "new_forward(string(\"Alon\")) ==> ";

wrong_new_forward(string("Alon"));

cout << endl;

cout << "new perfect forwarding:" << endl;

cout << "-----------------------" << endl;

cout << "string s(\"Alon\"); ==> ";

new_forward(s);

cout << "new_forward(string(\"Alon\")) ==> ";

new_forward(string("Alon"));

}

The Target class has two overloaded methods. The first takes an L-Value reference and the second takes an R-Value reference. To be sure that they are defined to take the correct reference type I am using the type_trait remove_reference<T>::type. To show the perfect forwarding, I have created three intermediate functions. The first old_forward takes the parameter by L-Value and passes it to one of the Target’s overloaded functions. The second takes the parameter as an R-Value reference, but it passes it without the use of the std::forward method, hence revert to the old L-Value behavior. The last one is the correct implementation; it takes the value as an R-Value reference and uses the std::forward to preserve the original reference type.

The result:

The implementation of std:forward is:

template<class T> inline

T&& forward(typename remove_reference<T>::type& t)

{ // forward an lvalue

return (static_cast<T&&>(t));

}

template<class T> inline

T&& forward(typename remove_reference<T>::type&& t)

{ // forward anything

static_assert(!is_lvalue_reference<T>::value, "bad forward call");

return (static_cast<T&&>(t));

}

As you can see, it is quite similar to std::move, but you are the one providing the template type parameter.

What these functions do is casting to an R-Value reference. Since R-Value reference preserves the reference type, the forward passes the same type of T, the template parameter, which in a template intermediate function is usually the input parameter type.

To understand why template functions that take R-Value reference can be suitable for both L-Value references and R-Value references bind, we need to understand the reference collapsing rules. Prior to C++ 11, it was forbidden to use a syntax such as this: void Foo(int & & x). Now it is legal. When the compiler sees many ampersands, it uses these rules to decide whether the result is a single ampersand (L-Value reference) or double ampersand (R-Value reference):

T & & è T&

T& && è T&

T&& & è T&

T&& && è T&&

For template functions that take an R-Value reference, there are special parameter deduction rules:

template <typename T>

void new_forward(T&& value)

When T is called with an L-Value reference, T holds a single ampersand and according to the rules above, three ampersands become one, hence the function takes an L-Value reference: (T&& &value) è (T &value)
When T is called with an R-Value reference, T holds two ampersands and according to the rules above, four ampersands become two, hence the function takes an R-Value reference: (T&& &&value) è (T&& value)

With this knowledge in mind you should use perfect forwarding whenever you create a mediator function to preserve the original parameter type.

R-Value References and STL

In Visual Studio 2010 and in Visual Studio 2012 Microsoft has rewritten STL to support R-Value references, the move semantics and perfect forwarding. Containers such as vector use move semantics to improve performance. STL code will call your move constructor or assignment operator if you define one. Some algorithm such as std::swap takes advantages of the std::move function:

template<class T> inline

void swap(T& left, T& right)

{ // exchange values stored at left and right

T tmp = move(left);

left = move(right);

right = move(tmp);

}

The new unique_ptr<T> is a non-copy-able move semantics type that guarantees that there will be only one smart pointer that points to the instance, because it moves the real pointer in any assignment, function call or function return. This makes the old auto_ptr<T> obsolete.

Summary

Yes, you have reached the end of this post and you have survived . You can read more about R-Value, Move, and Perfect Forwarding here , here, and here.

Introduction to C++ 11 Series – Part 8, Lambda Expression or Functions

Alon Fliess — Mon, 01 Apr 2013 20:45:48 GMT

One of the most important features of C++ 11 is the addition of Lambda, an inline function mechanism (and a closure).

Motivation

The first motivation is to make this a valid C++ code:

[](){}();

There are many reasons to use lambda and functional programing; for example, STL algorithms use function or functor objects. STL <functional> provides a set of functors such as plus, minus, less, equal_to, etc. Most of these functors are binary functions, i.e. they take two parameters. To use a predefined binary functor in an STL algorithm, you need to bind one of the functor arguments to a predefined value. For example to find the first element whose value is greater than 10, you can write this code:

#include "stdafx.h"

#include <algorithm>

#include <functional>

#include <iostream>

#include <vector>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

vector<int> v;

for (int i = 0; i < 20; i+=3)

v.push_back(i);

auto result = find_if(begin(v), end(v),
bind2nd(greater<int>(), 10));

cout << *result << endl;

return 0;

}

TR1, now part of C++ 11, added the new bind method and the use of placeholders:

(I might write a future post about functional programing with TR1 (bind, placeholders, mem_fn))

#include "stdafx.h"

#include <algorithm>

#include <functional>

#include <iostream>

#include <vector>

using namespace std;

using namespace std::placeholders;

int _tmain(int argc, _TCHAR* argv[])

{

vector<int> v;

for (int i = 0; i < 20; i+=3)

v.push_back(i);

//auto result = find_if(begin(v), end(v), bind2nd(greater<int>(), 10));

auto result = find_if(begin(v), end(v), bind(greater<int>(), _1, 10));

cout << *result << endl;

return 0;

}

However, using a Lambda function makes it much simpler; you actually do not need those functors anymore:

#include "stdafx.h"

#include <algorithm>

//#include <functional>

#include <iostream>

#include <vector>

using namespace std;

//using namespace std::placeholders;

int _tmain(int argc, _TCHAR* argv[])

{

vector<int> v;

for (int i = 0; i < 20; i+=3)

v.push_back(i);

//auto result = find_if(begin(v), end(v), bind2nd(greater<int>(), 10));

//auto result = find_if(begin(v), end(v), bind(greater<int>(), _1, 10));

auto result = find_if(begin(v), end(v),
[](int value) { return value > 10; });

cout << *result << endl;

return 0;

}

So, what is a Lambda Function?

A construct that combines the benefits of function pointers and function objects

It’s an inline method (a closure)

With lambda you can:

Easily use any STL mechanism that needs a functor
Create array of functions
Use functional programming paradigm

Very useful for concurrent programming

Write shorter and readable code

Capture Variables

One of the main differences of using Lambda vs. using predefined functors is the ability of the lambda function to access, or capture, local variables of the enclosing function.

For example:

int v = 7, r = 8;

auto l = [v,&r](int i)

{

cout << v << ' ' << r << ' ' << i << endl;

};

l(9);

The result is:

The variable v is captured by value, i.e. the lambda uses a const copy of the value. The variable r is captured by reference, i.e. the lambda function refers to the same outer r variable memory location.

For example, this is a dangerous use of lambda:

function<void (int)> Foo()

{

int v = 7, r = 8;

auto l = [v,&r](int i)

{

cout << v << ' ' << r << ' ' << i << endl;

};

return l;

}

int _tmain(int argc, _TCHAR* argv[])

{

auto func = Foo();

func(9);

return 0;

}

The result is:

In this case the r captured variable refers to a stack location that no longer exists.

Using the undocumented /d1reportAllClassLayout compiler switch, we can see that the compiler creates this class:

class <lambda0> size(16):

+---

0 | v

| <alignment member> (size=4)

8 | r

+---

The capturing syntax is:

Return Type:

Lambda can return nothing (void), or like any other function, it can return any value. If there is more than one return location in the lambda function body, you need to specify the return type using the trailing-return-type syntax:

Exceptions:

Like any other function, you can throw an exception from the lambda. Although exception specifications are deprecated, some compilers and tools still test exception correctness. You can also use exception specification syntax: []() throw () {}

Capture by value variable are constants

As we have seen, capture by value makes the captured variable into a const. This enables better code optimization. However sometime we want to change the captured copy in the lambda body:

int times = 10;

auto func = [times](const string &s)

{

while (times-- > 0)

cout << s << endl;

};

func("Alon");

This yields a compiler error:

error C3491: 'times': a by-value capture cannot be modified in a non-mutable lambda

To solve this, we can tell the compiler not to capture the variable as a const:

int times = 10;

auto func = [times](const string &s) mutable

{

while (times-- > 0)

cout << s << endl;

};

func("Alon");

Summary

Now you understand that [](){}(); is a call to a lambda function that captures nothing, takes nothing, returns void and does nothing.

Lambda is a very powerful mechanism. Using lambdas, your code will never look the same!