No functions found matching your search.
vector<T>
#include <vector>
| Function | Complexity | Description |
|---|---|---|
| v.push_back(x) | O(1) amortized | Append x to end |
| v.pop_back() | O(1) | Remove last element |
| v.size() | O(1) | Number of elements |
| v.empty() | O(1) | True if size == 0 |
| v.clear() | O(n) | Remove all elements |
| v.resize(n) | O(n) | Resize to n elements (fills 0) |
| v.resize(n, val) | O(n) | Resize and fill with val |
| v.assign(n, val) | O(n) | Assign n copies of val |
| v.front() | O(1) | Reference to first element |
| v.back() | O(1) | Reference to last element |
| v[i] | O(1) | Access element at i (no bounds check) |
| v.at(i) | O(1) | Access element at i (throws if out of range) |
| v.insert(it, x) | O(n) | Insert x before iterator it |
| v.insert(it, n, x) | O(n) | Insert n copies of x before it |
| v.erase(it) | O(n) | Remove element at iterator it |
| v.erase(it1, it2) | O(n) | Remove range [it1, it2) |
| v.reserve(n) | O(n) | Reserve capacity for n elements |
| v.capacity() | O(1) | Current allocated capacity |
| v.shrink_to_fit() | O(n) | Release excess capacity |
| v.swap(v2) | O(1) | Swap contents with v2 |
| v.begin() / v.end() | O(1) | Iterator to first / past-last element |
| v.rbegin() / v.rend() | O(1) | Reverse iterators |
| v.data() | O(1) | Raw pointer to underlying array |
| v.emplace_back(args) | O(1) amortized | Construct element in-place at end (faster than push_back) |
| v.emplace(it, args) | O(n) | Construct in-place at iterator |
string
#include <string>
| Function | Complexity | Description |
|---|---|---|
| s.size() / s.length() | O(1) | Number of characters |
| s.empty() | O(1) | True if empty |
| s.push_back(c) | O(1) amortized | Append character c |
| s.pop_back() | O(1) | Remove last character |
| s.append(t) | O(n) | Append string t |
| s += t | O(n) | Concatenate |
| s.substr(pos, len) | O(n) | Substring starting at pos, length len |
| s.find(t) | O(n·m) | First occurrence of t, returns string::npos if not found |
| s.rfind(t) | O(n·m) | Last occurrence of t |
| s.find_first_of(t) | O(n) | First char that is any char in t |
| s.find_last_of(t) | O(n) | Last char that is any char in t |
| s.find_first_not_of(t) | O(n) | First char NOT in t |
| s.replace(pos, len, t) | O(n) | Replace len chars at pos with t |
| s.insert(pos, t) | O(n) | Insert string t at pos |
| s.erase(pos, len) | O(n) | Remove len chars at pos |
| s.clear() | O(n) | Remove all characters |
| s.compare(t) | O(n) | Lexicographic compare; 0 if equal |
| s.at(i) / s[i] | O(1) | Access character at i |
| s.front() / s.back() | O(1) | First / last character |
| s.c_str() | O(1) | Null-terminated C-string pointer |
| s.reverse() — via algorithm | O(n) | reverse(s.begin(), s.end()) |
| stoi(s) / stol / stoll | O(n) | String to int / long / long long |
| stof / stod / stold | O(n) | String to float / double / long double |
| to_string(n) | O(n) | Number to string |
| getline(cin, s) | O(n) | Read full line including spaces |
map<K,V> & unordered_map<K,V>
#include <map> / <unordered_map>
| Function | map / unordered_map | Description |
|---|---|---|
| m[key] | O(log n) / O(1) avg | Access or insert key (inserts default if missing!) |
| m.at(key) | O(log n) / O(1) avg | Access key; throws if not found |
| m.insert({k,v}) | O(log n) / O(1) avg | Insert pair; no-op if key exists |
| m.emplace(k, v) | O(log n) / O(1) avg | In-place insert; faster than insert |
| m.erase(key) | O(log n) / O(1) avg | Remove by key |
| m.erase(it) | O(1) amortized | Remove by iterator |
| m.find(key) | O(log n) / O(1) avg | Returns iterator; m.end() if not found |
| m.count(key) | O(log n) / O(1) avg | 1 if key exists, 0 otherwise |
| m.contains(key) C++20 | O(log n) / O(1) avg | True if key exists (cleaner than count) |
| m.size() | O(1) | Number of key-value pairs |
| m.empty() | O(1) | True if empty |
| m.clear() | O(n) | Remove all elements |
| m.begin() / m.end() | O(1) | Iterators over key-value pairs |
| m.lower_bound(k) map only | O(log n) | Iterator to first key ≥ k |
| m.upper_bound(k) map only | O(log n) | Iterator to first key > k |
| m.equal_range(k) map only | O(log n) | Pair of [lower_bound, upper_bound] |
| m.swap(m2) | O(1) | Swap contents |
| m.merge(m2) C++17 | O(n log n) | Absorb m2 into m (moves nodes) |
multimap: same API, allows duplicate keys. unordered_map: O(n) worst case on hash collision; use custom hash for int pairs.
set<T> & unordered_set<T>
#include <set> / <unordered_set>
| Function | set / unordered_set | Description |
|---|---|---|
| s.insert(x) | O(log n) / O(1) avg | Insert x; no duplicates stored |
| s.erase(x) | O(log n) / O(1) avg | Remove element x |
| s.erase(it) | O(1) amortized | Remove by iterator |
| s.find(x) | O(log n) / O(1) avg | Iterator to x; s.end() if absent |
| s.count(x) | O(log n) / O(1) avg | 1 if x exists, 0 otherwise |
| s.contains(x) C++20 | O(log n) / O(1) avg | True if x exists |
| s.size() | O(1) | Number of elements |
| s.empty() | O(1) | True if empty |
| s.clear() | O(n) | Remove all elements |
| s.lower_bound(x) set only | O(log n) | Iterator to first element ≥ x |
| s.upper_bound(x) set only | O(log n) | Iterator to first element > x |
| *s.begin() | O(1) | Smallest element (set is sorted) |
| *s.rbegin() | O(1) | Largest element |
| s.begin() / s.end() | O(1) | Iterators (sorted order for set) |
| s.swap(s2) | O(1) | Swap contents |
multiset: allows duplicates; count(x) returns actual count. set uses red-black tree internally.
stack<T>
#include <stack>
| Function | Complexity | Description |
|---|---|---|
| st.push(x) | O(1) amortized | Push x onto top |
| st.pop() | O(1) | Remove top element (does NOT return it) |
| st.top() | O(1) | Reference to top element |
| st.size() | O(1) | Number of elements |
| st.empty() | O(1) | True if empty |
| st.emplace(args) | O(1) amortized | Construct element in-place on top |
| st.swap(st2) | O(1) | Swap contents |
queue<T> & deque<T>
#include <queue> / <deque>
| Function | Complexity | Description |
|---|---|---|
| q.push(x) | O(1) amortized | Enqueue x at back |
| q.pop() | O(1) | Dequeue front element |
| q.front() | O(1) | Reference to front element |
| q.back() | O(1) | Reference to back element |
| q.size() | O(1) | Number of elements |
| q.empty() | O(1) | True if empty |
| — deque only — | ||
| dq.push_front(x) | O(1) amortized | Insert at front |
| dq.push_back(x) | O(1) amortized | Insert at back |
| dq.pop_front() | O(1) | Remove from front |
| dq.pop_back() | O(1) | Remove from back |
| dq[i] / dq.at(i) | O(1) | Random access |
| dq.insert(it, x) | O(n) | Insert at iterator |
| dq.erase(it) | O(n) | Erase at iterator |
priority_queue<T>
#include <queue>
| Function | Complexity | Description |
|---|---|---|
| pq.push(x) | O(log n) | Insert x |
| pq.pop() | O(log n) | Remove top element |
| pq.top() | O(1) | Largest element (max-heap by default) |
| pq.size() | O(1) | Number of elements |
| pq.empty() | O(1) | True if empty |
| pq.emplace(args) | O(log n) | Construct in-place |
Min-heap:
Custom comparator:
priority_queue<int, vector<int>, greater<int>> pq;Custom comparator:
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
list<T> (doubly linked)
#include <list>
| Function | Complexity | Description |
|---|---|---|
| l.push_front(x) | O(1) | Insert at front |
| l.push_back(x) | O(1) | Insert at back |
| l.pop_front() | O(1) | Remove from front |
| l.pop_back() | O(1) | Remove from back |
| l.insert(it, x) | O(1) | Insert before iterator (O(1) given iterator!) |
| l.erase(it) | O(1) | Erase at iterator |
| l.front() / l.back() | O(1) | First / last element |
| l.size() / l.empty() | O(1) | Size / empty check |
| l.sort() | O(n log n) | Sort in-place (cannot use std::sort) |
| l.reverse() | O(n) | Reverse in-place |
| l.remove(x) | O(n) | Remove all elements equal to x |
| l.remove_if(pred) | O(n) | Remove all elements where pred is true |
| l.unique() | O(n) | Remove consecutive duplicates |
| l.splice(it, l2) | O(1) | Move all of l2 into l before it |
| l.merge(l2) | O(n) | Merge two sorted lists |
pair<A,B> & tuple<...>
#include <utility> / <tuple>
| Function | Complexity | Description |
|---|---|---|
| make_pair(a, b) | O(1) | Create a pair |
| p.first / p.second | O(1) | Access first / second element |
| p1 < p2 | O(1) | Lexicographic compare (first, then second) |
| make_tuple(a, b, c) | O(1) | Create a tuple |
| get<i>(t) | O(1) | Access i-th element of tuple (compile-time index) |
| tie(a, b, c) = t | O(1) | Unpack tuple into variables |
| auto [a,b,c] = t C++17 | O(1) | Structured binding (cleanest unpack) |
| tuple_size<T>::value | O(1) | Compile-time size of tuple |
| swap(p1, p2) | O(1) | Swap two pairs |
<algorithm>
#include <algorithm>
| Function | Complexity | Description |
|---|---|---|
| sort(b, e) | O(n log n) | Sort range [b, e) ascending |
| sort(b, e, cmp) | O(n log n) | Sort with custom comparator |
| stable_sort(b, e) | O(n log n) | Sort preserving relative order of equals |
| partial_sort(b, m, e) | O(n log k) | Sort only first k elements into [b, m) |
| nth_element(b, nth, e) | O(n) avg | Rearrange so nth element is what it'd be if sorted |
| reverse(b, e) | O(n) | Reverse range in-place |
| rotate(b, mid, e) | O(n) | Left-rotate so mid becomes first |
| binary_search(b, e, x) | O(log n) | True if x exists in sorted range |
| lower_bound(b, e, x) | O(log n) | Iterator to first element ≥ x (sorted range) |
| upper_bound(b, e, x) | O(log n) | Iterator to first element > x (sorted range) |
| equal_range(b, e, x) | O(log n) | Pair of [lower_bound, upper_bound] |
| min(a, b) / max(a, b) | O(1) | Min / max of two values |
| min({a,b,c}) / max({...}) | O(n) | Min / max of initializer list |
| min_element(b, e) | O(n) | Iterator to minimum element |
| max_element(b, e) | O(n) | Iterator to maximum element |
| minmax_element(b, e) | O(n) | Pair of [min_it, max_it] in one pass |
| clamp(v, lo, hi) C++17 | O(1) | Return v clamped to [lo, hi] |
| swap(a, b) | O(1) | Swap two values |
| fill(b, e, val) | O(n) | Fill range with val |
| fill_n(b, n, val) | O(n) | Fill n elements starting at b |
| copy(b, e, out) | O(n) | Copy range to output iterator |
| copy_if(b, e, out, pred) | O(n) | Copy elements satisfying pred |
| transform(b, e, out, fn) | O(n) | Apply fn to each element, store in out |
| for_each(b, e, fn) | O(n) | Apply fn to each element |
| count(b, e, val) | O(n) | Count occurrences of val |
| count_if(b, e, pred) | O(n) | Count elements satisfying pred |
| find(b, e, val) | O(n) | Iterator to first occurrence of val |
| find_if(b, e, pred) | O(n) | Iterator to first element satisfying pred |
| all_of(b, e, pred) | O(n) | True if pred holds for ALL elements |
| any_of(b, e, pred) | O(n) | True if pred holds for ANY element |
| none_of(b, e, pred) | O(n) | True if pred holds for NO element |
| unique(b, e) | O(n) | Remove consecutive duplicates; returns new end |
| remove(b, e, val) | O(n) | Move non-val elements forward; returns new end |
| remove_if(b, e, pred) | O(n) | Remove elements satisfying pred |
| replace(b, e, old, new) | O(n) | Replace all old with new |
| next_permutation(b, e) | O(n) | Advance to next lexicographic permutation; false if last |
| prev_permutation(b, e) | O(n) | Previous permutation |
| merge(b1,e1,b2,e2,out) | O(n+m) | Merge two sorted ranges into out |
| inplace_merge(b, m, e) | O(n log n) | Merge two sorted halves in-place |
| includes(b1,e1,b2,e2) | O(n) | True if [b2,e2) is a subset of [b1,e1) |
| set_union / set_intersection / set_difference | O(n+m) | Set ops on sorted ranges → output iterator |
| is_sorted(b, e) | O(n) | True if range is sorted |
| is_permutation(b1,e1,b2) | O(n²) | True if ranges are permutations of each other |
| shuffle(b, e, rng) | O(n) | Randomly shuffle; use mt19937 as rng |
| accumulate → see numeric | Moved to <numeric> |
<numeric>
#include <numeric>
| Function | Complexity | Description |
|---|---|---|
| accumulate(b, e, init) | O(n) | Sum of range + init value |
| accumulate(b, e, init, fn) | O(n) | Fold/reduce with custom binary op |
| reduce(b, e) C++17 | O(n) | Like accumulate but parallelizable |
| partial_sum(b, e, out) | O(n) | Prefix sums into out |
| adjacent_difference(b,e,out) | O(n) | Differences of consecutive elements |
| inner_product(b1,e1,b2,init) | O(n) | Dot product of two ranges |
| iota(b, e, val) | O(n) | Fill with val, val+1, val+2, ... (index fill) |
| gcd(a, b) C++17 | O(log n) | Greatest common divisor |
| lcm(a, b) C++17 | O(log n) | Least common multiple |
| midpoint(a, b) C++20 | O(1) | Safe (a+b)/2 without overflow |
Bit manipulation builtins & tricks
#include <bit> (C++20) / GCC builtins
| Function | Complexity | Description |
|---|---|---|
| __builtin_popcount(n) | O(1) | Count of set bits (int) |
| __builtin_popcountll(n) | O(1) | Count of set bits (long long) |
| __builtin_clz(n) | O(1) | Count leading zeros. UB if n==0 |
| __builtin_clzll(n) | O(1) | Leading zeros (long long). UB if n==0 |
| __builtin_ctz(n) | O(1) | Count trailing zeros = index of lowest set bit. UB if n==0 |
| __builtin_ctzll(n) | O(1) | Trailing zeros (long long) |
| __builtin_parity(n) | O(1) | Parity: 1 if odd number of set bits |
| std::bit_width(n) C++20 | O(1) | floor(log2(n)) + 1 = bit length |
| std::popcount(n) C++20 | O(1) | Count set bits (unsigned only) |
| std::countl_zero(n) C++20 | O(1) | Leading zeros |
| std::countr_zero(n) C++20 | O(1) | Trailing zeros |
| std::has_single_bit(n) C++20 | O(1) | True if n is a power of 2 |
| std::bit_floor(n) C++20 | O(1) | Largest power of 2 ≤ n |
| std::bit_ceil(n) C++20 | O(1) | Smallest power of 2 ≥ n |
| n & (n-1) | O(1) | Strip lowest set bit (also: n==power of 2 iff result==0) |
| n & (-n) | O(1) | Isolate lowest set bit |
| n | (1 << i) | O(1) | Set bit i |
| n & ~(1 << i) | O(1) | Clear bit i |
| n ^ (1 << i) | O(1) | Toggle bit i |
| (n >> i) & 1 | O(1) | Check if bit i is set |
| n << k / n >> k | O(1) | Multiply / divide by 2^k |
<cmath> & <climits>
#include <cmath> / <climits>
| Function / Constant | Type | Description |
|---|---|---|
| abs(x) | O(1) | Absolute value (use <cstdlib> for int, <cmath> for double) |
| sqrt(x) | O(1) | Square root (double) |
| cbrt(x) | O(1) | Cube root |
| pow(base, exp) | O(1) | base^exp (floating point — use custom for int) |
| log(x) / log2(x) / log10(x) | O(1) | Natural / base-2 / base-10 log |
| ceil(x) / floor(x) | O(1) | Round up / down to integer |
| round(x) | O(1) | Round to nearest integer |
| fmod(x, y) | O(1) | Floating-point remainder |
| hypot(x, y) | O(1) | sqrt(x²+y²) without overflow |
| sin / cos / tan / atan2 | O(1) | Trig functions (radians) |
| INT_MIN / INT_MAX | constant | -2147483648 / 2147483647 |
| LLONG_MIN / LLONG_MAX | constant | Long long min/max |
| INT_MAX / 2 | constant | Safe "infinity" for DP (avoids overflow on addition) |
| 1e18 (1LL<<62) | constant | Common large-value sentinels in CP |
| M_PI | constant | π ≈ 3.14159... (use acos(-1.0) for portability) |
Iterator utilities
#include <iterator>
| Function | Complexity | Description |
|---|---|---|
| begin(c) / end(c) | O(1) | Free function iterators (work on arrays too) |
| rbegin(c) / rend(c) | O(1) | Reverse iterators |
| next(it, n=1) | O(n) | Advance iterator by n (O(1) for random-access) |
| prev(it, n=1) | O(n) | Move iterator back by n |
| advance(it, n) | O(n) | Advance it in-place |
| distance(it1, it2) | O(n) | Number of steps between iterators (O(1) for random-access) |
| back_inserter(c) | O(1) | Output iterator that calls push_back |
| front_inserter(c) | O(1) | Output iterator that calls push_front |
| inserter(c, it) | O(1) | Output iterator that calls insert(it, ...) |