Блог пользователя mukel

Автор mukel, 11 лет назад, По-английски

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() ...

  • Проголосовать: нравится
  • +244
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Very helpful tutorial. Thanks!

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

I think here typo mistake .

int mid = (lo + hi) - 1;

must be

int mid = (lo + hi) / 2;
»
11 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      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.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

            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.

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

On VS12 doesn't work this feature

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

Maybe there's some project settings?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for this!

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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??

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    #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 !

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      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 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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 лет назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +32 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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
    }
  }
}();
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;
}
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!