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