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() ...
Very helpful tutorial. Thanks!
Btw. notice that C++11 is allowed at IOI 2014 ! :)
Also 2014 ACM-ICPC World Finals will switch the default C++ to gnu++0x (C++0x plus GNU extensions)
I think here typo mistake .
must be
or maybe he wanna write : int mid = (lo + hi)>>1;
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.
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.
No, as you said yourself,
long
is guaranteed to hold only numbers from - 231 to 231 - 1. On 64-bit Windowslong
indeed is still 32 bits. When you want 64 bits, uselong long
or[u]int64_t
if it is defined.I mean 64-bit compilers, not 64-bit OS, and even in that case there is no guarantee that "long" has 64-bits.
Yes, I also meant that
long
is still 32 bits in this very case.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.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.
On VS12 doesn't work this feature
Maybe there's some project settings?
Sadly, VS is behind GNU and Clang in terms of C++11 support, but VS 2013 should support initializer lists, more info here.
Thanks for this nice post! Could you suggest any good books on C++11, or tutorials on inheritance of STL's container/iterator,etc?
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.htmlThanks for this!
By the way, is there a better recommendation available now? The FAQ seems to be missing some chunks.
but what if we want to traverse from l to r,where l>r. then what can we do?
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??
http://channel9.msdn.com/Events/GoingNative/2013/An-Effective-Cpp11-14-Sampler
An Effective C++11/14 Sampler(Scott Meyers)
can u elaborate on how
auto matrix = array< array<double, 10>, 10>();
is different fromdouble matrix[10][10];
just a simple example !
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 linecout << 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.
replace
unsigned int N
withsize_t N
Thanks. That worked. Any explanations that i can read up on?
Explanation is very simple,
std::array
is defined as:And on 64-bit systems
size_t
!=unsigned int
According to what I know, array<> is made for us to use that
double matrix[10][10];
as an STL, they're the same :pA 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.
You save lots of typing.
Well, you should consider writing python.
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.
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?
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 .
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
you are wrong :)
page 757 of current standard iso : http://isocpp.org/files/papers/N3797.pdf
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
Your post is good, but I would like to give some suggestions.
First,
why you ever need anI meant, sometimes it would be shorter withoutauto
in the declaration of a variable?auto
.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.
Third,
lower_bound
should not be used like this, when there is a goodpartition_point
:May fast AC be with you.
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
???
.by the way, there is another C++11 feature in your code: no spaces between angle brackets
yeah. that stupid error
require expression after >> operator
Oops. My comment did not match my intent. I would write
auto
instead of???
, too. I meant you need not to writeas what OP did.
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.
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:
where reference is what operator * returns.
My favorite use of lambdas is early return:
I call it "goto" :). Of course many people consider goto as really bad, but for this particular case I think it's "the way".
In your samples you capture everything by reference in lambdas (i.e. [&])
That's a bad practice. Capture only things you need
Another important thing in c++11 you missed is friendly brackets in templates.