C++ STL Guide: Containers, Iterators and Complexity

Quick Answer

The STL gives you ready-made containers and algorithms. Use vector by default, map when you need sorted keys with O(log n) lookup, and unordered_map when you want average O(1) and do not care about order. set holds unique sorted values. Algorithms such as sort, find and lower_bound work through iterators, so one call works across containers. The two traps are map's operator[] inserting missing keys, and iterators being invalidated when a container grows.

map is not a hash table, and [] quietly inserts

Two things about std::map catch out almost everyone arriving from Python or Java. The first is that it is not a hash table. std::map is a balanced binary search tree, so lookup, insert and erase are all O(log n), and iterating it walks the keys in sorted order. The hash table in the STL is std::unordered_map. If an interviewer asks what m[key] costs on a map, the answer is logarithmic, not constant.

The second is the one that shows up as a real bug. operator[] on a map is not a read. If the key is missing, it default-constructs a value, inserts it, and hands you a reference to the new entry.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> marks;
    marks["Anita"] = 88;

    if (marks["Ravi"] > 40) {              // Ravi was never added
        std::cout << "pass\n";
    }

    std::cout << marks.size() << "\n";     // prints 2, not 1
    return 0;
}

The map now contains an entry for Ravi with value 0. Do that inside a loop over a large input file and you have doubled your memory and broken every count that comes afterwards. To ask a question without changing the container, use marks.count(key), compare marks.find(key) against marks.end(), or use marks.contains(key) if you are on C++20. This is also why operator[] refuses to compile on a const map, which is often the first clue that something is wrong.

The frequency-counting idiom freq[c]++ depends on exactly this insertion behaviour and is perfectly correct. The bug only appears when you meant to ask a question and accidentally made a statement.

vector: the default container, and the reallocation trap

std::vector should be your first choice unless you have a reason to pick something else. It stores elements contiguously, which means indexing is O(1) and, just as importantly, the hardware prefetcher can stream through it. Adding to the back with push_back is amortised O(1): when the buffer is full the vector allocates a bigger one, moves everything across, and frees the old one. Inserting or erasing anywhere other than the back is O(n), because everything after that position has to shift.

That growth step is where the trap lives. When a vector reallocates, every iterator, pointer and reference into it becomes invalid.

#include <vector>

int main() {
    std::vector<int> v{10, 20, 30};
    int& first = v[0];

    v.push_back(40);   // may reallocate: the old buffer is freed
    // first now refers to memory the vector no longer owns
    return 0;
}

Nothing warns you. The code often appears to work in a small test and corrupts memory in a bigger one. The rule is simple: do not hold a reference or iterator into a vector across any operation that can change its size.

If you know roughly how many elements are coming, call v.reserve(n) first. That allocates the capacity once, so the loop does no reallocation at all. Note that reserve changes capacity, not size: after reserve(1000) the vector still has size() == 0, and writing v[5] is undefined behaviour. If you want a thousand real elements, construct with std::vector<int> v(1000) instead. Confusing reserve with resize is a common source of segmentation faults.

map, set, unordered_map: what each one costs

Once you know the guarantees, choosing a container becomes mechanical. Here is the short version worth memorising before a placement round.

• vector: index O(1), push_back amortised O(1), insert or erase in the middle O(n), searching an unsorted vector O(n).
• map and set: insert, erase and find are O(log n). Keys stay sorted, so you can iterate in order and ask for ranges. Iterators and references stay valid when you insert, and only the erased element's iterator is invalidated.
• unordered_map and unordered_set: average O(1) for insert, erase and find, worst case O(n) when many keys land in the same bucket. Iteration order is unspecified and can differ between runs and compilers. A rehash invalidates iterators, though references to the elements themselves survive.
• multimap and multiset are the same trees but allow duplicate keys.

There is one gap that surprises people. unordered_map needs a hash function for its key type, and the standard library does not supply one for std::pair. So std::unordered_map<std::pair<int,int>, int> does not compile, while std::map<std::pair<int,int>, int> compiles fine, because pair does define operator<. If you need a hash map keyed on coordinates you either write a custom hash or pack the pair into a single long long with something like x * 1000000LL + y.

One more practical point: the constant factor on unordered_map is not small. For a few thousand elements, an ordered map or even a sorted vector is often faster in wall-clock terms despite the worse complexity, because it touches less memory.

pair, iterators and the loop that copies everything

std::pair is two values glued together, reached through .first and .second. Every element of a map is a std::pair<const Key, Value>, and that const on the key is why you cannot rename a key in place: you erase and insert instead.

An iterator is a generalised pointer. begin() gives you one pointing at the first element, end() gives you one just past the last, and you move with ++it and read with *it or it->second. Range-based for loops are sugar over exactly this, which is why the following line matters more than it looks:

for (auto entry : marks) { }        // copies every pair
for (const auto& entry : marks) { } // no copies at all

With int keys the copy is free. With std::string keys and struct values it is a heap allocation per element per pass. From C++17 you can destructure the pair, which reads much better:

for (const auto& [name, score] : marks) {
    std::cout << name << ": " << score << "\n";
}

The other iterator rule worth learning early is how to erase while looping. Erasing an element destroys its iterator, so ++it afterwards is undefined behaviour. Since C++11 the container's erase returns the next valid iterator, so the correct loop advances only in the branch that did not erase:

for (auto it = marks.begin(); it != marks.end(); ) {
    if (it->second < 35) {
        it = marks.erase(it);
    } else {
        ++it;
    }
}

Notice there is no ++it in the for header. This same shape works for vector, set and the unordered containers.

sort, find and the algorithms worth knowing

The algorithms in <algorithm> take iterators rather than containers, which is what lets one implementation serve many types. std::sort runs in O(n log n) and needs random access iterators, so it works on vector, deque and raw arrays but not on std::list, which supplies its own .sort() member. You never sort a map or set because they are already ordered.

Custom ordering comes from a comparator, usually a lambda:

#include <algorithm>
#include <string>
#include <vector>

struct Student { std::string name; int marks; };

int main() {
    std::vector<Student> students = {{"Anita", 88}, {"Ravi", 70}, {"Meera", 91}};

    std::sort(students.begin(), students.end(),
              [](const Student& a, const Student& b) {
                  return a.marks > b.marks;   // strict: use >, never >=
              });
    return 0;
}

Write >= there and you have undefined behaviour. The comparator must be a strict weak ordering, meaning it returns false when both arguments are equal. With >=, std::sort can walk off the end of the range and crash, and it usually only does so once your input is large enough for the implementation to switch strategy.

The other quiet performance bug is search. std::find is a linear scan. Calling std::find(s.begin(), s.end(), x) on a set compiles happily and throws away the entire reason you chose a set: use the member s.find(x), which is O(log n). The same applies to map. On a sorted vector, reach for std::lower_bound for a logarithmic search instead.

Beyond those, a small set covers most day-to-day work: std::max_element and std::min_element, std::count, std::reverse, std::accumulate from <numeric> for sums, and std::unique to collapse adjacent duplicates. unique only removes neighbours, so you sort first, and it does not shrink the container: it returns an iterator you pass to erase.

Frequently Asked Questions