STL – Arrays, Vectors, Deques, Stacks, Queues

Revision en5, by Nourhan_Abo-Heba, 2025-09-02 22:53:19

Hi everyone 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:

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:

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:

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:

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:

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

// check if vector is empty
if (!vec.empty()) {
    vec.pop_back();          // safe pop
    cout << vec.back();      // safe access
}

Sorting

sort(vec.begin(), vec.end());        // increasing
sort(vec.rbegin(), vec.rend());      // decreasing
sort(vec.begin()+l, vec.begin()+r);  // sort subarray [l, r)

Reversing

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.

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).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Nourhan_Abo-Heba 2026-02-25 14:20:47 8744
en5 English Nourhan_Abo-Heba 2025-09-02 22:53:19 1349
en4 English Nourhan_Abo-Heba 2025-09-02 16:48:09 130
en3 English Nourhan_Abo-Heba 2025-09-02 16:43:01 374
en2 English Nourhan_Abo-Heba 2025-09-02 16:23:09 120
en1 English Nourhan_Abo-Heba 2025-09-02 10:04:58 1900 Initial revision (published)