Let’s talk about some basic STL containers, their pros/cons, and when to use each.↵
↵
---↵
↵
Array↵
↵
* Fixed size.↵
* Contiguous in memory → random access is **O(1)**.↵
* **Disadvantage:** you can’t add or erase elements.↵
↵
Example:↵
↵
```cpp↵
int arr[5]; // size is fixed↵
```↵
↵
---↵
↵
Vector↵
↵
* Dynamic array.↵
* Contiguous in memory (like array).↵
* Supports adding/removing elements at the end in **O(1)**.↵
* Insertion/erasure in the middle or front = **O(n)** (bad!).↵
↵
Common functions:↵
↵
```cpp↵
vector<int> v(n); // with size n↵
vector<int> v; // empty, then use push_back()↵
↵
v.push_back(10); // O(1)↵
v.pop_back(); // O(1)↵
v.resize(100); // change size↵
if(v.empty()) ...↵
↵
for(auto x : v) cout << x; // iterate↵
↵
v.erase(v.begin()); // erase first element O(n)↵
v.insert(v.begin(), 7); // insert at front O(n)↵
```↵
↵
---↵
↵
Deque (Double Ended Queue)↵
↵
* Solves vector’s problem with front operations.↵
* Supports `push_front()` / `pop_front()` in **O(1)**.↵
* Everything else is same as vector.↵
↵
Example:↵
↵
```cpp↵
deque<int> d;↵
d.push_back(5);↵
d.push_front(3);↵
d.pop_back();↵
d.pop_front();↵
```↵
↵
---↵
↵
Stack↵
↵
* LIFO (Last In, First Out).↵
* Only access the last pushed element.↵
↵
Functions:↵
↵
```cpp↵
stack<int> s;↵
s.push(10);↵
s.pop();↵
cout << s.top();↵
cout << s.size();↵
if(s.empty()) ...↵
```↵
↵
Use case: **checking brackets**.↵
↵
---↵
↵
Queue↵
↵
* FIFO (First In, First Out).↵
* Access only first and last elements.↵
↵
Functions:↵
↵
```cpp↵
queue<int> q;↵
q.push(5); // enqueue↵
q.pop(); // dequeue↵
cout << q.front(); ↵
cout << q.back();↵
```↵
↵
---↵
↵
TL;DR↵
↵
* **Array** → fixed size.↵
* **Vector** → dynamic, fast at the back, slow at front.↵
* **Deque** → dynamic, fast at both ends.↵
* **Stack** → LIFO.↵
* **Queue** → FIFO.↵
↵
---↵
↵
Additional Notes↵
↵
Insert before element at index i → v.begin() + i↵
↵
Insert after element at index i → v.begin() + i + 1↵
↵
Finding index with std::find↵
↵
Sometimes you don’t know the index, but you know the value:↵
↵
auto it = find(vec.begin(), vec.end(), i );↵
int idx = it — vec.begin(); // index of element↵
↵
---↵
Tips and Tricks↵
↵
## Useful `vector` functions for CF↵
↵
```cpp↵
// check if vector is empty↵
if (!vec.empty()) {↵
vec.pop_back(); // safe pop↵
cout << vec.back(); // safe access↵
}↵
```↵
↵
---↵
↵
### Sorting↵
↵
```cpp↵
sort(vec.begin(), vec.end()); // increasing↵
sort(vec.rbegin(), vec.rend()); // decreasing↵
sort(vec.begin()+l, vec.begin()+r); // sort subarray [l, r)↵
```↵
↵
---↵
↵
### Reversing↵
↵
```cpp↵
reverse(vec.begin(), vec.end()); // reverse entire vector↵
reverse(vec.begin()+l, vec.begin()+r); // reverse subarray [l, r)↵
```↵
↵
---↵
↵
### Lower Bound / Upper Bound↵
↵
**Important:** vector must be **sorted**.↵
↵
```cpp↵
auto it = lower_bound(vec.begin(), vec.end(), x);↵
// points to first element >= x↵
int idx = it - vec.begin();↵
↵
auto it2 = upper_bound(vec.begin(), vec.end(), x);↵
// points to first element > x↵
int idx2 = it2 - vec.begin();↵
```↵
↵
Quick rules:↵
↵
* `lower_bound(x)` → index of **first ≥ x**↵
* `upper_bound(x)` → index of **first > x**↵
* Count of `x`:↵
↵
```cpp↵
int cnt = upper_bound(vec.begin(), vec.end(), x) ↵
- lower_bound(vec.begin(), vec.end(), x);↵
```↵
↵
---↵
↵
Always remember:↵
↵
* Don’t `pop_back()` or use `back()` on an empty vector.↵
* `lower_bound` and `upper_bound` are **binary search**, so `O(log n)`.↵
↵
---↵
↵
Let's talk about some basic STL containers, their pros/cons, and when to use each.</p>↵
↵
<br>↵
↵
<b>Table of Contents</b>↵
<ul>↵
<li>Array</li>↵
<li>Vector</li>↵
<li>Deque</li>↵
<li>Stack</li>↵
<li>Queue</li>↵
<li>TL;DR</li>↵
<li>Tips & Tricks</li>↵
<li>Practice Problems</li>↵
</ul>↵
↵
<br>↵
↵
<hr>↵
↵
<b>1. Array</b>↵
↵
<ul>↵
<li>Fixed size.</li>↵
<li>Contiguous in memory → random access is <b>O(1)</b>.</li>↵
<li><b>Disadvantage:</b> you can't add or erase elements.</li>↵
</ul>↵
↵
<pre>↵
int arr[5]; // size is fixed↵
</pre>↵
↵
<hr>↵
↵
<b>2. Vector</b>↵
↵
<ul>↵
<li>Dynamic array — like an array but resizable.</li>↵
<li>Contiguous in memory (same as array).</li>↵
<li>Adding/removing at the <b>end</b> is <b>O(1)</b>.</li>↵
<li>Insertion/erasure in the <b>middle or front</b> is <b>O(n)</b> — avoid when possible.</li>↵
</ul>↵
↵
Common functions:↵
↵
<pre>↵
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)↵
</pre>↵
↵
<hr>↵
↵
<b>3. Deque (Double Ended Queue)</b>↵
↵
<ul>↵
<li>Solves vector's weakness at the front.</li>↵
<li>Supports <b>push_front() / pop_front()</b> in <b>O(1)</b>.</li>↵
<li>Everything else works the same as vector.</li>↵
</ul>↵
↵
<pre>↵
deque<int> d;↵
d.push_back(5);↵
d.push_front(3);↵
d.pop_back();↵
d.pop_front();↵
</pre>↵
↵
<hr>↵
↵
<b>4. Stack</b>↵
↵
<ul>↵
<li><b>LIFO</b> — Last In, First Out.</li>↵
<li>You can only access the most recently pushed element.</li>↵
<li>Classic use case: <b>bracket checking</b>.</li>↵
</ul>↵
↵
<pre>↵
stack<int> s;↵
s.push(10);↵
s.pop();↵
cout << s.top();↵
cout << s.size();↵
if (s.empty()) ...↵
</pre>↵
↵
<hr>↵
↵
<b>5. Queue</b>↵
↵
<ul>↵
<li><b>FIFO</b> — First In, First Out.</li>↵
<li>Access only the front and back elements.</li>↵
</ul>↵
↵
<pre>↵
queue<int> q;↵
q.push(5); // enqueue↵
q.pop(); // dequeue (removes front)↵
cout << q.front();↵
cout << q.back();↵
</pre>↵
↵
<hr>↵
↵
<b>TL;DR</b>↵
↵
<ul>↵
<li><b>Array</b> — fixed size, fastest random access.</li>↵
<li><b>Vector</b> — dynamic, fast at the back, slow at the front.</li>↵
<li><b>Deque</b> — dynamic, fast at <i>both</i> ends.</li>↵
<li><b>Stack</b> — LIFO.</li>↵
<li><b>Queue</b> — FIFO.</li>↵
</ul>↵
↵
<hr>↵
↵
<b>Tips & Tricks</b>↵
↵
<br><br>↵
↵
<b>Inserting at a specific index</b>↵
↵
<pre>↵
v.insert(v.begin() + i, x); // insert before index i↵
v.insert(v.begin() + i + 1, x); // insert after index i↵
</pre>↵
↵
<br>↵
↵
<b>Finding the index of a value with std::find</b>↵
↵
<pre>↵
auto it = find(v.begin(), v.end(), x);↵
int idx = it — v.begin(); // index of x in v↵
</pre>↵
↵
<br>↵
↵
<b>Sorting</b>↵
↵
<pre>↵
sort(v.begin(), v.end()); // ascending↵
sort(v.rbegin(), v.rend()); // descending↵
sort(v.begin() + l, v.begin() + r); // sort subarray [l, r)↵
</pre>↵
↵
<br>↵
↵
<b>Reversing</b>↵
↵
<pre>↵
reverse(v.begin(), v.end()); // reverse entire vector↵
reverse(v.begin() + l, v.begin() + r); // reverse subarray [l, r)↵
</pre>↵
↵
<br>↵
↵
<b>Lower Bound / Upper Bound</b>↵
↵
<i>Important: the vector must be sorted first.</i>↵
↵
<pre>↵
// 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);↵
</pre>↵
↵
Quick rules:↵
<ul>↵
<li><b>lower_bound(x)</b> → index of first element <b>≥ x</b></li>↵
<li><b>upper_bound(x)</b> → index of first element <b>> x</b></li>↵
<li>Both are binary search → <b>O(log n)</b></li>↵
</ul>↵
↵
<br>↵
↵
<spoiler summary="⚠️ Common Mistakes to Avoid">↵
<ul>↵
<li>Never call <b>pop_back()</b> or <b>back()</b> on an empty vector — undefined behavior.</li>↵
<li>lower_bound / upper_bound only work correctly on a <b>sorted</b> container.</li>↵
<li>Don't use <b>v.erase(v.begin())</b> in a loop — it's O(n) per call, making the loop O(n²).</li>↵
</ul>↵
</spoiler>↵
↵
<hr>↵
↵
<b>Practice Problems</b>↵
↵
<i>AtCoder problems:</i>↵
<ul>↵
<li><a href="https://atcoder.jp/contests/abc237/tasks/abc237_d?lang=en">ABC237 D — LR Insertion</a></li>↵
<li><a href="https://atcoder.jp/contests/abc158/tasks/abc158_d?lang=en">ABC158 D — String Formation</a></li>↵
<li><a href="https://atcoder.jp/contests/abc103/tasks/abc103_b?lang=en">ABC103 B — String Rotation</a></li>↵
<li><a href="https://atcoder.jp/contests/abc247/tasks/abc247_d?lang=en">ABC247 D — Cylinder</a></li>↵
<li><a href="https://atcoder.jp/contests/abc216/tasks/abc216_d?lang=en">ABC216 D — Pair of Balls</a></li>↵
</ul>↵
↵
<i>Codeforces problems (join the group first: <a href="https://codeforces.me/group/rWwHLW304Z/contests">STLs Contest Group</a>):</i>↵



