Remember that last post about new C++ features enabled in TopCoder's servers? These new features (and far more) are also available in Codeforces if you choose GNU c++0x 4 as language (instead of plain GNU c++) and in those contests in which you can compile locally by just using a recent g++ version with the -std=c++0x modifier.
But there is more about the improvements in C++. Have I ever told you about how much I like std::pair? Let me introduce pair's younger brother, std::tuple:
Why and how were tuples added?
One flaw about std::pair was how it stores only two values. Which made it of limited use. There were plenty of times during contests where I had to use nested pairs. Ugly code like queue<pair<int, pair<int,int> > >. The optimal would be to have something that behaves like std::pair, but allows more than two values. A solution like a std::triple would have been a poor solution though, because it would still be limited. But of course, templates with variable argument number would be crazy, right man?
Enter variadic templates, a c++11 killer feature, in my opinion. Templates with variable number of arguments. They allow these tuples and plenty of other things through recursion. It is amazing the sort of things c++ will be able to do at compile time with these. Imagine a strongly typed printf-like function, for example. The good news is that these templates work in TopCoder's ultra old g++ 4.4, and CodeForces' compiler is even more recent. So they are fair game. While C++, the language, adds variadic templates, the STL, the standard template library, is the one responsible of adding tuples.
Let us get to use them
Just add the include: #include <tuple>
Now we basically use std::tuple the same way we used std::pair in the past, except that we can now use more than two arguments. Let us start with an easy one, imagine that you are running a BFS (Breadth-first-search) on a graph that is described by three dimensions, so imagine that it is a 3D grid with x, y and z. (So typical).
queue<tuple<int,int,int> > Q;
bool visited[X][Y][Z];
memset(visited, 0, sizeof(visited));
visited[0][0][0] = true;
Q.push( make_tuple(0,0,0) );
while (! Q.empty()) {
tuple<int,int,int> node = Q.front(); Q.pop();
int x = get<0>(node), y = get<1>(node), z = get<2>(node);
//... etc
// augment edges from node (x,y,z)?
}
The first bad news is that things like get<index> are needed to access the tuples. They are a bit verbose for my taste. Also note that although they use integers as a matter of indexing, they have to be constants. (Although if you really need variable indexes, you probably need a vector and not a tuple). However, there was possibly no choice in this case, because in order to implement variadic templates, you need some recursion, which means that indexing is likely needed...
But let us go on. Although the get>0> seems heavy, compare with the alternatives. Coding a whole struct? Using a nested pair like I did in one of the first paragraphs? So verbosity could be worse.
The reality is that tuples (or pairs) are not meant to be a replacement of structs or classes, but just something that will help you in some peculiar cases. Like in the post about std::pair, let us deal with a comparison problem: John wants to pick between two strings. He prefers strings that have a larger number of even letters (b,d,f,...). If two strings have the same number of even letters, he prefers the one with a smaller length, if two strings have the same number of even letters and the same length, he prefers the lexicographically smallest one. As simple as:
int even(const string & x)
{
// count the number of even characters
int c = 0;
for (int i=0; i<x.size(); i++) {
c += ( x[i] % 2 == 0);
}
return c;
}
// Given a and b, picks the string that John likes the most:
string johnLikesString(string a, string b)
{
auto q = std::min( make_tuple(-even(a), a.length(), a),
make_tuple(-even(b), b.length(), b) );
return get<2>(q);
}
Like with std::pair, tuples can be compared using the common relational operators (They implement lexicographical comparison for the values in the order in which they are in the tuple, so element 0 is compared first, if both are equal, element 1 is compared and so and so). Which means that we can use std::min() to pick the smaller of two tuples. Since we wanted the string with the larger number of even characters to be picked, we call -even(...) instead of just even(). At the end, the tuple that is picked by std::min will contain John's preferred string as element #2.
Thanks to relational operators like `<` , `>` , `<=` , `>=`, being implemented automatically for our tuples, we can sort tuples using std::sort. We can also use tuples in std::set, or as keys in std::map.
Also note the cameo by the auto keyword. A great feature. In this case, we don't even need to know the type of the q variable in order to use it. After some inspection, we can see that its type is: tuple<int,int,string>.
std::tie
std::tie is an interesting thing, it does something similar to std::make_tuple, but it uses "lvalue references" instead of creating copies of the values. For simple types, like ints it is not important. Big deal, you are creating a copy of number 5 in memory. But what if you want to compare data structures that could be sort of big? Like in the previous example, what if the strings could be 10000000 characters long? Creating new copies of the strings could be too expensive, so expensive that you reach a memory limit in a problem. But it is not only memory, creating copies of objects takes time.
string johnLikesString(string a, string b) //using by value-arguments sorts of makes
// the following optimization a bit worthless,
// I know.
{
// tie uses references, but we can't use a reference to a temporary
// object. So we couldn't use a.length() directly inside of std::tie
int aeven = -even(a), alen = a.length();
int beven = -even(b), blen = b.length();
// Comparing without creating a copy of the strings:
if (std::tie(aeven,alen, a) < std::tie(beven, blen, b) ) {
return a;
} else {
return b;
}
}
Pitfalls and a bonus
Nothing is perfect, specially not c++, not even c++11. Actually, c++11 follows the long tradition that coding in c++ is a lot like operating riding a rocket. A rocket is a fast method of transportation and it is the product of plenty of work and research. But god, if you ride it, it will explode in your face eventually.
The usual std::pair issues stand, although they seem to behave a bit better. But for example, the following line of code will make your compiler throw hundreds of syntax errors at you:
tuple<int,int,string> a = make_tuple(4,5,"ssss");Well, of course, the issue is that "sss" is a const char*, did you expect the tuple to know that it can cast const char* to std::string? hahaha. And since the error occurs in the third step of the tuple recursion, your compiler will be very confused. There are ways to fix this.
// make the typeo f the argument explicit:
tuple<int,int,string> a = make_tuple(4,5, string("sss") );
// use make_tuple with explicit types:
tuple<int,int,string> a = make_tuple<int,int,string>(4,5, "sss" );
// use make_tuple with explicit types and abuse auto:
auto a = make_tuple<int,int,string>(4,5, "sss" );
// Also abuse the new { } initializer:
auto a = tuple<int,int,string>{4,5, "sss" };
// Now that I think about it, the whole thing was very silly:
tuple<int,int,string> a(4,5,"sss");
But don't be sad. Here is an eastern egg for you. Swapping the values of two variables, python style:
int x = 5, y = 7;
//swap x and y:
tie(x,y) = make_tuple(y,x);
// All possible because tie uses references and make_tuple creates copies
int z = 6;
//cycle x,y,z = (y,z,x)
tie(x,y,z) = make_tuple(y,z,x);
//Greatest common divisor, the way Euclid intended:
int gcd(int a, int b)
{
while (b != 0) {
tie(a,b) = make_tuple(b , a%b);
}
return a;
}
0 comments:
Post a Comment