C++ STL (Standard Template Library) Complete Study Guide
1. STL Overview
What is STL?
The Standard Template Library is a collection of template classes and functions that provide:
Containers: Data structures to store collections of objects
Iterators: Objects that point to elements in containers
Algorithms: Functions that perform operations on containers
Function Objects: Classes that act like functions
Adaptors: Components that modify the interface of other components
Key Benefits
Generic Programming: Works with any data type
Efficiency: Highly optimized implementations
Standardized: Consistent across different compilers
Reusability: No need to implement common data structures
2. Containers
2.1 Sequence Containers
Vector
Dynamic array that can grow/shrink at runtime.
cpp
#include <vector>
vector<int> vec = {1, 2, 3, 4, 5};
// Basic operations
vec.push_back(6); // Add to end: O(1) amortized
vec.pop_back(); // Remove from end: O(1)
vec.insert(vec.begin() + 2, 10); // Insert at position: O(n)
vec.erase(vec.begin() + 1); // Remove at position: O(n)
// Access
int val = vec[2]; // Direct access: O(1)
int val2 = vec.at(2); // Bounds-checked access: O(1)
int front = vec.front(); // First element: O(1)
int back = vec.back(); // Last element: O(1)
// Size operations
vec.size(); // Current size
vec.capacity(); // Current capacity
vec.reserve(100); // Reserve space for 100 elements
vec.resize(10); // Resize to 10 elements
Deque (Double-ended Queue)
Allows fast insertion/deletion at both ends.
cpp
#include <deque>
deque<int> dq = {1, 2, 3};
dq.push_front(0); // Add to front: O(1)
dq.push_back(4); // Add to back: O(1)
dq.pop_front(); // Remove from front: O(1)
dq.pop_back(); // Remove from back: O(1)
// Random access like vector
int val = dq[1]; // O(1) access
List (Doubly Linked List)
Efficient insertion/deletion anywhere in the container.
cpp
#include <list>
list<int> lst = {1, 2, 3, 4};
lst.push_front(0); // Add to front: O(1)
lst.push_back(5); // Add to back: O(1)
lst.insert(next(lst.begin(), 2), 10); // Insert at position: O(1)
lst.remove(3); // Remove all occurrences of 3: O(n)
lst.sort(); // Sort the list: O(n log n)
lst.unique(); // Remove consecutive duplicates: O(n)
Forward List (Singly Linked List)
More memory-efficient than list, but only forward iteration.
cpp
#include <forward_list>
forward_list<int> flst = {1, 2, 3};
flst.push_front(0); // Add to front: O(1)
flst.insert_after(flst.begin(), 5); // Insert after position: O(1)
flst.remove(2); // Remove all occurrences: O(n)
Array (Fixed-size Array)
Fixed-size array with STL container interface.
cpp
#include <array>
array<int, 5> arr = {1, 2, 3, 4, 5};
arr[2] = 10; // Direct access
arr.at(1) = 20; // Bounds-checked access
arr.fill(0); // Fill all elements with 0
2.2 Associative Containers
Set
Stores unique elements in sorted order.
cpp
#include <set>
set<int> s = {3, 1, 4, 1, 5}; // Duplicates automatically removed
s.insert(2); // Insert element: O(log n)
s.erase(1); // Remove element: O(log n)
// Search operations
auto it = s.find(3); // Find element: O(log n)
if (it != s.end()) {
cout << "Found: " << *it;
}
bool exists = s.count(4); // Check existence: O(log n)
auto lower = s.lower_bound(3); // First element >= 3: O(log n)
auto upper = s.upper_bound(3); // First element > 3: O(log n)
Multiset
Like set but allows duplicate elements.
cpp
#include <set>
multiset<int> ms = {1, 2, 2, 3, 3, 3};
ms.insert(2); // Insert (duplicates allowed)
int count = ms.count(2); // Count occurrences: O(log n + k)
ms.erase(ms.find(2)); // Remove single occurrence
ms.erase(2); // Remove all occurrences
Map
Stores key-value pairs with unique keys in sorted order.
cpp
#include <map>
map<string, int> m = {{"apple", 5}, {"banana", 3}};
m["orange"] = 7; // Insert/update: O(log n)
m.insert({"grape", 4}); // Alternative insert
m.erase("banana"); // Remove by key: O(log n)
// Access
int val = m["apple"]; // Direct access (creates if not exists)
int val2 = m.at("apple"); // Bounds-checked access
// Search
auto it = m.find("grape"); // Find by key: O(log n)
if (it != m.end()) {
cout << it->first << ": " << it->second;
}
Multimap
Like map but allows duplicate keys.
cpp
#include <map>
multimap<string, int> mm;
mm.insert({"fruit", 1});
mm.insert({"fruit", 2}); // Duplicate keys allowed
auto range = mm.equal_range("fruit"); // Get range of elements with key
for (auto it = range.first; it != range.second; ++it) {
cout << it->second << " ";
}
2.3 Unordered Associative Containers (C++11)
Unordered Set
Hash table implementation of set.
cpp
#include <unordered_set>
unordered_set<int> us = {1, 2, 3, 4, 5};
us.insert(6); // Insert: O(1) average, O(n) worst
us.erase(3); // Remove: O(1) average, O(n) worst
bool found = us.find(4) != us.end(); // Find: O(1) average
// Hash table info
cout << "Bucket count: " << us.bucket_count() << endl;
cout << "Load factor: " << us.load_factor() << endl;
Unordered Map
Hash table implementation of map.
cpp
#include <unordered_map>
unordered_map<string, int> um = {{"key1", 10}, {"key2", 20}};
um["key3"] = 30; // Insert/update: O(1) average
um.erase("key1"); // Remove: O(1) average
auto it = um.find("key2"); // Find: O(1) average
if (it != um.end()) {
cout << it->first << ": " << it->second;
}
2.4 Container Adaptors
Stack (LIFO)
cpp
#include <stack>
stack<int> stk;
stk.push(1); // Push element
stk.push(2);
stk.push(3);
while (!stk.empty()) {
cout << stk.top() << " "; // Access top element
stk.pop(); // Remove top element
}
Queue (FIFO)
cpp
#include <queue>
queue<int> q;
q.push(1); // Add to back
q.push(2);
q.push(3);
while (!q.empty()) {
cout << q.front() << " "; // Access front element
q.pop(); // Remove front element
}
Priority Queue (Max Heap by default)
cpp
#include <queue>
priority_queue<int> pq; // Max heap
priority_queue<int, vector<int>, greater<int>> min_pq; // Min heap
pq.push(3);
pq.push(1);
pq.push(4);
while (!pq.empty()) {
cout << pq.top() << " "; // Access max element
pq.pop(); // Remove max element
}
// Output: 4 3 1
3. Iterators
Iterator Types
cpp
vector<int> vec = {1, 2, 3, 4, 5};
// Forward iterator
vector<int>::iterator it = vec.begin();
while (it != vec.end()) {
cout << *it << " ";
++it;
}
// Reverse iterator
vector<int>::reverse_iterator rit = vec.rbegin();
while (rit != vec.rend()) {
cout << *rit << " ";
++rit;
}
// Const iterator
vector<int>::const_iterator cit = vec.cbegin();
// *cit = 10; // Error: cannot modify through const iterator
Iterator Operations
cpp
vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();
// Basic operations
*it; // Dereference
++it; // Move to next
--it; // Move to previous (bidirectional+)
it + 3; // Jump ahead 3 positions (random access)
it - 2; // Jump back 2 positions (random access)
// Helper functions
advance(it, 3); // Move iterator 3 positions forward
auto dist = distance(vec.begin(), vec.end()); // Calculate distance
auto next_it = next(it, 2); // Get iterator 2 positions ahead
auto prev_it = prev(it, 1); // Get iterator 1 position back
4. Algorithms
4.1 Non-modifying Algorithms
cpp
#include <algorithm>
vector<int> vec = {1, 2, 3, 4, 5, 3, 6};
// Search algorithms
auto it = find(vec.begin(), vec.end(), 3); // Find first occurrence
auto it2 = find_if(vec.begin(), vec.end(), [](int x) { return x > 3; }); // Find with condition
// Count algorithms
int count = count(vec.begin(), vec.end(), 3); // Count occurrences
int count_if = count_if(vec.begin(), vec.end(), [](int x) { return x > 3; }); // Count with condition
// Check algorithms
bool all_positive = all_of(vec.begin(), vec.end(), [](int x) { return x > 0; });
bool any_even = any_of(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
bool none_negative = none_of(vec.begin(), vec.end(), [](int x) { return x < 0; });
// For each
for_each(vec.begin(), vec.end(), [](int& x) { cout << x << " "; });
4.2 Modifying Algorithms
cpp
vector<int> vec = {1, 2, 3, 4, 5};
vector<int> dest(5);
// Copy algorithms
copy(vec.begin(), vec.end(), dest.begin()); // Copy all elements
copy_if(vec.begin(), vec.end(), dest.begin(), [](int x) { return x > 2; }); // Copy with condition
// Transform
vector<int> result(vec.size());
transform(vec.begin(), vec.end(), result.begin(), [](int x) { return x * 2; }); // Square each element
// Fill and generate
fill(vec.begin(), vec.end(), 10); // Fill with value 10
generate(vec.begin(), vec.end(), []() { return rand() % 100; }); // Generate random values
// Replace
replace(vec.begin(), vec.end(), 3, 30); // Replace all 3s with 30s
replace_if(vec.begin(), vec.end(), [](int x) { return x > 5; }, 0); // Replace based on condition
4.3 Sorting and Related
cpp
vector<int> vec = {5, 2, 8, 1, 9, 3};
// Sorting
sort(vec.begin(), vec.end()); // Ascending sort
sort(vec.begin(), vec.end(), greater<int>()); // Descending sort
sort(vec.begin(), vec.end(), [](int a, int b) { return abs(a) < abs(b); }); // Custom comparator
// Partial sorting
partial_sort(vec.begin(), vec.begin() + 3, vec.end()); // Sort first 3 elements
nth_element(vec.begin(), vec.begin() + 2, vec.end()); // Put 3rd smallest at position 2
// Binary search (requires sorted container)
bool found = binary_search(vec.begin(), vec.end(), 5);
auto lower = lower_bound(vec.begin(), vec.end(), 5);
auto upper = upper_bound(vec.begin(), vec.end(), 5);
4.4 Set Operations (on sorted ranges)
cpp
vector<int> v1 = {1, 2, 3, 4, 5};
vector<int> v2 = {3, 4, 5, 6, 7};
vector<int> result;
// Set union
set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
// Set intersection
result.clear();
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
// Set difference
result.clear();
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
4.5 Heap Operations
cpp
vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
// Make heap
make_heap(vec.begin(), vec.end()); // Create max heap
// Heap operations
push_heap(vec.begin(), vec.end()); // Add element to heap
pop_heap(vec.begin(), vec.end()); // Move max to end
vec.pop_back(); // Remove the max element
// Sort heap
sort_heap(vec.begin(), vec.end()); // Convert heap to sorted array
5. Function Objects (Functors)
Built-in Function Objects
cpp
#include <functional>
// Arithmetic
plus<int> add;
int result = add(5, 3); // 8
minus<int> subtract;
multiplies<int> multiply;
divides<int> divide;
// Comparison
greater<int> gt;
bool result = gt(5, 3); // true
less<int> lt;
equal_to<int> eq;
not_equal_to<int> neq;
// Logical
logical_and<bool> and_op;
logical_or<bool> or_op;
logical_not<bool> not_op;
Lambda Expressions (C++11)
cpp
// Basic lambda
auto lambda = [](int x) { return x * x; };
int result = lambda(5); // 25
// Lambda with capture
int multiplier = 10;
auto multiply_by = [multiplier](int x) { return x * multiplier; };
// Capture by reference
int counter = 0;
auto increment = [&counter]() { counter++; };
// Generic lambda (C++14)
auto generic = [](auto x, auto y) { return x + y; };
6. Adaptors and Utilities
Iterator Adaptors
cpp
#include <iterator>
vector<int> vec;
// Insert iterators
back_insert_iterator<vector<int>> back_it = back_inserter(vec);
front_insert_iterator<deque<int>> front_it = front_inserter(deq);
insert_iterator<set<int>> ins_it = inserter(s, s.begin());
// Stream iterators
istream_iterator<int> input_it(cin);
ostream_iterator<int> output_it(cout, " ");
Utility Functions
cpp
#include <utility>
// Pair
pair<int, string> p = make_pair(1, "hello");
cout << p.first << " " << p.second;
// Tuple (C++11)
#include <tuple>
tuple<int, double, string> t = make_tuple(1, 3.14, "world");
cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t);
// Move semantics (C++11)
vector<int> v1 = {1, 2, 3};
vector<int> v2 = move(v1); // v1 is now empty, v2 has the data
7. Performance Comparison
Time Complexities
Container Access Insert Delete Search
vector O(1) O(n) O(n) O(n)
deque O(1) O(n) O(n) O(n)
list O(n) O(1) O(1) O(n)
set/map O(log n) O(log n) O(log n) O(log n)
unordered_set/map O(1) avg O(1) avg O(1) avg O(1) avg
When to Use What
vector: Default choice, fast random access, cache-friendly
deque: Need fast insertion at both ends
list: Frequent insertion/deletion in middle
set/map: Need sorted data with fast search
unordered_set/map: Need fastest possible search/insert
8. Best Practices
Container Selection
1. Use vector by default
2. Use deque if you need fast front insertion
3. Use list for frequent middle insertion/deletion
4. Use map/set when you need sorted data
5. Use unordered_map/unordered_set for fastest lookups
Performance Tips
cpp
// Reserve space for vectors when size is known
vector<int> vec;
vec.reserve(1000);
// Use emplace instead of insert for complex objects
vector<pair<int, string>> vec;
vec.emplace_back(1, "hello"); // Better than vec.push_back(make_pair(1, "hello"))
// Use const iterators when not modifying
for (auto cit = vec.cbegin(); cit != vec.cend(); ++cit) {
cout << *cit;
}
// Prefer range-based for loops (C++11)
for (const auto& element : container) {
cout << element;
}
Memory Management
cpp
// Clear vs shrink_to_fit
vector<int> vec(1000);
vec.clear(); // Size = 0, but capacity unchanged
vec.shrink_to_fit(); // Reduce capacity to match size
// Swap trick (pre-C++11)
vector<int>().swap(vec); // Clear and deallocate memory
9. Common Patterns and Idioms
Erase-Remove Idiom
cpp
vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
// Remove all occurrences of 2
vec.erase(remove(vec.begin(), vec.end(), 2), vec.end());
Sort with Custom Comparator
cpp
vector<pair<int, string>> vec = {{3, "apple"}, {1, "banana"}, {2, "cherry"}};
// Sort by first element
sort(vec.begin(), vec.end());
// Sort by string length
sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
return a.second.length() < b.second.length();
});
Finding Min/Max Elements
cpp
vector<int> vec = {3, 1, 4, 1, 5, 9};
auto min_it = min_element(vec.begin(), vec.end());
auto max_it = max_element(vec.begin(), vec.end());
auto minmax_pair = minmax_element(vec.begin(), vec.end());
10. Advanced Topics
Custom Comparators for Containers
cpp
// Custom comparator for set
struct Compare {
bool operator()(int a, int b) const {
return a > b; // Descending order
}
};
set<int, Compare> desc_set;
// Using lambda (C++11)
auto cmp = [](int a, int b) { return a > b; };
set<int, decltype(cmp)> desc_set2(cmp);
Custom Hash Functions
cpp
struct Point {
int x, y;
};
struct PointHash {
size_t operator()(const Point& p) const {
return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
}
};
struct PointEqual {
bool operator()(const Point& a, const Point& b) const {
return a.x == b.x && a.y == b.y;
}
};
unordered_set<Point, PointHash, PointEqual> point_set;
11. Common Mistakes and Pitfalls
1. Iterator Invalidation: Modifying containers while iterating
2. Dangling Iterators: Using iterators after container modification
3. Wrong Container Choice: Using vector when list would be better
4. Not Reserving Space: Causing unnecessary reallocations
5. Comparing Floating Point: Direct equality comparison of floats
12. Practice Problems
Beginner
1. Implement a function to find duplicates in a vector
2. Merge two sorted vectors
3. Find the kth largest element in an array
4. Implement a simple cache using map
Intermediate
1. Implement LRU cache using list and unordered_map
2. Find all anagrams in a list of strings
3. Implement a basic graph using adjacency list
4. Priority queue-based Dijkstra's algorithm
Advanced
1. Implement a custom allocator
2. Thread-safe container wrapper
3. Memory pool for frequent allocations
4. Custom iterator for tree traversal
Quick Reference
Most Common Operations
cpp
// Vector
vector<int> v = {1, 2, 3};
v.push_back(4);
v.size();
v[0];
// Map
map<string, int> m;
m["key"] = 42;
m.find("key") != m.end();
// Set
set<int> s;
s.insert(5);
s.count(5);
// Algorithm
sort(v.begin(), v.end());
auto it = find(v.begin(), v.end(), 3);
The STL is vast and powerful - master these fundamentals and gradually explore advanced features as
needed!
