C++ STL Containers: vector, map, set, unordered_map

The Standard Template Library is C++‘s great strength. Pick the right container and your code is both fast and short. Pick the wrong one and you fight the data structure forever. The choice is almost always driven by access pattern, not by what feels natural.

Sequence containers

These store elements in a defined order.

• std::vector — contiguous, dynamic-size array. The default sequence container.
• std::array — fixed-size, stack-allocated. Use when the size is a compile-time constant.
• std::deque — double-ended queue with fast push/pop at both ends.
• std::list — doubly linked list. Almost never the right choice.
• std::forward_list — singly linked. Even more niche.

Default to std::vector. Modern CPUs love contiguous memory; cache locality usually beats any algorithmic edge a list has.

vector basics

#include <vector>

std::vector<int> v{1, 2, 3};
v.push_back(4);
v.emplace_back(5);          // constructs in place

for (int x : v) std::cout << x << ' ';

std::cout << v.size() << ' ' << v.front() << ' ' << v.back();

emplace_back forwards its arguments to the element constructor, saving a copy when the element type is non-trivial.

Reserve when you know the size

push_back may reallocate and copy when capacity runs out. If you know roughly how many elements are coming, call reserve first.

std::vector<int> v;
v.reserve(1'000'000);
for (int i = 0; i < 1'000'000; ++i) v.push_back(i);

This turns many reallocations into one.

Associative containers (ordered)

std::map and std::set are red-black trees: ordered, with O(log n) insert, lookup, and erase.

#include <map>
#include <set>

std::map<std::string, int> ages{{"ada", 36}, {"alan", 41}};
ages["grace"] = 60;

if (auto it = ages.find("ada"); it != ages.end()) {
    std::cout << it->second;
}

std::set<int> seen{1, 2, 3};
seen.insert(4);

Use the ordered versions when you need range queries, sorted iteration, or lower_bound/upper_bound.

Unordered associative containers

std::unordered_map and std::unordered_set are hash tables with average O(1) operations.

#include <unordered_map>

std::unordered_map<std::string, int> counts;
++counts["apple"];
++counts["apple"];
++counts["pear"];

Use the unordered versions when you only need fast lookup and do not care about order. Worst case is O(n) if all keys hash to the same bucket; for hostile inputs (web requests), consider randomized hashing.

emplace vs insert

insert takes an already-constructed element. emplace forwards its arguments to the element constructor.

std::map<std::string, std::vector<int>> by_name;

by_name.insert({"a", {1, 2}});
by_name.emplace("b", std::vector<int>{3, 4});

For map and set, emplace constructs the pair in place, saving one copy.

Iteration patterns

Range-for handles 95% of cases:

for (const auto& [key, value] : ages) {
    std::cout << key << " -> " << value << '\n';
}

The structured binding [key, value] decomposes each pair. See Modern C++ Features for more.

For index-based access, use .size() with std::size_t:

for (std::size_t i = 0; i < v.size(); ++i) std::cout << v[i];

v[i] does no bounds check; v.at(i) does and throws on out-of-range.

Removing elements

The erase-remove idiom moves unwanted elements to the end and erases them. C++20 simplifies it with std::erase and std::erase_if.

#include <vector>

std::vector<int> v{1, 2, 3, 4, 5};
std::erase_if(v, [](int x) { return x % 2 == 0; }); // removes 2, 4

For maps and sets, prefer erase directly on iterators or keys.

Complexity at a glance

• vector: random access O(1), push_back amortized O(1), middle insert O(n).
• deque: random access O(1), push/pop at either end O(1).
• map/set: insert, find, erase O(log n), ordered iteration.
• unordered_map/unordered_set: insert, find, erase average O(1).

Whenever you reach for a container, glance at this table. It will save you from list mistakes.

A worked example

Counting words in input, sorted by frequency:

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>

int main() {
    std::unordered_map<std::string, int> counts;
    for (std::string w; std::cin >> w; ) ++counts[w];

    std::vector<std::pair<std::string, int>> sorted(counts.begin(), counts.end());
    std::sort(sorted.begin(), sorted.end(),
              [](const auto& a, const auto& b) { return a.second > b.second; });

    for (const auto& [word, n] : sorted) {
        std::cout << word << ' ' << n << '\n';
    }
}

Fast counting via the hash map, then a single sort for ordering.

Common pitfalls

• Using std::list because “insertion is O(1)” — pointer chasing usually loses.
• Forgetting reserve before a big batch of push_back.
• Iterating with int instead of std::size_t and triggering signed/unsigned warnings.
• Reading m[key] for membership test — it inserts a default value if missing.

What is next

Read Smart Pointers to put owning pointers in containers safely. Then Modern C++ Features for auto, range-for, and structured bindings used heavily here.

Wrap up

std::vector is the right answer to most container questions. Reach for ordered associative containers when sort order matters, and the unordered versions when only lookup speed does. Always look at complexity before reaching for the exotic. The STL pays back time spent learning it many times over.