Vectors, pairs, tuples, and iterators

Dynamic arrays, grouping values, and moving through data the way judges expect — fast I/O, reserve, and range-based for.

Why vector is your default container

In competitive programming, std::vector is the workhorse: variable size, cache-friendly contiguous storage, and interoperability with every algorithm in <algorithm>.

Mental model: a dynamic array that doubles (typically) when full — amortized O(1) push_back, random access in O(1).

Contest habits:

Use vector<int> or vector<long long>; pick width to match constraints (overflow is a classic WA).
a.size() is size_t; mixing with int in loops causes bugs — use int n = (int)a.size() or for (size_t i = 0; i < a.size(); ++i).
a.back() / a.front() after checking non-empty.

Example — read n, fill, sum:

int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
long long s = 0;
for (long long x : a) s += x;

Example — adjacency list (undirected graph):

int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
}

Example — emplace_back (construct in place):

vector<pair<int,int>> edges;
edges.emplace_back(1, 2);  // no extra pair temporary

pair and tuple: grouping without structs

std::pair<T,U> stores two values; std::tuple generalizes to n types. Pairs appear everywhere: edges (u, w), events (time, type), sorting keys (key, index) for stability by original order.

C++17: std::tuple + std::tie or structured bindings:

auto [x, y] = p;  // if p is pair or tuple

Sorting pairs: default lexicographic order compares first, then second — perfect for (coordinate, id) or (cost, vertex).

Example — sort by value, tie-break by original index:

int n;
cin >> n;
vector<pair<int,int>> a(n);  // (value, index)
for (int i = 0; i < n; i++) {
    cin >> a[i].first;
    a[i].second = i;
}
sort(a.begin(), a.end());  // smaller value first; smaller index wins ties

Example — tie with sort (C++11):

vector<tuple<int,int,int>> t;  // (a, b, c)
// ...
sort(t.begin(), t.end());  // lexicographic on tuple
int x, y, z;
tie(x, y, z) = t[0];

Example — structured binding in a loop:

vector<pair<int,int>> edges = {{1,2},{3,4}};
for (auto [u, v] : edges) {
    // use u, v
}

Iterators: the glue to algorithms

Most STL algorithms take iterator pairs [begin, end) — half-open interval, end is “one past last”.

Common patterns:

a.begin(), a.end() for the whole vector.
a.rbegin(), a.rend() for reverse iteration.
auto it = lower_bound(a.begin(), a.end(), x); then it - a.begin() for an index.

Invalidation: inserting into a vector can invalidate iterators (reallocation). In contests, either build in one pass, reserve upfront, or re-query begin() after growth.

Example — index from lower_bound on sorted vector:

vector<int> a = {1, 3, 3, 7};
int x = 3;
auto it = lower_bound(a.begin(), a.end(), x);
int idx = int(it - a.begin());  // first position >= x
bool found = (it != a.end() && *it == x);

Example — erase all occurrences of value v (unsorted: use new vector or map; here: sort+unique or remove-erase on unsorted):

// If sorted:
a.erase(lower_bound(a.begin(), a.end(), v),
        upper_bound(a.begin(), a.end(), v));

Example — reverse iteration:

for (auto it = a.rbegin(); it != a.rend(); ++it) {
    int x = *it;
}

reserve and fast I/O

reserve(n) does not change size(); it only allocates capacity so repeated push_back avoids reallocations — useful when you know n from input.

Fast I/O (many platforms): at the start of main:

ios::sync_with_stdio(false);
cin.tie(nullptr);

Use \n instead of endl unless you need the flush. For huge inputs, some competitors use scanning with scanf or custom fast readers — know your contest environment.

Example — reserve + push_back (unknown count until EOF is different; here n known):

int n;
cin >> n;
vector<int> a;
a.reserve(n);
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    a.push_back(x);
}
// a.size() == n; capacity >= n

Example — resize vs constructor vector<int> b(n):

vector<int> c(n, 0);   // n zeros
c.resize(2 * n);       // grows, new slots default-initialized (0 for int)

Patterns in words

Typical flow: read n, reserve(n), loop push_back; or read into fixed vector<int> a(n) and process. Use pairs to sort by multiple criteria without writing a struct.

1READ n
2RESERVE capacity for n elements
3FOR i = 1 to n
4  READ x
5  APPEND x to vector
6SORT vector OR PASS (begin, end) to algorithm

Complexity and gotchas

Time: push_back amortized O(1); random access O(1); inserting/erasing in the middle is O(n) due to shifting.

Space: contiguous — roughly capacity * sizeof(T).

Gotcha: vector<vector<int>> as an adjacency list is standard; remember each inner vector is separate — total edges still drive memory.

Complexity Analysis

Time Complexity

Amortized O(1) push_back; O(n) for linear scans

Space Complexity

O(n) for n stored elements

Reallocation may invalidate iterators until you understand capacity; reserve when n is known

Growth Rate Comparison