C++ STL Complete Guide for Competitive Programming
June 18, 2025Megh
Welcome to the ultimate start-to-end guide for mastering the C++ Standard Template Library (STL) with a competitive programming focus. This guide assumes you know C++ syntax but are new to STL.
TL;DR
STL (Standard Template Library) is your best friend in competitive programming. It provides ready-made data structures and algorithms that save time and reduce bugs. Master containers, algorithms, iterators, functors, and nested containers to solve problems faster and more efficiently.
What is STL?
The Standard Template Library (STL) is a collection of pre-written C++ classes and functions that provide common data structures and algorithms. It's essential for competitive programming as it saves implementation time, reduces bugs, and provides optimized implementations.
STL Components
- Containers - Data structures to store data
- Algorithms - Functions to manipulate data
- Iterators - Objects to traverse containers
- Functors - Function objects for customization
1. Containers
🔹Sequence Containers
Vector
Dynamic array that can grow and shrink during runtime.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v1; // Empty vector
vector<int> v2(5); // Size 5, all elements = 0
vector<int> v3(5, 10); // Size 5, all elements = 10
vector<int> v4 = {1, 2, 3, 4, 5}; // Initialize with values
// Adding elements
v1.push_back(10);
v1.push_back(20);
v1.insert(v1.begin(), 5); // Insert at beginning
// Accessing elements
cout << v1[0] << " " << v1.at(1) << " " << v1.back() << endl;
// Size operations
cout << "Size: " << v1.size() << ", Capacity: " << v1.capacity() << endl;
// Remove elements
v1.pop_back();
v1.erase(v1.begin()); // Remove first element
return 0;
}List
Doubly linked list allowing fast insertion/deletion anywhere.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
list<int> lst = {10, 20, 30};
// Adding elements
lst.push_front(5); // Add at front
lst.push_back(40); // Add at back
lst.insert(next(lst.begin(), 2), 15); // Insert at position
// Remove elements
lst.pop_front();
lst.pop_back();
lst.remove(20); // Remove all occurrences of 20
// Iterate
for(int x : lst) {
cout << x << " ";
}
cout << endl;
return 0;
}Deque
Double-ended queue allowing fast insertion/deletion at both ends.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
deque<int> dq;
dq.push_back(10);
dq.push_front(5);
dq.push_back(20);
cout << "Front: " << dq.front() << ", Back: " << dq.back() << endl;
dq.pop_front();
dq.pop_back();
return 0;
}🔹Container Adaptors
Stack
LIFO (Last In, First Out) container.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
stack<int> stk;
stk.push(10);
stk.push(20);
stk.push(30);
while(!stk.empty()) {
cout << stk.top() << " "; // 30 20 10
stk.pop();
}
return 0;
}Queue
FIFO (First In, First Out) container.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
while(!q.empty()) {
cout << q.front() << " "; // 10 20 30
q.pop();
}
return 0;
}Priority Queue
Container where elements are served based on priority.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
// Max heap (default)
priority_queue<int> maxHeap;
maxHeap.push(30);
maxHeap.push(10);
maxHeap.push(50);
while(!maxHeap.empty()) {
cout << maxHeap.top() << " "; // 50 30 10
maxHeap.pop();
}
cout << endl;
// Min heap
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(30);
minHeap.push(10);
minHeap.push(50);
while(!minHeap.empty()) {
cout << minHeap.top() << " "; // 10 30 50
minHeap.pop();
}
return 0;
}🔹Associative Containers
Set
Stores unique elements in sorted order.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
set<int> s = {30, 10, 20, 10}; // Duplicate 10 ignored
s.insert(40);
s.insert(5);
// Elements: 5, 10, 20, 30, 40
for(int x : s) {
cout << x << " ";
}
cout << endl;
// Search operations
auto it = s.find(20);
if(it != s.end()) {
cout << "Found: " << *it << endl;
}
cout << "Count of 10: " << s.count(10) << endl; // 1 or 0
s.erase(20);
return 0;
}Multiset
Stores elements in sorted order, allows duplicates.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
multiset<int> ms = {30, 10, 20, 10, 20};
ms.insert(10);
ms.insert(25);
// Elements: 10, 10, 10, 20, 20, 25, 30
for(int x : ms) {
cout << x << " ";
}
cout << endl;
cout << "Count of 10: " << ms.count(10) << endl; // 3
// Remove one occurrence
ms.erase(ms.find(10));
// Remove all occurrences
ms.erase(20);
return 0;
}Map
Stores key-value pairs in sorted order of keys.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
map<string, int> mp;
mp["apple"] = 5;
mp["banana"] = 3;
mp["cherry"] = 8;
mp.insert({"date", 2});
mp.insert(make_pair("elderberry", 6));
// Access value
cout << "Apple: " << mp["apple"] << endl;
// Check if key exists
if(mp.find("banana") != mp.end()) {
cout << "Banana found" << endl;
}
// Iterate
for(auto& pair : mp) {
cout << pair.first << ": " << pair.second << endl;
}
mp.erase("banana");
return 0;
}Multimap
Stores key-value pairs in sorted order, allows duplicate keys.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
multimap<string, int> mmp;
mmp.insert({"apple", 5});
mmp.insert({"apple", 3});
mmp.insert({"banana", 8});
mmp.insert({"apple", 7});
cout << "Count of apple: " << mmp.count("apple") << endl; // 3
// Find all values for a key
auto range = mmp.equal_range("apple");
cout << "Apple values: ";
for(auto it = range.first; it != range.second; ++it) {
cout << it->second << " ";
}
cout << endl;
// Remove one occurrence
mmp.erase(mmp.find("apple"));
return 0;
}🔹Unordered Associative Containers
Unordered Set
Hash table storing unique elements with no particular order.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_set<int> us = {30, 10, 20, 10}; // Duplicate ignored
us.insert(40);
us.insert(5);
// No guaranteed order
for(int x : us) {
cout << x << " ";
}
cout << endl;
// Fast search O(1) average
if(us.find(20) != us.end()) {
cout << "20 found" << endl;
}
cout << "Count of 10: " << us.count(10) << endl;
us.erase(20);
return 0;
}Unordered Multiset
Hash table storing elements with no particular order, allows duplicates.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_multiset<int> ums = {30, 10, 20, 10, 20};
ums.insert(10);
ums.insert(25);
cout << "Count of 10: " << ums.count(10) << endl; // 3
// Remove one occurrence
ums.erase(ums.find(10));
// Remove all occurrences
ums.erase(20);
for(int x : ums) {
cout << x << " ";
}
cout << endl;
return 0;
}Unordered Map
Hash table storing key-value pairs with no particular order.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<string, int> ump;
ump["apple"] = 5;
ump["banana"] = 3;
ump["cherry"] = 8;
// Fast access O(1) average
cout << "Apple: " << ump["apple"] << endl;
// Frequency counting
string text = "hello";
unordered_map<char, int> freq;
for(char c : text) {
freq[c]++;
}
for(auto& pair : freq) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}Unordered Multimap
Hash table storing key-value pairs with no particular order, allows duplicate keys.
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_multimap<string, int> ummp;
ummp.insert({"apple", 5});
ummp.insert({"apple", 3});
ummp.insert({"banana", 8});
ummp.insert({"apple", 7});
cout << "Count of apple: " << ummp.count("apple") << endl; // 3
// Find all values for a key
auto range = ummp.equal_range("apple");
cout << "Apple values: ";
for(auto it = range.first; it != range.second; ++it) {
cout << it->second << " ";
}
cout << endl;
return 0;
}2. Nested Containers
🔹2D Vector (Matrix)
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
// Initialize 3x4 matrix with 0
vector<vector<int>> matrix(3, vector<int>(4, 0));
// Initialize with values
vector<vector<int>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Access and modify
matrix[0][0] = 10;
cout << "Element at (1,2): " << grid[1][2] << endl; // 6
// Iterate
for(int i = 0; i < grid.size(); i++) {
for(int j = 0; j < grid[i].size(); j++) {
cout << grid[i][j] << " ";
}
cout << endl;
}
return 0;
}🔹Graph Adjacency List
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 5;
vector<vector<int>> adj(n); // Unweighted graph
vector<vector<pair<int, int>>> wadj(n); // Weighted graph
// Add edges
adj[0].push_back(1);
adj[0].push_back(2);
wadj[0].push_back({1, 5}); // Edge to vertex 1 with weight 5
wadj[0].push_back({2, 3}); // Edge to vertex 2 with weight 3
// Print adjacency list
for(int i = 0; i < n; i++) {
cout << "Vertex " << i << ": ";
for(int neighbor : adj[i]) {
cout << neighbor << " ";
}
cout << endl;
}
return 0;
}🔹Map of Vectors (Grouping)
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
map<string, vector<int>> groups;
groups["even"].push_back(2);
groups["even"].push_back(4);
groups["even"].push_back(6);
groups["odd"].push_back(1);
groups["odd"].push_back(3);
groups["odd"].push_back(5);
for(auto& group : groups) {
cout << group.first << ": ";
for(int num : group.second) {
cout << num << " ";
}
cout << endl;
}
return 0;
}🔹Priority Queue with Pairs
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
// Min heap for Dijkstra (distance, vertex)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0}); // Distance 0 to vertex 0
pq.push({5, 1}); // Distance 5 to vertex 1
pq.push({3, 2}); // Distance 3 to vertex 2
while(!pq.empty()) {
auto [dist, vertex] = pq.top(); // C++17 structured binding
pq.pop();
cout << "Vertex " << vertex << " with distance " << dist << endl;
}
return 0;
}3. Common Algorithms
🔹Sorting
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {64, 34, 25, 12, 22};
sort(v.begin(), v.end()); // Ascending
sort(v.begin(), v.end(), greater<int>()); // Descending
// Custom comparator
vector<pair<int, int>> pairs = {{3, 1}, {1, 2}, {2, 3}};
sort(pairs.begin(), pairs.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
return a.second < b.second;
});
return 0;
}🔹Searching
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {1, 3, 5, 7, 9, 11};
// Binary search (sorted array required)
bool found = binary_search(v.begin(), v.end(), 7);
// Lower and upper bound
auto lb = lower_bound(v.begin(), v.end(), 6);
auto ub = upper_bound(v.begin(), v.end(), 6);
// Find element
auto it = find(v.begin(), v.end(), 5);
if(it != v.end()) {
cout << "Found at index: " << it - v.begin() << endl;
}
return 0;
}Time Complexities
Sequence Containers:
- Vector: Access O(1), Insert/Delete at end O(1), Middle O(n)
- List: Access O(n), Insert/Delete anywhere O(1)
- Deque: Access O(1), Insert/Delete at ends O(1), Middle O(n)
Associative Containers:
- Set/Map/Multiset/Multimap: All operations O(log n)
Unordered Containers:
- Unordered Set/Map/Multiset/Multimap: Average O(1), Worst O(n)
Container Adaptors:
- Stack/Queue: All operations O(1)
- Priority Queue: Insert/Delete O(log n), Top O(1)
Quick Reference for Competitive Programming
Most Used Containers in CP:
vector- Dynamic arrays, most versatilevector<vector<int>>- 2D matrices, DP tablesset/unordered_set- Unique elements, fast searchmap/unordered_map- Key-value pairs, frequency countingpriority_queue- Heap operations, Dijkstrastack/queue- DFS/BFS, expression evaluationvector<vector<pair<int,int>>>- Weighted graphs
Nested Container Tips:
- Use
vector<vector<int>>for 2D arrays and DP - Use
vector<set<int>>for graphs with unique edges - Use
map<int, vector<int>>for grouping data - Use
priority_queue<pair<int,int>>for Dijkstra - Remember to initialize nested containers properly
Master these STL components including nested containers and you'll solve competitive programming problems much faster and with fewer bugs!