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 ≥ xupper_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 useback()on an empty vector. lower_boundandupper_boundare binary search, soO(log n).




