mukel's blog

By mukel, 10 years ago, In English

Updated: 30 December 2013 3:27 CEST (Added a brief introduction to Lambda Functions).

The new C++ standard, also known as C++11 and also as C++0x is here, with some sugars for programming contest. I'll update this thread soon with new contents (and better structure). You can use C++11 on Topcoder, Codeforces, HackerRank ... This thread is based on my own experience, so you don't need to dig on the whole C++11 specification to find some useful feature you can use in programming contests.

The "auto" keyword:

Type inference is included in many modern programming languages, and C++ is not behind, the "auto" keyword works like "var" in C#, it only tells the compiler to infer the type for us: So,

map< string, pair< int, int > > somyLongTypeName = map< string, pair< int, int > >();

Can be shortened to, with no impact on speed, since the type is inferred at compile time:

auto longTypeNamesAreHistory = map< string, pair< int, int > >();

Of course that a typedef could do the same, but using auto is faster (to type).

Personally I think that one of the best use of auto is when dealing with iterators, for example:

for (map< string, pair< int, int > >::iterator it = m.begin(); it != m.end(); ++it)
{
    /* do something with it */
}

Becomes:

for (auto it = m.begin(); it != m.end(); ++it)
{
    /* do something with it */
}

Which is a great improvement, easier to write and read, and to maintain (imagine we change one of the template arguments of m).

Initializer lists:

This is also a nice addition, and makes easier to initialize stl containers, let's a basic example:

vector< int > primeDigits = {2, 3, 5, 7};
vector< string > days = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
pair< int, int > p = {1, 2}; // equivalent to make_pair(1, 2)

Maps also can be initialized:

map< int, string > numeral = {
    {0, "zero"},
    {1, "one"},
    {2, "two"},
    {3, "three"},   
    {4, "four"},
    {5, "five"},
    {6, "six"},
    {7, "seven"},
    {8, "eight"},
    {9, "nine"}
};

Range based for loops:

C++11 also introduced a new way to iterate thourgh STL containers:

The old way (using auto for simplicity):

for (auto it = container.begin(); it != container.end(); ++it)
{
    /* do something with it */
}

Becomes:

for (auto x : container)
{
    cout << x << endl;
}

We can even modify the elements (note the &):

vector< int > numbers = {2, 3, 5, 7};
for (auto& x : numbers)
    x *= 2;

for (auto x : numbers)
    cout << x << endl;

The above should multiply by 2 all the elements of container.

But we can go even further and pythonize the for loops as follows:

First let's define a number_iterator and number_range:

template<typename T>
struct number_iterator : std::iterator<random_access_iterator_tag, T>{
	T v;
	number_iterator(T _v) : v(_v) {}
	operator T&(){return v;}
	T operator *() const {return v;}
};
template <typename T>
struct number_range {
	T b,e;
	number_range(T b, T e):b(b),e(e){}
	number_iterator<T> begin(){return b;}
	number_iterator<T> end(){return e;}
};
/* make_pair like functions for our range type */
template<typename T> number_range<T> range(T e) {return number_range<T>(0, e);}

// inclusive range
template<typename T> number_range<T> range(T b, T e) {return number_range<T>(b, e);}

Now we can do something like:

for (auto i: range(1000))
    sum += i;

or

for (auto i: range(10, 20))
    cout << i << endl;

Nothing to worry about speed, is exactly the same when compiled with -O2 (tested on g++ 4.8), which is logical since all the operations of the iterators are delegated to underlying type T (int or long long). Until now, my experience tell me that the new range for loops are easier to write/read without any speed penalty. Note that this is not so practical since we need to implement our own iterator and range classes, but if we have a pre-written template, the code becomes very clean and readable.

Another common example, (no more -> for (int i = 0; i < G[u].size(); ++i)... :

void dfs(int u, int from) {
    for (auto v: G[u])
        if (v != from)
            dfs(v);
}

But we can go even further (with the help of lambdas) and implement binary search using the well known lower_bound and upper_bound functions:

Let's implement a simple binary search to find the square root:

int findSqrt(int n) {
    int lo = 0, hi = n;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (mid * mid <= n)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return lo - 1;
}

Using our number_iterator and lower_bound the above code becomes:

int findSqrt(int n) {
	int lb = lower_bound(number_iterator<int>(0), number_iterator<int>(n), 0,
		[&] (int value, int /* ignored */ ) {
			return value * value <= n;
		}
	);
	return lb - 1;
}

As you can see, no need to cast (or de-reference) the resulting iterator, we can also use long long (not doubles obviously).

New array type:

C++11 brings a new array type which offer complete integration with the STL (not too useful IMHO), the syntax is verbose for multidimensional arrays, but there is no penalty on speed:

auto arr = array< int, 10 >{5, 8, 1, 9, 0, 3, 4, 2, 7, 6}; // array of 10 ints

sort(arr.begin(), arr.end()); // yes, same as sort(arr, arr + n) for normal arrays

arr[0] += arr[5]; // normal [] indexing

for (auto i: range(arr.size()))
{
    /* do something */
}

auto matrix = array< array<double, 10>, 10>(); // 10 by 10 matrix (not the same as double[10][10])

Initialization can be somehow particular, please refer to this for further details.

Lambda functions:

Before the new standard, C++ used functors, which are classes that simulates functions, still functions were not 1st class constructs. The new standard introduced lambda functions (still not 1st class citizens), and make the use of functions more pleasant than before. Let's see a trivial example:

Generates a permutation sorted by heights[].

auto heights = vector< int >{ ...some values here... };

auto order = vector< int >(heights.size());

for (int i: range(heights.size()))
    order[i] = i;

sort(order.begin(), order.end(),
    [&] (const int& a, const& int b) -> bool {
        return heights[a] < heights[b];
    }
);

See also the binary search implemented using lower_bound in the "Range based for loops" section.

The above is a quite common use case, but one may wonder why use a lambda instead of a simple static function, the reason is quite simple, the cool part is that lambda functions can capture other variables (by value or by reference, is even possible to specify which variables to capture), allowing us to access to all visible variables in the scope. The old style functions can only access global variables. The compiler can infer the return type in most cases. My advice is to avoid recursive lambda functions. Lambdas are a huge advance, but definetely not the same as in functional languages were functions are real 1st class constructs.

C++

for_each(v.begin(), v.end(),
    [&] (int x) {
        cout << x << endl;
    }
)

Scala

v foreach println

TODO: Better/more examples

Move semantics:

What is it and how it works?

C++03 and previous standards had a serious penalty when returning non-pointer values, eg. vector< int >, map< string, int >, string?... since the whole value should be deep-copied by value, move semantics is an optimization that avoid the copy of the whole structure and integrates flawlessly to existing code. To explain better how it works (without entering in technical details) let's try with a concrete example, let's assume we are returning a vector< int > , instead of copy the vector when returning, it just "moves" (with the help of some additional construct) what we are returning, the "move" is achieved by copying only the necesary internal "data" of the vector, which consist in a pointer and a integer (size), that way the whole data is NOT copied, only the necessary to have. Note that "move" is different from copy, it just "moves" cleverly what is really important, resulting in a considerable boost. So you can safely return vectors, maps, strings with a no performance overhead in a more natural way that using pointers which can be harder to code, debug ...

Soon, benchmarks using the new move semantics feature...

More is coming, lambdas, benchmarks, regex, new pseudo-random number generators, bye bye rand() ...

  • Vote: I like it
  • +244
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Very helpful tutorial. Thanks!

Btw. notice that C++11 is allowed at IOI 2014 ! :)

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Also 2014 ACM-ICPC World Finals will switch the default C++ to gnu++0x (C++0x plus GNU extensions)

»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I think here typo mistake .

int mid = (lo + hi) - 1;

must be

int mid = (lo + hi) / 2;
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Also, we can use "long" instead of "long long" on 64 bit systems. As far as I know, it works on topcoder but not on codechef. Haven't tried it on codeforces though.

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Codeforces uses MinGW 4.7.2 32 bits, so "long" is only 32-bit, on 64-bit compilers "long" should have 64-bits to fit register (word) size (as in TopCoder). In fact the number of bits for each type is implementation dependent, int should have at least 16 bits, long should have at least 32 bits, the standard only provides lower bounds on the number of bits. Resuming, on Codeforces long is exactly the same as int, use long long for 64 bits.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      on 64-bit systems "long" should have 64-bits to fit register (word) size

      No, as you said yourself, long is guaranteed to hold only numbers from  - 231 to 231 - 1. On 64-bit Windows long indeed is still 32 bits. When you want 64 bits, use long long or [u]int64_t if it is defined.

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I mean 64-bit compilers, not 64-bit OS, and even in that case there is no guarantee that "long" has 64-bits.

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Yes, I also meant that long is still 32 bits in this very case.

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Windows takes the design to unify datatype size across 32-bit and 64-bit systems and compilers ( with the main exception of pointer and size_t types) aiming to easy migration of code. While Unix-like system chose the opposite, so only if use 64-bit compiler on 64-bit Linux or OS X you will get a 64-bit long data type. If you want a crossplatform solution either never use long ( use int or long long according to your needs) or use int32_t and int64_t defined in <cinttypes> header, both solution are supported on any C++11 compliant compiler, but the first is supported on gcc before C++11.

          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            Rev. 2   Vote: I like it +8 Vote: I do not like it

            Strictly speaking, int32_t may doesn't exist if compiler doesn't support 32bit types. (e.g it its char size is smth like 10bit)

            Not that it's going to happen on PC.

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

On VS12 doesn't work this feature

std::vector<int> a = {1, 2, 3};

Maybe there's some project settings?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Sadly, VS is behind GNU and Clang in terms of C++11 support, but VS 2013 should support initializer lists, more info here.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this nice post! Could you suggest any good books on C++11, or tutorials on inheritance of STL's container/iterator,etc?

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice tutorial, I haven't seen the range trick before. BTW, Bjarne Stroustrup's C++11 FAQ is also very helpful: http://www.stroustrup.com/C++11FAQ.html

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for this!

    By the way, is there a better recommendation available now? The FAQ seems to be missing some chunks.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but what if we want to traverse from l to r,where l>r. then what can we do?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      one way is, we can add this line before return statement in range(b,e) :

      if(b>e)return number_range(-b,-e); we can use our variable by adding minus before it.

      like :

      for(int i : range(1000,0)) cout<<arr[-i]<<" "; cout<<endl;

      will print array in reverse order. i know we can do like this,

      for(int i : range(0,1000)) cout<<arr[999-i]<<" "; cout<<endl;

      but, what if we really want reverse range(), then we can use above one !!

      is there any other way??

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can u elaborate on how auto matrix = array< array<double, 10>, 10>(); is different from double matrix[10][10];

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    #include<array>
    #include<iostream>
    using namespace std;
    
    template<class T, unsigned int N>
    ostream& operator<<(ostream& os, const array<T, N>& arr){
    	for (int i = 0; i < N; ++i)
    		os << arr[i] << (i < N - 1 ? "," : "");
    	os << endl;
    	return os;
    }
    
    int main(){
    	array<array<int, 10>, 10> a;
    	for (int i = 0; i < a.size(); ++i) a[i].fill(i);
    	for (int i = 1; i < a.size(); i += 2) a[i].swap(a[i - 1]);
    	cout << a << endl;
    	/* prints
    	1,1,1,1,1,1,1,1,1,1
    	,0,0,0,0,0,0,0,0,0,0
    	,3,3,3,3,3,3,3,3,3,3
    	,2,2,2,2,2,2,2,2,2,2
    	,5,5,5,5,5,5,5,5,5,5
    	,4,4,4,4,4,4,4,4,4,4
    	,7,7,7,7,7,7,7,7,7,7
    	,6,6,6,6,6,6,6,6,6,6
    	,9,9,9,9,9,9,9,9,9,9
    	,8,8,8,8,8,8,8,8,8,8 */
    	return 0;
    }
    

    just a simple example !

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi.

      I was trying to execute the sample code.

      I am getting the following error on clang C++17:

      Invalid operands to binary expression ('std::ostream' (aka 'basic_ostream<char>') and 'array<array<int, 10>, 10>') The error is on the line cout << a << endl;

      I think the overloaded outstream operator will print the array by itself. No need to iterate over elements to print.

      Also, in reference tot he question to which you replied, I am still kind of confused. How are they different?

      Thanks.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        replace unsigned int N with size_t N

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks. That worked. Any explanations that i can read up on?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Explanation is very simple, std::array is defined as:

            template<class T, std::size_t N> struct array;
            

            And on 64-bit systems size_t != unsigned int

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    According to what I know, array<> is made for us to use that double matrix[10][10]; as an STL, they're the same :p

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      A difference means any difference right ? :)

      std::array provides nicer interface to deal with the same type of storage, and thus should be preferred; there's nothing to gain with static arrays over std::array.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        there's nothing to gain with static arrays over std::array.

        You save lots of typing.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, you should consider writing python.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    array< array<> > (multidimensional case) does not guarantee that a contiguous chunk of memory is used as in the classic multidimensional arrays. Since the new array type is not dynamic (the size is a template parameter) the compiler can still reserve a contiguous space.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, how can it be not contiguous? Inner arrays are contiguous and lay contiguously in the outer array because of same guarantee for outer array. I can think only of alignment issues here, but anyway they aren't in random places. Do I miss anything?

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it
      array<array<int, 3>, 4> a;
      a[1][1] = 5;
      ++a[0][4];
      cout << a[1][1] << endl;
      /* (&a[1][1]) == (&a[0][4]) */
      

      prints 6 as expected with normal 2d arrays . because arr[0][4] == *(a + 0*3 + 4) == *(a + 1*3 + 1) == a[1][1] !

      so the memory is absolutely continuous .

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 2   Vote: I like it -16 Vote: I do not like it

        If it works on specific implementation on specific platform in specific point of time, it doesn't mean anything. UB may be on every step. It's C++

        Here, you cant get [4] of a[0] because its stay of 3 elements

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        you are wrong :)

        page 757 of current standard iso : http://isocpp.org/files/papers/N3797.pdf

»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Codeforces offer two options that include some of C++11 but not all, these are MS Visual C++2010 and C++0x. For example : MS Visual C++2010 fails in compilation of STL initializer lists, and C++0x fails in compiling stol() and stoi() functions

»
10 years ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

Your post is good, but I would like to give some suggestions.

First, why you ever need an auto in the declaration of a variable? I meant, sometimes it would be shorter without auto.

map<string, pair<int, int>> itCanBeEvenShorter; /* pure C++98 way on this line */
array<int, 10> arr {5, 8, 1, 9, 0, 3, 4, 2, 7, 6};

Second, your iterator is not quite standard conforming. Read §24.2 [iterator.requirements] of the C++11 specification or this for detail, and Boost's Counting Iterator for a standard-conforming implementation. To make my third point compile on my machine, you need to make your iterator default-constructable.

	number_iterator(T _v = 0) : v(_v) {}

Third, lower_bound should not be used like this, when there is a good partition_point:

int findSqrt(int n) {
	int lb = partition_point(number_iterator<int>(0), number_iterator<int>(n),
		[&] (int value) { return value * value <= n; });
	return lb - 1;
}

May fast AC be with you.

  • »
    »
    10 years ago, # ^ |
    Rev. 3   Vote: I like it +28 Vote: I do not like it

    Example where one may want auto:

    there's a map you have:
    map<that_is<really, long, type>, std::vector<pair<tuple<int, int, int>, string>>> mapa;

    ??? it = mapa.lower_bound(42);

    I'd prefer to write auto instead of ???.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      by the way, there is another C++11 feature in your code: no spaces between angle brackets

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yeah. that stupid error require expression after >> operator

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oops. My comment did not match my intent. I would write auto instead of ???, too. I meant you need not to write

      auto mapa = map<that_is<really, long, type>, std::vector<pair<tuple<int, int, int>, string>>>();
      

      as what OP did.

»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Please, can we update to a newer MS C++ compiler? Visual Studio 14 is around the corner, and Codeforces is still using the compiler from VS 2010, which lacks most of the features and library support of C++ 11. Using GCC is an option of course, but you always have a chance of receiving a compilation error, since compilers are still not 100% compatible.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

About your range example:

I suppose it to work everywhere but want to notice it's not valid random access iterator because being random access iterator means to be forward iterator and ForwardIterator has a requirement:

— if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T

where reference is what operator * returns.

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

My favorite use of lambdas is early return:

[&](){
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (whatever(i, j)) {
        return;
      }
      // more code
    }
  }
}();
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I call it "goto" :). Of course many people consider goto as really bad, but for this particular case I think it's "the way".

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In your samples you capture everything by reference in lambdas (i.e. [&])

That's a bad practice. Capture only things you need

[&by_ref, by_value](int some_args)
{
   if (some_args + by_value == 3)
   {
       ++by_ref;
       return true;
   }
   return false;
}
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another important thing in c++11 you missed is friendly brackets in templates.

map< string, pair< int, int > > somyLongTypeName = map< string, pair< int, int > >(); // C++
map<string, pair<int, int>> somyLongTypeName = map<string, pair<int, int>>(); // C++11, much better!