Skip to main content

C++ Tricks For Competitive Programmers

I see lots of programmers write code like this one:
pair<int, int> p;
vector<int> v;
// ...
p = make_pair(3, 4);
v.push_back(4); v.push_back(5);
while you can just do this:
pair<int, int> p;
vector<int> v;
// ...
p = {3, 4};
v = {4, 5};

1. Assign value by a pair of {} to a container

I see lots of programmers write code like this one:
pair<int, int> p;
// ...
p = make_pair(3, 4);
while you can just do this:
pair<int, int> p;
// ...
p = {3, 4};
even a more complex pair
pair<int, pair<char, long long> > p;
// ...
p = {3, {'a', 8ll}};
What about vector, deque, set and other containers?

vector<int> v;
v = {1, 2, 5, 2};
for (auto i: v)
    cout << i << ' ';
cout << '\n';
// prints "1 2 5 2"


deque<vector<pair<int, int>>> d;
d = {{{3, 4}, {5, 6}}, {{1, 2}, {3, 4}}};
for (auto i: d) {
    for (auto j: i)
        cout << j.first << ' ' << j.second << '\n';
    cout << "-\n";
}
// prints "3 4
//         5 6
//         -
//    1 2
//    3 4
//    -"


set<int> s;
s = {4, 6, 2, 7, 4};
for (auto i: s)
    cout << i << ' ';
cout << '\n';
// prints "2 4 6 7"


list<int> l;
l = {5, 6, 9, 1};
for (auto i: l)
    cout << i << ' ';
cout << '\n';
// prints "5 6 9 1"


array<int, 4> a;
a = {5, 8, 9, 2};
for (auto i: a)
    cout << i << ' ';
cout << '\n';
// prints "5 8 9 2"


tuple<int, int, char> t;
t = {3, 4, 'f'};
cout << get<2>(t) << '\n';
Note that it doesn't work for stack and queue.

2. Name of argument in macros

You can use '#' sign to get exact name of an argument passed to a macro:
#define what_is(x) cerr << #x << " is " << x << endl;
// ...
int a_variable = 376;
what_is(a_variable);
// prints "a_variable is 376"
what_is(a_variable * 2 + 1)
// prints "a_variable * 2 + 1 is 753"

3. Get rid of those includes!

Simply use
#include <bits/stdc++.h>
This library includes many of libraries we do need in contest like algorithm, iostream, vector and many more. Believe me you don't need to include anything else!

4. Hidden function (not really hidden but not used often)

one)
__gcd(value1, value2)
You don't need to code Euclidean Algorithm for a gcd function, from now on we can use. This function returns gcd of two numbers.
e.g. __gcd(18, 27) = 9.
two)
__builtin_ffs(x)
This function returns 1 + least significant 1-bit of x. If x == 0, returns 0. Here x is int, this function with suffix 'l' gets a long argument and with suffix 'll' gets a long long argument.
e.g. __builtin_ffs(10) = 2 because 10 is '...10 1 0' in base 2 and first 1-bit from right is at index 1 (0-based) and function returns 1 + index.
three)
__builtin_clz(x)
This function returns number of leading 0-bits of x which starts from most significant bit position. x is unsigned int and like previous function this function with suffix 'l gets a unsigned long argument and with suffix 'll' gets a unsigned long long argument. If x == 0, returns an undefined value.
e.g. __builtin_clz(16) = 27 because 16 is ' ... 10000'. Number of bits in a unsigned int is 32. so function returns 32 — 5 = 27.
four)
__builtin_ctz(x)
This function returns number of trailing 0-bits of x which starts from least significant bit position. x is unsigned int and like previous function this function with suffix 'l' gets a unsigned long argument and with suffix 'll' gets a unsigned long long argument. If x == 0, returns an undefined value.
e.g. __builtin_ctz(16) = 4 because 16 is '...1 0000 '. Number of trailing 0-bits is 4.
five)
__builtin_popcount(x)
This function returns number of 1-bits of x. x is unsigned int and like previous function this function with suffix 'l' gets a unsigned long argument and with suffix 'll' gets a unsigned long long argument. If x == 0, returns an undefined value.
e.g. __builtin_popcount(14) = 3 because 14 is '... 111 0' and has three 1-bits.
Note: There are other __builtin functions too, but they are not as useful as these ones.
Note: Other functions are not unknown to bring them here but if you are interested to work with them, I suggest this website.

5. Variadic Functions and Macros

We can have a variadic function. I want to write a sum function which gets a number of ints, and returns sum of them. Look at the code below:
int sum() { return 0; }

template<typename... Args>
int sum(int a, Args... args) { return a + sum(args...); }

int main() { cout << sum(5, 7, 2, 2) + sum(3, 4); /* prints "23" */ }
In the code above I used a template. sum(5, 7, 2, 2) becomes 5 + sum(7, 2, 2) then sum(7, 2, 2), itself, becomes 7 + sum(2, 2) and so on... I also declare another sum function which gets 0 arguments and returns 0.
I can even define a any-type sum function:
int sum() { return 0; }

template<typename T, typename... Args>
T sum(T a, Args... args) { return a + sum(args...); }

int main() { cout << sum(5, 7, 2, 2) + sum(3.14, 4.89); /* prints "24.03" */ }
Here, I just changed int to T and added typename T to my template.
In C++14 you can also use auto sum(T a, Args... args) in order to get sum of mixed types. (Thanks to slycelote and Corei13)
We can also use variadic macros:
#define a_macro(args...) sum(args)

int sum() { return 0; }

template<typename T, typename... Args>
auto sum(T a, Args... args) { return a + sum(args...); }

int main() { cout << a_macro(5, 7, 2, 2) + a_macro(3.14, 4.89); /* prints "24.03" */ }
Using these 2, we can have a great debugging function: (thanks to Igorjan94) — Updated!
#include <bits/stdc++.h>

using namespace std;

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
 cerr << *it << " = " << a << endl;
 err(++it, args...);
}

int main() {
 int a = 4, b = 8, c = 9;
 error(a, b, c);
}
Output:
a = 4
b = 8
c = 9
This function helps a lot in debugging.

6. Here is C++0x in CF, why still C++?

Variadic functions also belong to C++11 or C++0x, In this section I want to show you some great features of C++11.
one) Range-based For-loop
Here is a piece of an old code:
set<int> s = {8, 2, 3, 1};
for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
    cout << *it << ' ';
// prints "1 2 3 8"
Trust me, that's a lot of code for that, just use this:
set<int> s = {8, 2, 3, 1};
for (auto it: s)
    cout << it << ' ';
// prints "1 2 3 8"
We can also change the values just change auto with auto &:
vector<int> v = {8, 2, 3, 1};
for (auto &it: v)
    it *= 2;
for (auto it: v)
    cout << it << ' ';
// prints "16 4 6 2"
two) The Power of auto
You don't need to name the type you want to use, C++11 can infer it for you. If you need to loop over iterators of a set<pair<int, pair<int, int> > > from begin to end, you need to type set<pair<int, pair<int, int> > >::iterator for me it's so suffering! just use auto it = s.begin()
also x.begin() and x.end() now are accessible using begin(x) and end(x).
There are more things. I think I said useful features. Maybe I add somethings else to post. If you know anything useful please share with Codeforces community :)
From Ximera's comment:
this code:
for(i = 1; i <= n; i++) {
    for(j = 1; j <= m; j++)
        cout << a[i][j] << " ";
    cout << "\n";
}
is equivalent to this:
for(i = 1; i <= n; i++)
    for(j = 1; j <= m; j++)
        cout << a[i][j] << " \n"[j == m];
And here is the reason: " \n" is a char*, " \n"[0] is ' ' and " \n"[1] is '\n'.
From technetium28's comment:
Usage of tie and emplace_back:
#define mt make_tuple
#define eb emplace_back
typedef tuple<int,int,int> State; // operator< defined

int main(){
  int a,b,c;
  tie(a,b,c) = mt(1,2,3); // assign
  tie(a,b) = mt(b,a); // swap(a,b)

  vector<pair<int,int>> v;
  v.eb(a,b); // shorter and faster than pb(mp(a,b))

  // Dijkstra
  priority_queue<State> q;
  q.emplace(0,src,-1);
  while(q.size()){
    int dist, node, prev;
    tie(dist, ode, prev) = q.top(); q.pop();
    dist = -dist;
    // ~~ find next state ~~
    q.emplace(-new_dist, new_node, node);
  }
}
And that's why emplace_back faster: emplace_back is faster than push_back 'cause it just construct value at the end of vector but push_back construct it somewhere else and then move it to the vector.
Also in the code above you can see how tie(args...) works. You can also use ignore keyword in tie to ignore a value:
tuple<int, int, int, char> t (3, 4, 5, 'g');
int a, b;
tie(b, ignore, a, ignore) = t;
cout << a << ' ' << b << '\n';
Output: 5 3
I use this macro and I love it:
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
First of all, you don't need to name the type you want to use. Second of all it goes forwards and backwards based on (begin > end) condition. e.g. rep(i, 1, 10) is 1, 2, ..., 8, 9 and rep(i, 10, 1) is 9, 8, ..., 2, 1
It works well with different types e.g.
vector<int> v = {4, 5, 6, 4, 8};
rep(it, end(v), begin(v))
    cout << *it << ' ';
// prints "8 4 6 5 4"
Also there is another great feature of C++11, lambda functions!
Lambdas are like other languages' closure. It defines like this:
[capture list](parameters) -> return value { body }
one) Capture List: simple! We don't need it here, so just put []
two) parameters: simple! e.g. int x, string s
three) return value: simple again! e.g. pair<int, int> which can be omitted most of the times (thanks to Jacob)
four) body: contains function bodies, and returns return value.
e.g.
auto f = [] (int a, int b) -> int { return a + b; };
cout << f(1, 2); // prints "3"
You can use lambdas in for_each, sort and many more STL functions:
vector<int> v = {3, 1, 2, 1, 8};
sort(begin(v), end(v), [] (int a, int b) { return a > b; });
for (auto i: v) cout << i << ' ';
Output:
8 3 2 1 1
From Igorjan94's comment:
Usage of move:
When you work with STL containers like vector, you can use move function to just move container, not to copy it all.
vector<int> v = {1, 2, 3, 4};
vector<int> w = move(v);

cout << "v: ";
for (auto i: v)
    cout << i << ' ';

cout << "\nw: ";
for (auto i: w)
    cout << i << ' ';
Output:
v: 
w: 1 2 3 4
As you can see v moved to w and not copied.

7. C++0x Strings

one) Raw Strings (From IvayloS's comment)
You can have UTF-8 strings, Raw strings and more. Here I want to show raw strings. We define a raw string as below:
string s = R"(Hello, World!)"; // Stored: "Hello, World!"
A raw string skips all escape characters like \n or \". e.g.
string str = "Hello\tWorld\n";
string r_str = R"(Hello\tWorld\n)";
cout << str << r_str;
Output:
Hello World
Hello\tWorld\n
You can also have multiple line raw string:
string r_str =
R"(Dear Programmers,
I'm using C++11
Regards, Swift!)";
cout << r_str;
Output:
Dear Programmer,
I'm using C++11
Regards, Swift!
two) Regular Expressions (regex)
Regular expressions are useful tools in programming, we can define a regular expression by regex e.g. regex r = "[a-z]+";. We will use raw string for them because sometimes they have \ and other characters. Look at the example:
regex email_pattern(R"(^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+$)"); // This email pattern is not totally correct! It's correct for most emails.

string
valid_email("swift@codeforces.com"),
invalid_email("hello world");

if (regex_match(valid_email, email_pattern))
    cout << valid_email << " is valid\n";
else
    cout << valid_email << " is invalid\n";

if (regex_match(invalid_email, email_pattern))
    cout << invalid_email << " is valid\n";
else
    cout << invalid_email << " is invalid\n";
Output:
swift@codeforces.com is valid
hello world is invalid
Note: You can learn Regex in this website.
three) User-defined literals
You already know literals from C++ like: 0xA, 1000ll, 3.14f and so on...
Now you can have your own custom literals! Sounds great :) So let's see an example:
long long operator "" _m(unsigned long long literal) {
 return literal;
}

long double operator "" _cm(unsigned long long literal) {
 return literal / 100.0;
}

long long operator "" _km(unsigned long long literal) {
 return literal * 1000;
}

int main() {
 // See results in meter:
 cout << 250_m << " meters \n"; // Prints 250 meters
 cout << 12_km << " meters \n"; // Prints 12000 meters
 cout << 421_cm << " meters \n"; // Prints 4.21 meters
}
Note that a literal should start with an underscore (_). We declare a new literal by this pattern:
[returnType] operator "" _[name]([parameters]) { [body] }
note that parameters only can be one of these:
(const char *)
(unsigned long long int)
(long double)
(char)
(wchar_t)
(char16_t)
(char32_t)
(const char *, size_t)
(const wchar_t *, size_t)
(const char16_t *, size_t)
(const char32_t *, size_t)
Literals also can used with templates.

Comments

Post a Comment

Popular posts from this blog

Big O Notation — Time & Space Complexity in Ruby!

  Big O Cheat Sheet In this post, we will look at the Big O Notation both time and space complexity! For all our examples we will be using Ruby. What is Big O Notation? Big O notation is just a fancy way of describing how your code’s performance depends on the amount of data its processing. It allows us to calculate the worst possible runtime of an algorithm, or how long it takes the algorithm to complete. In other words, it informs us of how much it will slow down based on the input size. It’s usually talked about in two ways the  time complexity ( how long an algorithm takes )and  space complexity ( how much space an algorithm uses ) Let me put this graph here we can refer to it as we go on, it’s a graph showing the complexities compare against each other. Big O complexity chart Time Complexity Before we get try wrapping our heads around the different big O notations here is a nice table that I am borrowing to show how speed will slow down based on the size of the datas...
Post a Comment
Read more

NT Part 2: Generating Primes, Prime Test, Prime Factorization

  Generating primes fast is very important in some problems. Let's cut to the chase and introduce Eratosthenes's Sieve. The main idea is the following. Suppose we want to find all primes between 2 and 50. Iterate from 2 to 50. We start with 2. Since it is not checked, it is a prime number. Now check all numbers that are multiple of    except  2. Now we move on, to number 3. It's not checked, so it is a prime number. Now check all numbers that are multiple of  ,   except  3. Now move on to 4. We see that this is checked - this is a multiple of 2! So 4 is not a prime. We continue doing this. Here's the implementation. #include <stdio.h> int primechk [ 21000 ] ;   void preprocess ( void ) { int i, j ; for ( i = 2 ; i <= 20000 ; i ++ ) { primechk [ i ] = 1 ; } for ( i = 2 ; i <= 20000 ; i ++ ) { if ( primechk [ i ] == 1 ) { for ( j = 2 ; i * j <= 20000...
Post a Comment
Read more

NT Part 6: Sieve of Eratosthenes(Details)

  About 2300 years ago from today, famous Greek mathematician Euclid proved that there are an infinite number of prime numbers. Since then people have been searching for these prime numbers. In 1849, one of the greatest mathematician of all time, Carl Fredrick Gauss, had identified almost all of the prime numbers within the first 3 hundred thousand whole numbers. In the age of computers, we can find large prime numbers in the blink of an eye. But to do that, we need to know a bit of programming and a 2000 year old algorithm. By the end of this tutorial, you will be able to figure out a solution on your own to Gauss’s problem. What is a Prime Number? A prime number is an integer number that is divisible by 1 and the number itself only. For example, 7 is divisible by 1 and 7 only. But 6 is not a prime number because 6 is be divisible by 2 and 3 as well. It is worth mentioning that 1 itself is not a prime number. Now if you are asked to determine if a number is a prime number, you can...
Post a Comment
Read more