C++ tricks | Necron's Den

These are some C++ techniques and tricks I’ve accumulated throughout my competitive programming journey.

Faster I/O

This may¹ speed up code execution, especially for problems with large dataset.

std::cin.tie(nullptr);
ios_base::sync_with_stdio(false);

Or an one-lined version

std::cin.tie(nullptr)->ios_base::sync_with_stdio(false);

Btw, cout is not tied to any streams so you don’t have to “untie” it.

There’s also a much faster variant of this technique, though not included here.

More compact 2D array dumping

for (int i = 1; i <= m; i++)
	for (int j = 1; j <= n; j++)
		std::cout << a[i][j] << " \n"[j == m];

It will end the line with either whitespace or newline, based on what j == m is evaluated to ( for 0 - false and \n for 1 - true).

”Superior” hashmap implementation

Usage

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> table;

unordered_maplinear insertion:                                  0.689846
gp_hash_tablelinear insertion:                                  0.256131

unordered_maplinear read/write:                                 1.69783
gp_hash_tablelinear read/write:                                 0.26842

unordered_maprandom insertion:                                  2.90184
gp_hash_tablerandom insertion:                                  0.56553

unordered_maprandom read/write:                                 2.02336
gp_hash_tablerandom read/write:                                 0.403486

This data structure performs much faster than unordered_map in all respects, though maybe exclusive to gcc.

Source: https://codeforces.com/blog/entry/60737

Vector usage

Preallocating vectors

int n = 1e3;
std::vector<int> a(n);

Input with for-in loop

for (int &z : a)
	std::cin >> z;

Using `vector<bool>` to store more boolean data

vector<bool> can be used in place of the traditional bool[] to minimize memory usage as one element of vector<bool> consumes only 1 bit, unlike that of bool[] which uses 1 byte, albeit with a “little” performance penalty as a trade-off cuz it must use proxies to access the actual address.

std::vector<bool> a(1e9); // uses only like ~122MB

Algorithms

Pre-counting divisors

Complexity: $O(n\log n)$

std::vector<int> divc(n+1);
int l = 1e7;
for (int i = 1; i <= l; i++)
	for (int j = i; j <= l; j += i)
		divc[j]++;

Or a faster version (~ $O(n)$ )

for (i = 1; i <= sqrt(l); i++)
	for (j = i; j <= l / i; j++)
		divc[i * j] += 1 + (i != j);

More coming “soon”…

This can slow down your code in some very specific cases. ↩