C++ Standard Template Library (STL) for problem solving

In short

The Standard Template Library is the part of the C++ standard library that provides ready-made generic containers (vector, map, set, deque), iterators that walk over them, and algorithms (sort, lower_bound, next_permutation) that work on any container through those iterators. It is built on templates, so one sort works for int, string or a user-defined struct, and every operation carries a documented complexity guarantee. For placement coding rounds — Amazon, Microsoft, Google, Flipkart, Zoho, Walmart, Oracle, Goldman Sachs, Samsung R&D, service companies' advanced tracks, and platforms such as CodeChef, HackerRank, HackerEarth and Codeforces — STL fluency is the difference between a 10-line accepted solution and a 100-line buggy one. University MCA papers and lab vivas ask for container definitions, complexities, iterator categories and small programs; GATE tests the underlying data-structure complexities that the STL implements.

Explained

What the STL is: six components

• Containers — store objects: sequence (vector, deque, list, forward_list, array), associative (set, multiset, map, multimap), unordered (unordered_set/map and their multi versions), and adaptors (stack, queue, priority_queue).
• Iterators — generalised pointers that connect containers to algorithms; the glue of the whole design.
• Algorithms — about 100 function templates in <algorithm> and <numeric> that operate on iterator ranges, not on containers.
• Functors / function objects — callable objects (less<int>, greater<int>, lambdas) passed as comparison or operation policy.
• Allocators — encapsulate memory allocation; default std::allocator is almost always left untouched.
• Adaptors — wrap something to change its interface: container adaptors (stack), iterator adaptors (reverse_iterator, back_inserter), function adaptors (std::bind).
• Headers: <vector> <map> <set> <unordered_map> <deque> <list> <stack> <queue> <algorithm> <numeric> <string> <utility> <tuple> <bitset>.
• Everything lives in namespace std. Competitive code often uses #include <bits/stdc++.h> with using namespace std; — a GCC-only convenience header, not standard C++, and not acceptable in production code.

Sequence containers

• vector — dynamic contiguous array. O(1) indexing, amortised O(1) push_back, O(n) insert/erase in the middle. Capacity usually doubles on overflow, so a reallocation copies/moves all elements. reserve(n) avoids repeated reallocation; shrink_to_fit() releases spare capacity. Default choice for almost everything.
• deque — double-ended queue built from fixed-size blocks. O(1) push/pop at both ends and O(1) random access, but elements are not one contiguous block, so no &v[0] guarantee. Used for sliding-window maximum and 0-1 BFS.
• list (doubly linked) and forward_list (singly linked) — O(1) insert/erase given an iterator, but no random access and poor cache behaviour. Rarely the right answer in contests; asked in exams for LRU-style designs where iterators must stay valid.
• array<T,N> — fixed-size stack array with STL interface (size(), begin(), range-for); zero overhead over a C array.
• string — a container of char with STL iterators plus substr, find, +=; works with sort, reverse, count.
• vector<bool> is a space-optimised specialisation (bit-packed) and does not behave like a normal container — operator[] returns a proxy, not a bool&. Use deque<bool>, vector<char> or bitset when that matters.
• bitset<N> — fixed-length bit array with &, |, ^, <<, count(), any(); gives a 64× constant-factor speed-up in subset and DP-bitmask problems.

Ordered associative containers (balanced BST, usually red-black tree)

• set — unique keys kept in sorted order; insert, erase, find, count all O(log n); iteration gives sorted order.
• multiset — duplicates allowed; erase(value) deletes all copies, erase(iterator) deletes exactly one — a classic interview trap.
• map — sorted key→value pairs; m[key] inserts a default-constructed value if the key is absent, so use find or count/contains (C++20) for pure lookup. at() throws std::out_of_range instead of inserting.
• multimap — repeated keys; no operator[]; use equal_range(key).
• Ordering comes from operator< (or less<Key>); a custom key needs a strict weak ordering — comparator returns false for equal elements, otherwise undefined behaviour.
• Unique strength: order queries — begin() for minimum, rbegin() for maximum, and member lower_bound/upper_bound in O(log n). This is why floor/ceiling, "next greater element present in the set", and interval-merge problems use set/map.

Unordered containers (hash table with separate chaining)

• unordered_set / unordered_map — average O(1) insert/find/erase, **worst case O(n)** when many keys collide; no ordering, so no lower_bound and no sorted iteration.
• Controls: bucket_count(), load_factor(), max_load_factor(), reserve(n); rehashing invalidates iterators (references to elements survive).
• Keys need std::hash plus operator==. pair/vector have no default hash — supply a custom hash functor, or encode the pair into one integer (x * 1000000LL + y).
• On Codeforces, unordered_map<int,int> can be attacked by anti-hash tests; a safer habit is map for small data or a custom hash with a random seed.

Container adaptors

• stack<T> — LIFO over a deque by default; push, pop, top, empty, size. No iterators.
• queue<T> — FIFO; push, pop, front, back.
• priority_queue<T> — binary max-heap; push and pop are O(log n), top is O(1). Min-heap: priority_queue<int, vector<int>, greater<int>> pq;. Used for Dijkstra, Prim, k-largest, merging k sorted lists, median maintenance (two heaps).
• Adaptors expose no iterators, cannot be traversed, and cannot remove an arbitrary element — if you need that, use set/multiset as an "indexed heap".

Iterators

• Categories (weakest to strongest): input → output → forward → bidirectional → random access → (C++20) contiguous. vector/deque/array give random access; set/map/list give bidirectional; forward_list gives forward.
• Operations: *it, ++it, --it (bidirectional), it + k, it2 - it1, comparison (random access only). advance(it, k), next(it) and distance(a, b) work for all categories, while prev(it) needs a bidirectional iterator.
• Ranges are half-open [first, last) — end() is one past the last element and must never be dereferenced. So last - first is exactly the size, and an empty range is first == last.
• Iterator invalidation — the most examined fine print:
  • vector: any reallocation invalidates everything; insert/erase invalidates from the point of change onward.
  • deque: insert/erase in the middle invalidates all iterators; push/pop at ends invalidates iterators but keeps references to other elements.
  • list/forward_list: only iterators to the erased element are invalidated.
  • set/map: erase invalidates only the erased element's iterator; insert invalidates none.
  • unordered containers: rehash invalidates iterators, not references.
• erase returns the next valid iterator — the correct loop is it = v.erase(it); else ++it;.
• const_iterator (cbegin/cend) for read-only traversal; rbegin/rend for reverse.

Algorithms and the problem-solving toolkit

• Sorting: sort (introsort: quicksort + heapsort fallback + insertion sort, O(n log n) worst case, not stable), stable_sort (merge-based, O(n log n) or O(n log² n) with low memory), partial_sort (top k), nth_element (average O(n) selection), is_sorted.
• Comparator: a lambda such as [](const P& a, const P& b){ return a.second > b.second; }; it must express "strictly before" or sort can crash on equal elements.
• Binary search on a sorted range: lower_bound (first element not less than x), upper_bound (first element greater than x), binary_search (bool), equal_range (both bounds). Count of x = upper_bound - lower_bound.
• Dedupe idiom: sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); — unique only removes adjacent duplicates, hence the sort first. This is the standard coordinate-compression step.
• Numeric: accumulate (use 0LL to avoid int overflow), partial_sum (prefix sums), adjacent_difference, inner_product, iota (fill 0,1,2,… — used to build DSU parents and index arrays), gcd/lcm (C++17).
• Searching and counting: find, find_if, count, count_if, max_element, min_element, minmax_element, all_of, any_of, none_of.
• Modifying: reverse, rotate, fill, copy, copy_if, transform, remove/remove_if (erase-remove idiom: they only shift, they do not shrink), replace, swap, next_permutation/prev_permutation (lexicographic, needs a sorted start for the full set of n! permutations).
• Set operations on sorted ranges: merge, set_union, set_intersection, set_difference, includes — all O(n + m).
• Heap algorithms on a vector: make_heap (O(n)), push_heap, pop_heap, sort_heap.
• Utilities: pair/make_pair, tuple/make_tuple/tie, structured bindings auto [k, v] : m (C++17), emplace_back (constructs in place, avoids a copy), move, swap, to_string, stoi/stoll, optional (C++17), string_view, std::ranges and views (C++20, e.g. ranges::sort(v)).

Choosing the right container — the decision that is actually marked

1. Need indexing and mostly appends → vector.
2. Need both ends → deque; only one end LIFO/FIFO → stack/queue.
3. Need fastest key lookup, order irrelevant → unordered_map/set.
4. Need sorted order, predecessor/successor, range queries → map/set.
5. Need repeated "extract minimum/maximum" → priority_queue (or multiset if arbitrary deletion is also needed).
6. Need many insert/erase at known positions with stable iterators → list.
7. Constant factors matter: vector beats list in practice even for mid-insertions at small n because of cache locality; unordered_map beats map typically 3–10× but loses ordering.

Key points

• STL - templates-based library of containers, iterators, algorithms, functors, adaptors and allocators.
• Generic programming - algorithms are written against iterator categories, so one sort serves every random-access container.
• Half-open range - every algorithm takes [first, last); end() is a sentinel, never dereference it.
• vector - contiguous, O(1) index, amortised O(1) push_back, reallocation invalidates iterators.
• deque - O(1) at both ends plus random access, but not contiguous.
• list - O(1) splice/erase with an iterator, no random access, cache-unfriendly.
• set/map - red-black tree, O(log n) operations, sorted iteration, member lower_bound.
• unordered_map - hash table, average O(1), worst O(n), no ordering, no lower_bound.
• multiset erase trap - erase(value) removes all equal elements; erase(find(value)) removes one.
• map[] inserts - subscripting a missing key creates it with a default value; find/count/at do not.
• priority_queue - max-heap by default; greater<T> as third template argument gives a min-heap.
• sort - introsort, guaranteed O(n log n), not stable; use stable_sort when equal keys must keep order.
• nth_element - average linear selection; use it for "k-th largest" instead of a full sort.
• lower_bound vs upper_bound - first >= x and first > x; their difference is the frequency of x.
• unique - collapses only adjacent duplicates and returns the new logical end; must be followed by erase.
• erase-remove idiom - v.erase(remove(v.begin(), v.end(), x), v.end()) actually shrinks the vector.
• Comparator contract - strict weak ordering; <= in a comparator is undefined behaviour and can crash sort.
• emplace_back/reserve - construct in place and pre-allocate to cut copies and reallocations.

Formulas and examples

Example 1 — vector growth cost. Push 1,000 ints into an empty vector<int> whose capacity starts at 1 and doubles.

• Capacities reached: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 → 11 allocations (⌈log₂1000⌉ = 10, plus the first).
• Elements copied during reallocation = 1+2+4+…+512 = 1,023 ≈ n, so amortised ≈ 1 copy per element.
• With v.reserve(1000) first: 1 allocation, 0 copies.

Example 2 — container choice by operation count. 2 × 10⁵ insertions plus 2 × 10⁵ lookups.

• map: 4 × 10⁵ operations × log₂(2 × 10⁵) ≈ 4 × 10⁵ × 17.6 ≈ 7.0 × 10⁶ comparisons, each following tree pointers.
• unordered_map: ≈ 4 × 10⁵ hash-and-probe steps — roughly an order of magnitude less work, which is why it is the default for pure frequency counting. Choose map only when sorted output or predecessor queries are needed.

Example 3 — binary search bounds. Sorted array a = 2, 4, 4, 4, 7, 9, 11 (0-based).

• lower_bound(a, 4) → index 1; upper_bound(a, 4) → index 4; frequency of 4 = 4 − 1 = 3.
• Count in [4, 9] = upper_bound(9) − lower_bound(4) = 6 − 1 = 5 (the values 4, 4, 4, 7, 9).
• lower_bound(a, 5) → index 4 (value 7), i.e. the ceiling of 5; the floor is the previous element, 4.

Example 4 — dedupe and coordinate compression.

vector<int> a = {3, 1, 3, 2, 1, 7};
sort(a.begin(), a.end());                       // 1 1 2 3 3 7
a.erase(unique(a.begin(), a.end()), a.end());   // 1 2 3 7  -> size 4
int id = lower_bound(a.begin(), a.end(), 3) - a.begin();   // id = 2

• Original size 6 → compressed size 4; value 3 maps to index 2. Total cost O(n log n) for the sort, O(n) for unique, O(log n) per query.

Example 5 — top-3 of 10⁶ numbers.

• Full sort: ≈ 10⁶ × log₂10⁶ = 10⁶ × 19.93 ≈ 2.0 × 10⁷ comparisons.
• nth_element(v.begin(), v.begin() + 3, v.end(), greater<int>()): average ≈ 10⁶ operations (then sort just those 3) — about 20× less work for the same answer.

Example 6 — k-th largest with a min-heap. Stream of 10⁶ values, k = 100: keep a priority_queue<int, vector<int>, greater<int>> of size 100; per element cost log₂100 ≈ 6.64, total ≈ 6.6 × 10⁶ operations and only 100 ints of memory, versus 4 MB to store all values.

Where it is used

• Product engineering at Indian offices of Amazon, Microsoft, Google, Adobe, Uber, Atlassian and at Flipkart, Zomato, Swiggy, Zoho, Freshworks — hiring rounds are STL-heavy and backend C++ services use vector/unordered_map for in-memory indexes and caches.
• Low-latency trading and quant desks (Tower Research, Graviton, Quadeye, WorldQuant in Mumbai/Gurugram/Bengaluru) — C++ with careful reserve, contiguous vectors and custom allocators for cache-friendly latency.
• Core engineering and embedded/automotive software (Bosch, Continental, KPIT, Tata Elxsi, L&T Technology Services, Qualcomm, Samsung R&D, ISRO/DRDO labs) — STL containers inside simulation, CAD, EDA and telecom stacks; MISRA-style rules sometimes restrict dynamic allocation.
• Competitive programming and hiring tests — CodeChef, Codeforces, ICPC regionals, Google Kick Start-style contests, and company tests on HackerRank/HackerEarth/Mettl where STL cuts implementation time.
• Academic work — MCA/B.Tech data-structures labs, NPTEL C++ courses, and university practical exams that ask for container-based implementations of stacks, graphs, LRU caches and priority scheduling.
• Job roles — SDE/SDE-1, systems engineer, game developer (Unreal uses its own containers but the thinking transfers), quantitative developer, performance engineer.

Interview questions

• Q: Why is push_back on a vector called amortised O(1)? A: Most calls are O(1); a reallocation costs O(n) but happens only on doubling, so n push_backs total O(n) work — fewer than 2n copies, and only about n in the typical case — giving O(1) per operation on average.
• Q: When would you prefer map over unordered_map? A: When you need sorted traversal, minimum/maximum, predecessor/successor or range queries via lower_bound, or a guaranteed O(log n) worst case instead of hashing's O(n) worst case.
• Q: What is wrong with if (m["key"] == 0) for checking a key in a map? A: operator[] inserts a default-constructed entry for a missing key, silently growing the map and changing size(); use find, count or C++20 contains.
• Q: Difference between lower_bound and upper_bound? A: lower_bound returns the first element not less than x, upper_bound the first element strictly greater than x; their difference is the number of occurrences of x.
• Q: Is std::sort stable, and what algorithm does it use? A: It is not stable; typical implementations use introsort — quicksort with a heapsort fallback for bad pivots and insertion sort for small ranges — giving worst-case O(n log n). Use stable_sort to keep the relative order of equal keys.
• Q: How do you make a min-heap with priority_queue? A: priority_queue<int, vector<int>, greater<int>> pq; — pass greater<T> as the comparator, or negate the values in a default max-heap.
• Q: Why does remove not reduce the container's size? A: Algorithms work on iterators and cannot resize the container; remove shifts the kept elements forward and returns the new logical end, so you must call v.erase(newEnd, v.end()).
• Q: When are vector iterators invalidated? A: On any reallocation (all iterators, pointers and references), and on insert/erase for every position at or after the modification point.
• Q: erase(value) on a multiset — what happens? A: It erases all elements equal to that value and returns the count; to remove one copy, erase the iterator returned by find.
• Q: Can pair<int,int> be a key in unordered_map? A: Not directly — there is no std::hash specialisation for pair; supply a custom hash functor or encode the pair into a single 64-bit integer.
• Q: How does next_permutation work and what does it return? A: It rearranges the range into the next lexicographically greater permutation and returns true; when the range is the largest permutation it resets to the sorted order and returns false — so start sorted to enumerate all n!.
• Q: Why is list usually slower than vector even for mid-list insertions? A: Each node is a separate allocation, so traversal causes cache misses and pointer chasing; vector's contiguous memory makes even O(n) shifting faster at small and moderate n.
• Q: What does nth_element guarantee? A: After the call, the element at the nth position is the one that would be there if sorted, everything before it is not greater and everything after is not less — in average O(n) time, without fully sorting.

Common mistakes

• Using a comparator with <= or >= (not a strict weak ordering) — sort may read out of bounds and crash on large inputs.
• Calling lower_bound/binary_search on an unsorted range, or using the free std::lower_bound on a set/map (it degrades to O(n) because the iterators are not random access) instead of the member function.
• Dereferencing end(), or using an iterator after push_back/insert/erase has invalidated it; forgetting that erase returns the next valid iterator.
• accumulate(v.begin(), v.end(), 0) on large values — the init type int overflows; use 0LL or a long long init.
• Calling unique without sorting first, or forgetting the erase that actually shrinks the container.
• Using m[key] for lookups inside a loop and then wondering why the map doubled in size, or taking a reference into a vector and continuing to push_back.
• Passing containers by value into functions in a tight loop (silent O(n) copy) instead of const&; relying on #include <bits/stdc++.h> or indexing stack/queue, which expose no iterators.

Related topics

Arrays and strings · Linked lists · Trees and binary search trees · Hashing and hash tables · Time and space complexity · DSA interview patterns