QORIX

COMPETITIVE PLAYGROUND

C++ STL Master Guide

Detailed explanation of containers with practical usage examples.

std::vector

Container

A dynamic array that can resize itself automatically when an element is inserted or deleted.

When to use: Use when you need a sequence of elements where you primarily access items by index or add/remove from the end. It is the default container to use in C++ for most cases.
Complexity
Access: O(1)
End Insert/Delete: O(1)
Search: O(n)

Usage Examples

Basic Operations
vector<int> v = {1, 2, 3};
v.push_back(4); // [1, 2, 3, 4]
v.pop_back();    // [1, 2, 3]
cout << v[0];    // 1
Resizing and Filling
vector<int> v(10, -1); // Size 10, all values -1
v.clear();             // Removes all elements
if (v.empty()) cout << "Empty";
2D Vector (Matrix)
vector<vector<int>> matrix(rows, vector<int>(cols, 0));
matrix[0][1] = 5;

std::set

Container

A container that stores unique elements in a specific sorted order (usually a Red-Black Tree).

When to use: Use when you need to store elements in sorted order and ensure no duplicates. Useful for finding the smallest/largest element quickly.
Complexity
Insert/Delete/Search: O(log n)

Usage Examples

Unique Sorted Elements
set<int> s;
s.insert(5);
s.insert(2);
s.insert(5); // Ignored (already exists)
for(int x : s) cout << x; // Outputs 2 5
Finding Elements
if (s.count(10)) cout << "Found";
auto it = s.find(5);
if (it != s.end()) s.erase(it);
Upper & Lower Bound
set<int> s = {10, 20, 30};
auto it = s.lower_bound(15); // Points to 20

std::map

Container

An associative container that stores Key-Value pairs, sorted by key.

When to use: Use when you need to associate a value with a key (like a dictionary) and keep the keys in sorted order.
Complexity
Insert/Delete/Search: O(log n)

Usage Examples

Key-Value Pairing
map<string, int> age;
age["Alice"] = 25;
age["Bob"] = 30;
cout << age["Alice"];
Iterating through Map
for (auto const& [name, val] : age) {
    cout << name << " is " << val;
}

std::priority_queue

Container

A container adapter that provides constant time lookup of the largest (or smallest) element.

When to use: Use for Heap-based algorithms like Dijkstra or when you always need to access the maximum/minimum element efficiently.
Complexity
Push/Pop: O(log n)
Top: O(1)

Usage Examples

Max Heap (Default)
priority_queue<int> pq;
pq.push(10); pq.push(30); pq.push(20);
cout << pq.top(); // 30
pq.pop();
Min Heap
priority_queue<int, vector<int>, greater<int>> minH;
minH.push(10); minH.push(5);
cout << minH.top(); // 5

std::unordered_map

Container

An associative container using Hashing to store key-value pairs (unordered).

When to use: Use when order doesn't matter and you need faster average performance than std::map. Note: Can be attacked with anti-hash cases on Codeforces.
Complexity
Average: O(1)
Worst: O(n)

Usage Examples

Fast Frequency Count
unordered_map<int, int> freq;
for(int x : arr) freq[x]++;

std::deque

Container

Double-ended queue that allows fast insertion and deletion at both ends.

When to use: Use when you need to add or remove elements from both the front and the back efficiently.
Complexity
Push/Pop Front/Back: O(1)

Usage Examples

Sliding Window Deque
deque<int> dq;
dq.push_back(10);
dq.push_front(20);
dq.pop_back();
dq.pop_front();