The C++ Standard Template Library (STL) is a powerful collection of generic classes and functions that provides ready-to-use data structures (containers), algorithms, and iterators. Built on template programming, the STL includes containers like vector, list, map, and set; algorithms like sort, find, and transform; and iterators that connect containers and algorithms—enabling you to write efficient, reusable code without reinventing fundamental programming building blocks.
Introduction: Standing on the Shoulders of Giants
Before the STL, every C++ programmer had to implement their own linked lists, dynamic arrays, sorting algorithms, and search routines. This was error-prone, time-consuming, and led to inconsistent quality across codebases. The Standard Template Library changed everything by providing a comprehensive, tested, and highly optimized collection of data structures and algorithms that work together seamlessly.
The STL is not just a library—it’s a design philosophy. It demonstrates how template programming can create generic, type-safe, and efficient abstractions. When you use vector<int> instead of a raw array, sort() instead of a hand-written sorting loop, or map<string, int> instead of a custom hash table, you’re leveraging decades of computer science knowledge packaged into a clean, consistent interface.
Three fundamental concepts unite the STL: containers (objects that store data), algorithms (functions that operate on data), and iterators (objects that provide access to container elements). These three components are designed to work together but remain independent—any iterator-compatible container can be used with any iterator-compatible algorithm. This orthogonal design is what makes the STL so powerful and flexible.
This comprehensive guide will walk you through the essential components of the STL, showing you how containers, algorithms, and iterators work individually and together. You’ll learn through practical examples that demonstrate real-world usage, understand the design principles behind the STL, and gain the knowledge you need to leverage this toolkit effectively in your own programs.
The Three Pillars of the STL
The STL is built around three interconnected concepts that work together as a unified system.
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// PILLAR 1: CONTAINER - stores data
vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
cout << "=== Original Data (Container) ===" << endl;
for (int n : numbers) {
cout << n << " ";
}
cout << endl;
// PILLAR 2: ITERATOR - provides access to elements
cout << "\n=== Using Iterators to Access Data ===" << endl;
for (vector<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// PILLAR 3: ALGORITHM - operates on data via iterators
cout << "\n=== After sort() Algorithm ===" << endl;
sort(numbers.begin(), numbers.end());
for (int n : numbers) {
cout << n << " ";
}
cout << endl;
// All three working together
cout << "\n=== Finding a Value (all three together) ===" << endl;
auto it = find(numbers.begin(), numbers.end(), 7);
if (it != numbers.end()) {
cout << "Found 7 at position: " << distance(numbers.begin(), it) << endl;
}
return 0;
}Step-by-step explanation:
- vector<int> numbers: The container — stores a collection of integers in dynamic memory
- Initializer list:
{5, 2, 8, 1, 9, 3, 7, 4, 6}provides initial values at construction - Range-based for loop: Modern syntax that hides iterator complexity
- vector<int>::iterator: The iterator type — a pointer-like object that navigates the container
- numbers.begin(): Returns iterator pointing to the first element
- numbers.end(): Returns iterator pointing just past the last element (sentinel)
- *it: Dereferences the iterator to get the element value
- ++it: Advances iterator to the next element
- sort(): An algorithm — takes two iterators as boundaries and sorts the range
- Decoupled design: sort() doesn’t know or care that numbers is a vector
- find(): Another algorithm — searches for value 7 between begin() and end()
- Return value check: find() returns end() if element not found
- distance(): Calculates how many steps between two iterators (i.e., the index)
- Three pillars unified: All three concepts connect through the iterator interface
Output:
Plaintext
=== Original Data (Container) ===
5 2 8 1 9 3 7 4 6
=== Using Iterators to Access Data ===
5 2 8 1 9 3 7 4 6
=== After sort() Algorithm ===
1 2 3 4 5 6 7 8 9
=== Finding a Value (all three together) ===
Found 7 at position: 6STL Containers: Choosing the Right Storage
The STL offers a range of containers, each with different performance trade-offs. Choosing the right container is key to writing efficient code.
C++
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <string>
using namespace std;
int main() {
// --- vector: dynamic array, O(1) random access ---
cout << "=== vector ===" << endl;
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.insert(vec.begin() + 1, 15); // Insert at position 1
cout << "Contents: ";
for (int v : vec) cout << v << " ";
cout << endl;
cout << "Element at index 2: " << vec[2] << endl;
cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << endl;
// --- list: doubly-linked list, O(1) insert/delete anywhere ---
cout << "\n=== list ===" << endl;
list<string> lst;
lst.push_back("Banana");
lst.push_front("Apple");
lst.push_back("Cherry");
cout << "Contents: ";
for (const string& s : lst) cout << s << " ";
cout << endl;
// Efficient insert in the middle
auto it = lst.begin();
advance(it, 1); // Move iterator to index 1
lst.insert(it, "Apricot"); // O(1) insert at iterator position
cout << "After insert: ";
for (const string& s : lst) cout << s << " ";
cout << endl;
// --- deque: double-ended queue, O(1) push/pop both ends ---
cout << "\n=== deque ===" << endl;
deque<int> dq;
dq.push_back(3);
dq.push_front(1);
dq.push_back(4);
dq.push_front(0);
cout << "Contents: ";
for (int d : dq) cout << d << " ";
cout << endl;
dq.pop_front();
dq.pop_back();
cout << "After pop_front and pop_back: ";
for (int d : dq) cout << d << " ";
cout << endl;
return 0;
}Step-by-step explanation:
- vector<int> vec: Contiguous array that grows dynamically as elements are added
- push_back(): Adds element to the end — O(1) amortized (occasionally triggers resize)
- vec.insert(vec.begin() + 1, 15): Inserts 15 at index 1 — O(n) because elements shift right
- vec[2]: Random access by index — O(1), very fast due to contiguous memory
- capacity vs size: Size is elements used; capacity is total allocated memory (can differ)
- list<string> lst: Doubly-linked list — each node has pointers to previous and next
- push_front(): Adds to the front — O(1) for list (expensive O(n) for vector)
- advance(it, 1): Moves iterator forward by 1 step (list iterators can’t use + like vector)
- lst.insert(it, “Apricot”): O(1) insertion once you have the iterator position
- deque<int> dq: Double-ended queue — efficient O(1) push/pop at both ends
- push_front() on deque: Efficient — deque is internally a segmented array
- pop_front() and pop_back(): Remove elements from both ends in O(1)
- Container choice matters: Vector for random access, list for frequent midpoint inserts, deque for both-ends operations
Output:
Plaintext
=== vector ===
Contents: 10 15 20 30
Element at index 2: 20
Size: 4, Capacity: 8
=== list ===
Contents: Apple Banana Cherry
After insert: Apple Apricot Banana Cherry
=== deque ===
Contents: 0 1 3 4
After pop_front and pop_back: 1 3Associative Containers: Key-Based Lookup
Associative containers organize data by keys, enabling fast lookup, insertion, and deletion.
C++
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
// --- map: sorted key-value pairs, O(log n) operations ---
cout << "=== map ===" << endl;
map<string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 82;
scores["Charlie"] = 91;
scores["Diana"] = 88;
cout << "All scores (sorted by key):" << endl;
for (const auto& pair : scores) {
cout << " " << pair.first << ": " << pair.second << endl;
}
// Lookup
cout << "Bob's score: " << scores["Bob"] << endl;
// Check existence before accessing
if (scores.count("Eve") == 0) {
cout << "Eve not found in map" << endl;
}
// --- set: sorted unique values, O(log n) operations ---
cout << "\n=== set ===" << endl;
set<int> uniqueNumbers;
uniqueNumbers.insert(5);
uniqueNumbers.insert(3);
uniqueNumbers.insert(8);
uniqueNumbers.insert(3); // Duplicate — silently ignored
uniqueNumbers.insert(1);
cout << "Unique numbers (sorted): ";
for (int n : uniqueNumbers) cout << n << " ";
cout << endl;
cout << "Contains 3? " << (uniqueNumbers.count(3) ? "Yes" : "No") << endl;
cout << "Contains 7? " << (uniqueNumbers.count(7) ? "Yes" : "No") << endl;
// --- unordered_map: hash table, O(1) average operations ---
cout << "\n=== unordered_map ===" << endl;
unordered_map<string, string> capitals;
capitals["France"] = "Paris";
capitals["Germany"] = "Berlin";
capitals["Japan"] = "Tokyo";
capitals["USA"] = "Washington D.C.";
cout << "Capital of Japan: " << capitals["Japan"] << endl;
cout << "Capital of Germany: " << capitals["Germany"] << endl;
cout << "All capitals (unordered):" << endl;
for (const auto& [country, capital] : capitals) {
cout << " " << country << " -> " << capital << endl;
}
return 0;
}Step-by-step explanation:
- map<string, int>: Sorted associative container; keys are always in ascending order
- operator[] for insertion:
scores["Alice"] = 95inserts or updates the key “Alice” - pair.first / pair.second: Each map element is a std::pair — first is key, second is value
- Automatic sorting: Map iterates in alphabetical order regardless of insertion order
- scores.count(“Eve”): Returns 0 if key doesn’t exist, 1 if it does (map has unique keys)
- set<int>: Stores only unique values, automatically sorted
- insert() on duplicate: Silently ignored — set enforces uniqueness
- O(log n) operations: Map and set use red-black trees internally
- set.count(): Returns 1 if element exists, 0 otherwise — safe existence check
- unordered_map<string, string>: Hash map — no ordering, but O(1) average lookup
- Hash-based lookup: Uses hash function on key to find bucket directly
- Structured binding:
const auto& [country, capital](C++17) unpacks pair neatly - Order not guaranteed: unordered_map iterates in implementation-defined order
- When to choose: map for sorted output or range queries; unordered_map for fastest lookup
Output:
Plaintext
=== map ===
All scores (sorted by key):
Alice: 95
Bob: 82
Charlie: 91
Diana: 88
Bob's score: 82
Eve not found in map
=== set ===
Unique numbers (sorted): 1 3 5 8
Contains 3? Yes
Contains 7? No
=== unordered_map ===
Capital of Japan: Tokyo
Capital of Germany: Berlin
All capitals (unordered):
USA -> Washington D.C.
Japan -> Tokyo
Germany -> Berlin
France -> ParisContainer Adapters: Specialized Interfaces
Container adapters wrap existing containers to provide restricted, specialized interfaces.
C++
#include <iostream>
#include <stack>
#include <queue>
#include <priority_queue>
#include <string>
using namespace std;
int main() {
// --- stack: LIFO (Last In, First Out) ---
cout << "=== stack (LIFO) ===" << endl;
stack<string> callStack;
callStack.push("main()");
callStack.push("calculateTax()");
callStack.push("getRate()");
cout << "Call stack (top to bottom):" << endl;
while (!callStack.empty()) {
cout << " " << callStack.top() << endl;
callStack.pop();
}
// --- queue: FIFO (First In, First Out) ---
cout << "\n=== queue (FIFO) ===" << endl;
queue<string> printQueue;
printQueue.push("Document1.pdf");
printQueue.push("Report.docx");
printQueue.push("Invoice.pdf");
cout << "Processing print queue:" << endl;
while (!printQueue.empty()) {
cout << " Printing: " << printQueue.front() << endl;
printQueue.pop();
}
// --- priority_queue: highest priority out first ---
cout << "\n=== priority_queue (max-heap by default) ===" << endl;
priority_queue<int> pq;
pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);
pq.push(40);
cout << "Dequeuing by priority (highest first):" << endl;
while (!pq.empty()) {
cout << " " << pq.top() << endl;
pq.pop();
}
// Min-heap: use greater<int> comparator
cout << "\n=== priority_queue (min-heap) ===" << endl;
priority_queue<int, vector<int>, greater<int>> minPQ;
minPQ.push(30);
minPQ.push(10);
minPQ.push(50);
minPQ.push(20);
cout << "Dequeuing by priority (lowest first):" << endl;
while (!minPQ.empty()) {
cout << " " << minPQ.top() << endl;
minPQ.pop();
}
return 0;
}Step-by-step explanation:
- stack<string>: Adapts an underlying container (deque by default) into a LIFO interface
- push(): Adds element on top of the stack
- top(): Reads the topmost element without removing it
- pop(): Removes the topmost element (does NOT return it — check top() first)
- LIFO behavior: getRate() was pushed last, so it comes off first — models a call stack
- queue<string>: FIFO container — first element pushed is the first one dequeued
- front(): Reads the element at the front (oldest element)
- FIFO behavior: Document1.pdf was pushed first, so it prints first — models a print queue
- priority_queue<int>: Max-heap by default — largest element always at top
- push() reorders internally: After each push, heap property is maintained automatically
- top() on priority_queue: Always returns the highest priority (max) element
- greater<int> comparator: Reverses the ordering, creating a min-heap
- Container adapters hide complexity: You can’t iterate over stack/queue — intentional restriction
- Real-world models: Stack = undo history; Queue = task scheduling; Priority Queue = event simulation
Output:
Plaintext
=== stack (LIFO) ===
Call stack (top to bottom):
getRate()
calculateTax()
main()
=== queue (FIFO) ===
Processing print queue:
Printing: Document1.pdf
Printing: Report.docx
Printing: Invoice.pdf
=== priority_queue (max-heap by default) ===
Dequeuing by priority (highest first):
50
40
30
20
10
=== priority_queue (min-heap) ===
Dequeuing by priority (lowest first):
10
20
30
50Iterators: The Glue Between Containers and Algorithms
Iterators are objects that behave like pointers, allowing algorithms to traverse containers without knowing their internal structure.
C++
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = {10, 20, 30, 40, 50};
// --- Forward iteration ---
cout << "=== Forward Iteration ===" << endl;
for (auto it = vec.begin(); it != vec.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// --- Reverse iteration ---
cout << "\n=== Reverse Iteration (rbegin/rend) ===" << endl;
for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
cout << *rit << " ";
}
cout << endl;
// --- Const iterator (read-only access) ---
cout << "\n=== Const Iterator (read-only) ===" << endl;
for (auto cit = vec.cbegin(); cit != vec.cend(); ++cit) {
cout << *cit << " ";
// *cit = 99; // ERROR: cannot assign through const iterator
}
cout << endl;
// --- Iterator arithmetic (only random-access iterators) ---
cout << "\n=== Iterator Arithmetic (vector) ===" << endl;
auto it = vec.begin();
cout << "First element: " << *it << endl;
cout << "Third element: " << *(it + 2) << endl;
cout << "Last element: " << *(vec.end() - 1) << endl;
// --- Iterator with list (bidirectional, no arithmetic) ---
cout << "\n=== Bidirectional Iterator (list) ===" << endl;
list<string> words = {"apple", "banana", "cherry"};
auto listIt = words.end();
--listIt; // Move backward to last element
cout << "Last word: " << *listIt << endl;
--listIt;
cout << "Second-to-last word: " << *listIt << endl;
// --- Using iterators to modify elements ---
cout << "\n=== Modifying Elements via Iterator ===" << endl;
for (auto it2 = vec.begin(); it2 != vec.end(); ++it2) {
*it2 *= 2; // Double each element
}
cout << "After doubling: ";
for (int v : vec) cout << v << " ";
cout << endl;
return 0;
}Step-by-step explanation:
- vec.begin(): Returns an iterator pointing at the first element (index 0)
- vec.end(): Returns an iterator pointing one past the last element — not a valid element
- it != vec.end(): Loop condition — stops when iterator reaches the sentinel
- ++it: Advances iterator to next element (equivalent to pointer arithmetic for vector)
- *it: Dereferences iterator — gives the element value at current position
- rbegin() / rend(): Reverse iterators — rbegin() starts at last, rend() is before first
- ++rit on reverse iterator: Moves backward through the container
- cbegin() / cend(): Const iterators — allow reading but prevent modification
- Compile-time safety:
*cit = 99won’t compile, protecting data integrity - it + 2: Only valid for random-access iterators (vector, deque, array)
- list iterators are bidirectional: Support ++ and — but not + or –
- advance() alternative: Use
advance(it, n)for non-random-access iterators - **it2 = 2: Dereferencing and assigning through non-const iterator modifies the element
- Iterator categories: Input, output, forward, bidirectional, random-access — each with different capabilities
Output:
Plaintext
=== Forward Iteration ===
10 20 30 40 50
=== Reverse Iteration (rbegin/rend) ===
50 40 30 20 10
=== Const Iterator (read-only) ===
10 20 30 40 50
=== Iterator Arithmetic (vector) ===
First element: 10
Third element: 30
Last element: 50
=== Bidirectional Iterator (list) ===
Last word: cherry
Second-to-last word: banana
=== Modifying Elements via Iterator ===
After doubling: 20 40 60 80 100STL Algorithms: Powerful Operations on Any Container
STL algorithms are generic functions that work on iterator ranges, enabling the same code to operate on any compatible container.
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
using namespace std;
int main() {
vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
// --- Sorting ---
cout << "=== Sorting ===" << endl;
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
cout << "Sorted ascending: ";
for (int n : sorted) cout << n << " ";
cout << endl;
sort(sorted.begin(), sorted.end(), greater<int>());
cout << "Sorted descending: ";
for (int n : sorted) cout << n << " ";
cout << endl;
// --- Searching ---
cout << "\n=== Searching ===" << endl;
sort(nums.begin(), nums.end()); // binary_search requires sorted input
bool found = binary_search(nums.begin(), nums.end(), 5);
cout << "Binary search for 5: " << (found ? "Found" : "Not found") << endl;
auto pos = find(nums.begin(), nums.end(), 9);
if (pos != nums.end()) {
cout << "Linear find 9 at index: " << distance(nums.begin(), pos) << endl;
}
// --- Counting ---
cout << "\n=== Counting ===" << endl;
int countOf5 = count(nums.begin(), nums.end(), 5);
cout << "Count of 5: " << countOf5 << endl;
int countEven = count_if(nums.begin(), nums.end(), [](int n){ return n % 2 == 0; });
cout << "Count of even numbers: " << countEven << endl;
// --- Transforming ---
cout << "\n=== Transforming ===" << endl;
vector<int> doubled(nums.size());
transform(nums.begin(), nums.end(), doubled.begin(), [](int n){ return n * 2; });
cout << "Doubled values: ";
for (int n : doubled) cout << n << " ";
cout << endl;
// --- Accumulating ---
cout << "\n=== Accumulating ===" << endl;
int sum = accumulate(nums.begin(), nums.end(), 0);
cout << "Sum of all elements: " << sum << endl;
int product = accumulate(nums.begin(), nums.end(), 1, multiplies<int>());
cout << "Product of all elements: " << product << endl;
// --- Removing and Erasing ---
cout << "\n=== Removing Duplicates ===" << endl;
vector<int> v2 = {1, 1, 2, 3, 3, 4, 5, 5};
auto newEnd = unique(v2.begin(), v2.end()); // Moves duplicates to end
v2.erase(newEnd, v2.end()); // Erase duplicates
cout << "After removing duplicates: ";
for (int n : v2) cout << n << " ";
cout << endl;
return 0;
}Step-by-step explanation:
- sort(begin, end): Sorts elements in the range in-place — O(n log n) average
- sorted copy: We copy nums to sorted first so original is preserved
- greater<int>(): A functor that reverses the comparison, producing descending order
- binary_search(): Requires sorted input — O(log n) search, returns bool
- find(): Linear search — O(n), works on any range, returns iterator to element
- distance(begin, pos): Calculates number of steps from begin to pos (i.e., index)
- count(): Counts occurrences of a specific value — O(n)
- count_if(): Counts elements satisfying a predicate — lambda
[](int n){ return n % 2 == 0; } - Lambda syntax:
[](int n){ return n * 2; }— anonymous function defined inline - transform(): Applies function to each element, stores result in output range
- Output range:
doubled.begin()must point to container with enough space - accumulate(): Folds range into single value starting from initial value (0)
- multiplies<int>(): Built-in functor for multiplication — used as custom operation
- unique(): Moves consecutive duplicates to end, returns iterator to new logical end
- erase(): Combined with unique() in “erase-remove idiom” to physically delete duplicates
Output:
Plaintext
=== Sorting ===
Sorted ascending: 1 1 2 3 3 4 5 5 6 9
Sorted descending: 9 6 5 5 4 3 3 2 1 1
=== Searching ===
Binary search for 5: Found
Linear find 9 at index: 9
=== Counting ===
Count of 5: 2
Count of even numbers: 3
=== Transforming ===
Doubled values: 2 2 4 6 6 8 10 10 12 18
=== Accumulating ===
Sum of all elements: 39
Product of all elements: 19440
=== Removing Duplicates ===
After removing duplicates: 1 2 3 4 5Lambdas and Functors: Customizing Algorithms
STL algorithms accept callable objects—functions, functors, and lambdas—to customize their behavior.
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
// --- Functor (function object) ---
struct IsLongerThan {
int threshold;
IsLongerThan(int t) : threshold(t) {}
bool operator()(const string& s) const {
return static_cast<int>(s.size()) > threshold;
}
};
int main() {
vector<string> words = {"apple", "fig", "banana", "kiwi", "strawberry", "plum"};
// --- Using a plain function ---
auto printWord = [](const string& s) {
cout << " " << s << endl;
};
cout << "=== All words ===" << endl;
for_each(words.begin(), words.end(), printWord);
// --- Using a lambda for custom sorting ---
cout << "\n=== Sorted by length ===" << endl;
vector<string> sorted = words;
sort(sorted.begin(), sorted.end(), [](const string& a, const string& b) {
return a.size() < b.size(); // Sort shortest first
});
for (const string& s : sorted) cout << " " << s << endl;
// --- Using a functor for filtering ---
cout << "\n=== Words longer than 4 chars (functor) ===" << endl;
vector<string> longWords;
copy_if(words.begin(), words.end(),
back_inserter(longWords),
IsLongerThan(4));
for (const string& s : longWords) cout << " " << s << endl;
// --- Lambda capturing outer variable ---
cout << "\n=== Words containing letter 'a' (capturing lambda) ===" << endl;
char target = 'a';
vector<string> withA;
copy_if(words.begin(), words.end(),
back_inserter(withA),
[target](const string& s) {
return s.find(target) != string::npos;
});
for (const string& s : withA) cout << " " << s << endl;
// --- transform with lambda ---
cout << "\n=== Uppercased words ===" << endl;
vector<string> upper(words.size());
transform(words.begin(), words.end(), upper.begin(), [](string s) {
for (char& c : s) c = toupper(c);
return s;
});
for (const string& s : upper) cout << " " << s << endl;
return 0;
}Step-by-step explanation:
- IsLongerThan struct: A functor — a struct/class with operator() making it callable
- threshold member: Functor stores state (unlike plain functions), initialized in constructor
- operator(): Makes the struct callable:
IsLongerThan(4)(someWord)evaluates to bool - Lambda for printWord:
[](const string& s){ ... }— anonymous callable object - for_each(): Calls the callable on every element — replaces manual loop
- Lambda for sort comparator: Takes two elements, returns true if first should come before second
- a.size() < b.size(): Sorts by string length instead of alphabetical order
- copy_if(): Copies elements satisfying predicate into output range
- back_inserter(longWords): Output iterator that calls push_back() — avoids pre-sizing
- IsLongerThan(4): Creates functor with threshold=4, used as predicate
- [target] capture: Lambda captures the
targetvariable by value from outer scope - s.find(target): Returns index of character or string::npos if not found
- transform() with lambda: Applies transformation to each element, storing result
- toupper(c): Standard function converting character to uppercase
- Lambdas vs functors: Lambdas are concise for simple cases; functors allow reuse and parameterization
Output:
Plaintext
=== All words ===
apple
fig
banana
kiwi
strawberry
plum
=== Sorted by length ===
fig
kiwi
plum
apple
banana
strawberry
=== Words longer than 4 chars (functor) ===
apple
banana
strawberry
=== Words containing letter 'a' (capturing lambda) ===
apple
banana
strawberry
=== Uppercased words ===
APPLE
FIG
BANANA
KIWI
STRAWBERRY
PLUMSTL Containers Performance Comparison
| Container | Access | Insert (end) | Insert (middle) | Search | Memory |
|---|---|---|---|---|---|
| vector | O(1) | O(1) amortized | O(n) | O(n) | Contiguous |
| list | O(n) | O(1) | O(1)* | O(n) | Non-contiguous |
| deque | O(1) | O(1) | O(n) | O(n) | Segmented |
| map | O(log n) | O(log n) | O(log n) | O(log n) | Tree |
| unordered_map | O(1) avg | O(1) avg | O(1) avg | O(1) avg | Hash table |
| set | O(log n) | O(log n) | O(log n) | O(log n) | Tree |
| stack/queue | O(1) top/front | O(1) | N/A | N/A | Adapted |
*list insert is O(1) only when you already have an iterator to the position
Putting It All Together: A Real-World Example
Let’s build a word frequency counter combining multiple STL components:
C++
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
int main() {
string text = "the quick brown fox jumps over the lazy dog the fox";
// Step 1: Tokenize text into words (vector as working storage)
vector<string> words;
istringstream stream(text);
string word;
while (stream >> word) {
words.push_back(word);
}
cout << "=== Total words: " << words.size() << " ===" << endl;
// Step 2: Count frequency (map for key-value storage)
map<string, int> frequency;
for (const string& w : words) {
frequency[w]++; // Creates entry with 0 if not exists, then increments
}
cout << "\n=== Word Frequencies (alphabetical) ===" << endl;
for (const auto& [w, count] : frequency) {
cout << " " << w << ": " << count << endl;
}
// Step 3: Sort by frequency (vector of pairs + custom sort)
vector<pair<string, int>> freqVec(frequency.begin(), frequency.end());
sort(freqVec.begin(), freqVec.end(),
[](const pair<string, int>& a, const pair<string, int>& b) {
return a.second > b.second; // Sort by count, descending
});
cout << "\n=== Top Words by Frequency ===" << endl;
int shown = 0;
for (const auto& [w, count] : freqVec) {
cout << " " << w << ": " << count << endl;
if (++shown >= 5) break; // Show top 5 only
}
// Step 4: Find words that appear more than once (copy_if)
vector<string> repeatedWords;
copy_if(freqVec.begin(), freqVec.end(),
back_inserter(repeatedWords),
[](const pair<string, int>& p) { return p.second > 1; });
// Note: we stored pairs, so adjust:
cout << "\n=== Words appearing more than once ===" << endl;
for (const auto& [w, count] : freqVec) {
if (count > 1) cout << " " << w << " (" << count << " times)" << endl;
}
// Step 5: Total unique words (set)
int uniqueCount = frequency.size();
cout << "\n=== Summary ===" << endl;
cout << " Total words: " << words.size() << endl;
cout << " Unique words: " << uniqueCount << endl;
return 0;
}Step-by-step explanation:
- istringstream: Wraps a string so it can be read word by word using
>> - push_back(word): Each extracted word added to words vector
- map<string, int> frequency: Key = word, value = count; automatically sorted
- frequency[w]++: If key doesn’t exist, map creates it with value 0, then increments
- Structured binding [w, count]: C++17 syntax to unpack pair in range-for
- Map auto-sorts: Output is alphabetical because map orders by key
- vector<pair<string,int>>: Copy map entries into vector to allow reordering
- Construct from iterators:
vector(frequency.begin(), frequency.end())copies all pairs - Custom sort comparator:
a.second > b.secondsorts by value (count) descending - Top-5 loop: Manually count shown items and break after 5
- Multiple STL components: vector, map, sort, copy_if, back_inserter work together
- frequency.size(): Number of map entries = number of unique words
- Composable design: Each component does one job; they compose into powerful solution
- Real pattern: Tokenize → aggregate → sort → filter — a very common data-processing pipeline
Output:
Plaintext
=== Total words: 10 ===
=== Word Frequencies (alphabetical) ===
brown: 1
dog: 1
fox: 2
jumps: 1
lazy: 1
over: 1
quick: 1
the: 3
=== Top Words by Frequency ===
the: 3
fox: 2
brown: 1
dog: 1
jumps: 1
=== Words appearing more than once ===
the (3 times)
fox (2 times)
=== Summary ===
Total words: 10
Unique words: 8Conclusion: The STL as Your Foundation
The Standard Template Library is not just a collection of utilities—it’s the backbone of modern C++ programming. By mastering its three pillars—containers, iterators, and algorithms—you gain access to decades of optimized, tested, and standardized code that handles the low-level details so you can focus on solving real problems.
Key takeaways:
- Containers manage data storage: vector for arrays, list for linked lists, map for key-value pairs, set for unique sorted values
- Iterators are the universal interface between containers and algorithms, behaving like smart pointers
- Algorithms like sort, find, transform, and accumulate work on any iterator range—completely decoupled from containers
- Container adapters (stack, queue, priority_queue) provide specialized interfaces over existing containers
- Lambdas and functors customize algorithm behavior inline, replacing verbose loop logic
- Choose containers wisely: vector for random access, map for fast key lookup, unordered_map for O(1) average performance
- The erase-remove idiom (unique + erase) efficiently removes elements in-place
- back_inserter enables growing output containers on the fly without pre-sizing
The STL’s design—separating storage from access from operations—is a masterpiece of software engineering. Once you think in terms of containers, iterators, and algorithms, you’ll find that most data manipulation problems decompose naturally into these building blocks. Use the STL, and write less code that does more—correctly, efficiently, and expressively.
