Hi everyone!
Let's talk about some basic STL containers, their pros/cons, and when to use each.
Table of Contents
- Array
- Vector
- Deque
- Stack
- Queue
- TL;DR
- Tips & Tricks
- Practice Problems
1. Array
- Fixed size.
- Contiguous in memory → random access is O(1).
- Disadvantage: you can't add or erase elements.
int arr[5]; // size is fixed
2. Vector
- Dynamic array — like an array but resizable.
- Contiguous in memory (same as array).
- Adding/removing at the end is O(1).
- Insertion/erasure in the middle or front is O(n) — avoid when possible.
Common functions:
vector<int> v(n); // size n, all zeros vector<int> v; // empty vector v.push_back(10); // add to end — O(1) v.pop_back(); // remove last — O(1) v.resize(100); // change size if (v.empty()) ... // check if empty for (auto x : v) cout << x; // range-based for loop v.erase(v.begin()); // erase first element — O(n) v.insert(v.begin(), 7); // insert at front — O(n)
3. Deque (Double Ended Queue)
- Solves vector's weakness at the front.
- Supports push_front() / pop_front() in O(1).
- Everything else works the same as vector.
deque<int> d; d.push_back(5); d.push_front(3); d.pop_back(); d.pop_front();
4. Stack
- LIFO — Last In, First Out.
- You can only access the most recently pushed element.
- Classic use case: bracket checking.
stack<int> s; s.push(10); s.pop(); cout << s.top(); cout << s.size(); if (s.empty()) ...
5. Queue
- FIFO — First In, First Out.
- Access only the front and back elements.
queue<int> q; q.push(5); // enqueue q.pop(); // dequeue (removes front) cout << q.front(); cout << q.back();
TL;DR
- Array — fixed size, fastest random access.
- Vector — dynamic, fast at the back, slow at the front.
- Deque — dynamic, fast at both ends.
- Stack — LIFO.
- Queue — FIFO.
Tips & Tricks
Inserting at a specific index
v.insert(v.begin() + i, x); // insert before index i v.insert(v.begin() + i + 1, x); // insert after index i
Finding the index of a value with std::find
auto it = find(v.begin(), v.end(), x); int idx = it — v.begin(); // index of x in v
Sorting
sort(v.begin(), v.end()); // ascending sort(v.rbegin(), v.rend()); // descending sort(v.begin() + l, v.begin() + r); // sort subarray [l, r)
Reversing
reverse(v.begin(), v.end()); // reverse entire vector reverse(v.begin() + l, v.begin() + r); // reverse subarray [l, r)
Lower Bound / Upper Bound
Important: the vector must be sorted first.
// first element >= x
auto it = lower_bound(v.begin(), v.end(), x);
int idx = it — v.begin();
// first element > x
auto it2 = upper_bound(v.begin(), v.end(), x);
int idx2 = it2 — v.begin();
// count occurrences of x
int cnt = upper_bound(v.begin(), v.end(), x)
— lower_bound(v.begin(), v.end(), x);
Quick rules:
- lower_bound(x) → index of first element ≥ x
- upper_bound(x) → index of first element > x
- Both are binary search → O(log n)
⚠️ Common Mistakes to Avoid
Practice Problems
AtCoder problems:
- ABC237 D — LR Insertion
- ABC158 D — String Formation
- ABC103 B — String Rotation
- ABC247 D — Cylinder
- ABC216 D — Pair of Balls
Codeforces problems (join the group first: STLs Contest Group):









STL arrays and C-style arrays are different things;
int arr[5];is different fromstd::array<int, 5> arr;.Auto comment: topic has been updated by Nourhan_Abo-Heba (previous revision, new revision, compare).