STL Containers and Algorithms
The Standard Template Library (STL) provides containers and algorithms that are the backbone of C++ programming.
Containers
Sequential Containers
| Container | Access | Insert/Remove (end) | Insert/Remove (middle) | Memory |
|---|---|---|---|---|
std::vector | O(1) random | O(1) amortized | O(n) | Contiguous |
std::array | O(1) random | N/A (fixed) | N/A | Contiguous |
std::deque | O(1) random | O(1) amortized | O(n) | Segmented |
std::list | O(n) linear only | O(1) at ends | O(1) with iterator | Linked |
Associative Containers
| Container | Lookup | Ordered? | Duplicates? |
|---|---|---|---|
std::set | O(log n) | ✅ Yes | ❌ No |
std::map | O(log n) | ✅ Yes | Keys must be unique |
std::multiset | O(log n) | ✅ Yes | ✅ Yes |
std::multimap | O(log n) | ✅ Yes | ✅ Yes |
std::unordered_set | O(1) avg | ❌ No | ❌ No |
std::unordered_map | O(1) avg | ❌ No | Keys must be unique |
std::unordered_multiset | O(1) avg | ❌ No | ✅ Yes |
std::unordered_multimap | O(1) avg | ❌ No | ✅ Yes |
Adapters
| Adapter | Underlying | Use |
|---|---|---|
std::stack | std::deque (default) | LIFO — push/pop from one end |
std::queue | std::deque (default) | FIFO — push to back, pop from front |
std::priority_queue | std::vector (default) | Max-heap — push/pop highest priority |
Algorithms
The <algorithm> header provides functions that work on any iterator range:
std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end()); // ascending sort
std::reverse(v.begin(), v.end()); // reverse
auto it = std::find(v.begin(), v.end(), 8); // linear search
auto count = std::count(v.begin(), v.end(), 5); // count occurrences
auto minmax = std::minmax_element(v.begin(), v.end()); // both
auto sum = std::accumulate(v.begin(), v.end(), 0); // sum (in <numeric>)
auto [it, ok] = std::binary_search(...); // binary search (requires sorted)
// Transform one range into another
std::transform(v.begin(), v.end(), result.begin(),
[](int x) { return x * 2; }); // lambda functionComplexity Guarantees
std::sort— O(n log n) average, O(n log n) worststd::find— O(n) linear searchstd::binary_search— O(log n), but requires sorted rangestd::unordered_map::find— O(1) average, O(n) worststd::map::find— O(log n) always
The STL is designed so you can swap containers without changing algorithm code — that's the power of iterators.