C++ Tips

Language details that decide correctness and speed in contests.

Integer types

Type	Range
int	$\pm 2.1\times 10^9$
unsigned int	$4.3\times 10^9$
long long	$\pm 9.2\times 10^{18}$
unsigned long long	$1.8\times 10^{19}$
__int128	$\pm 1.7\times 10^{38}$ — GCC only, and no cin/cout support

The overflow rule

int * int is computed as int even when assigned to a long long. Write 1LL * a * b, or make one operand long long. This is the most common wrong answer in competitive programming.

__int128 is genuinely useful for multiplying two values near $10^{18}$ modulo another, and for exact area computations in geometry. Print it by converting to a string manually.

Division and modulo of negatives

C++ truncates toward zero: -7 / 2 == -3 and -7 % 2 == -1. For a mathematical (non-negative) modulus:

int mod(int a, int m) { return ((a % m) + m) % m; }
int floorDiv(int a, int b) { return a / b - ((a % b != 0) && ((a < 0) != (b < 0))); }

Both come up constantly in grid wrap-around, modular arithmetic, and coordinate maths.

size() is unsigned

for (int i = 0; i < (int)v.size() - 1; i++)      // correct
for (int i = 0; i < v.size() - 1; i++)           // INFINITE LOOP when v is empty

v.size() - 1 on an empty vector is $2^{64}-1$. Always cast, or use the sz() macro from the template.

Sorting

sort(all(v), [](const P& a, const P& b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second > b.second;                   // tie-break descending
});

The comparator must be a strict weak ordering: cmp(a,a) must be false. Using <= is undefined behaviour and really does crash std::sort on large inputs — it is not a theoretical concern.

stable_sort preserves the order of equal elements; nth_element finds the $k$-th in $O(n)$ average.

Useful algorithms

Call	Does
lower_bound(all(v), x)	first $\ge x$
upper_bound(all(v), x)	first $>x$
v.erase(unique(all(v)), v.end())	dedupe a sorted vector
next_permutation(all(v))	next lexicographic permutation
accumulate(all(v), 0LL)	sum — note the 0LL
__gcd(a, b)	GCD (std::gcd in C++17)
iota(all(v), 0)	fill with $0,1,2,\dots$
partial_sum(all(v), out.begin())	prefix sums
minmax_element(all(v))	both extremes in one pass
count_if, all_of, any_of	predicate queries

lower_bound on a set

Use the member s.lower_bound(x), not std::lower_bound(all(s), x). The free function needs random access and degrades to $O(n)$ on a tree-based container.

Reference in range-for

for (auto& [key, val] : mp) val *= 2;        // modifies
for (const auto& s : strings) use(s);        // no copy
for (auto s : strings) use(s);               // copies every string

Copying strings or vectors in a loop is a silent constant-factor disaster.

Structured bindings and auto

auto [a, b] = make_pair(1, 2);
map<int,int> mp;
if (auto it = mp.find(k); it != mp.end()) use(it->second);

Recursion depth

The default stack is about 1-8 MB; a DFS on $10^6$ nodes with a large frame will overflow. Options: convert to an explicit stack, shrink the frame (avoid passing containers by value), or on Codeforces use a thread with a larger stack.

// GCC: run main work on a 256 MB stack
int main() { thread t(work, 0); t.join(); }    // or the classic setrlimit trick on Linux

Floating point

Compare with an epsilon, never with ==. Prefer exact integer arithmetic wherever the problem allows it — see Floating Point. long double gives 80-bit precision on x86 and is usually worth the switch in geometry.

Common undefined behaviour

Code	Problem
1 << 31	overflow — use 1LL << 31
x << 64	shift $\ge$ width
v[i] with i == v.size()	out of bounds
a[i++] = i	unsequenced modification
a comparator using <=	not a strict weak ordering
signed overflow	UB, and the optimiser will exploit it
reading an uninitialised variable	UB, and often works locally

-fsanitize=undefined catches most of these; see Debug Macros.

See also: STL Containers · Pitfalls · I/O Optimization · Contest Template