Блог пользователя Nourhan_Abo-Heba

Автор Nourhan_Abo-Heba, история, 15 месяцев назад, По-английски

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:

Codeforces problems (join the group first: STLs Contest Group):

  • Проголосовать: нравится
  • -21
  • Проголосовать: не нравится

»
15 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

STL arrays and C-style arrays are different things; int arr[5]; is different from std::array<int, 5> arr;.

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Nourhan_Abo-Heba (previous revision, new revision, compare).