STL Containers in C++

STL Containers in C++

The Standard Template Library provides battle-tested, generic containers that cover nearly every data structure need. Choosing the right container is often the single biggest factor in code performance — the difference between vector and list can be 10x on real workloads because of how modern CPUs work. Cache misses cost ~200 cycles each; a linked list incurs one on every element access, while a contiguous vector keeps everything in the same cache lines. This tutorial walks through each major container, its internals, and when to reach for it.

std::vector — Your Default Container

vector stores elements contiguously in heap memory, exactly like a dynamic array. This layout is cache-friendly: iterating a vector is as fast as iterating a plain array because sequential memory accesses are prefetched by the CPU. Random access is O(1), and push_back amortizes to O(1) by doubling capacity on reallocation. It is the right default for almost every sequence use case.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v;
    v.reserve(100);          // allocate capacity upfront — eliminates all reallocations

    for (int i = 0; i < 10; ++i)
        v.emplace_back(i * i); // construct in-place — no copy or temporary

    // Random access: O(1) — same cost as a C array
    std::cout << v[4] << "\n";       // 16 — no bounds check
    std::cout << v.at(4) << "\n";    // 16 — bounds-checked, throws on out-of-range

    // Insert in the middle: O(n) — shifts all subsequent elements
    v.insert(v.begin() + 3, 99);

    // Erase: O(n) — shifts elements to fill the gap
    v.erase(v.begin() + 3);

    std::cout << "size=" << v.size() << " capacity=" << v.capacity() << "\n";
}

Call reserve() when you know the final size to eliminate all reallocations.

emplace_back vs push_back

push_back takes a constructed object and moves it in. emplace_back takes constructor arguments and constructs the object directly in the vector’s storage — no temporary, no move. The difference matters for types with expensive constructors or types that are not movable.

#include <vector>
#include <string>

struct Point { double x, y; };

int main() {
    std::vector<Point> pts;

    // push_back: constructs a Point temporary, then moves it into the vector
    pts.push_back(Point{1.0, 2.0});

    // emplace_back: forwards arguments directly to Point's constructor in-place
    pts.emplace_back(3.0, 4.0);  // zero copies, zero temporaries

    std::vector<std::string> words;
    words.emplace_back(10, 'x'); // calls string(10, 'x') in-place — "xxxxxxxxxx"
}

std::deque — Double-Ended Queue

deque gives O(1) push and pop at both front and back. This is the one operation where vector falls short — pushing to the front of a vector is O(n) because every element must shift. Internally deque uses a sequence of fixed-size chunks rather than one contiguous block, so it avoids full reallocation but is slightly less cache-friendly than vector.

#include <deque>

std::deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_front(0);    // O(1) — vector cannot do this efficiently
dq.pop_front();      // O(1)

Use deque when you need efficient insertion at both ends. It backs std::stack and std::queue.

std::list — Doubly Linked List

Each node in list holds a value plus two pointers. Insertion and erasure at any iterator position are O(1), but random access is O(n) and cache behavior is poor — every node is a separate heap allocation, causing cache misses on every traversal. In most scenarios vector wins decisively due to cache effects.

#include <list>

std::list<int> lst{1, 2, 3, 4, 5};

auto it = lst.begin();
std::advance(it, 2);         // O(n) — no random access
lst.insert(it, 99);          // O(1) insertion — existing iterators remain valid
lst.erase(it);               // O(1) erasure
lst.splice(lst.begin(), lst, std::prev(lst.end())); // move a node — O(1), no copies

The main use case for list: you hold iterators into the container and need them to remain valid across insertions and erasures elsewhere in the list. In most other scenarios, vector wins due to cache effects.

std::map — Ordered Key-Value Store

map is a red-black tree where keys are always sorted. It gives O(log n) lookup, insertion, and erasure. The sorted order is its key benefit over unordered_map: you get ordered iteration, and operations like lower_bound that find the nearest key are only possible on an ordered structure.

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

int main() {
    std::map<std::string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"]   = 87;
    scores["Carol"] = 92;

    // Iteration is always in key-sorted order — guaranteed
    for (const auto& [name, score] : scores)   // C++17 structured bindings
        std::cout << name << ": " << score << "\n";

    // Find: O(log n) — returns end() if not found
    if (auto it = scores.find("Bob"); it != scores.end())
        std::cout << "Found Bob: " << it->second << "\n";

    // Lower bound: first key >= "B" — only possible with ordered containers
    auto lb = scores.lower_bound("B");
    std::cout << lb->first << "\n"; // Bob
}

std::unordered_map — Hash Table

unordered_map provides average O(1) lookup, insertion, and erasure by using a hash table. It is typically faster than map for large collections when you only need point lookups and don’t care about ordering. The tradeoff is that worst-case performance degrades to O(n) with a bad hash function, and there is no ordered iteration.

#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> freq;

    // Count word frequencies — each lookup and insert is O(1) average
    for (const char* word : {"apple", "banana", "apple", "cherry", "banana", "apple"})
        ++freq[word];

    // Reserve buckets upfront to avoid rehashing as the map grows
    std::unordered_map<std::string, int> big;
    big.reserve(1000);
    big.max_load_factor(0.7f);

    for (const auto& [word, count] : freq)
        std::cout << word << " -> " << count << "\n";
}

Prefer unordered_map over map when you don’t need sorted iteration and average-case performance matters more than worst-case guarantees.

std::set and std::unordered_set

set and unordered_set are the key-only equivalents of map and unordered_map. They are the natural tools for membership tests and deduplication — operations that come up constantly in algorithms and data processing.

#include <set>
#include <unordered_set>
#include <vector>

std::vector<int> data{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

// Deduplicate and sort in one step — set maintains sorted order
std::set<int> unique(data.begin(), data.end());
// {1, 2, 3, 4, 5, 6, 9}

// Deduplicate without sorting — faster lookup for membership tests
std::unordered_set<int> fast(data.begin(), data.end());
bool found = fast.count(5) > 0; // true

Container Adapters: stack and queue

std::stack and std::queue are thin wrappers that restrict access to enforce a specific access discipline. They are important not just for the data structure itself, but because using them in code explicitly communicates that you intend LIFO or FIFO semantics — making the code’s intent clearer than using a raw deque or vector.

#include <stack>
#include <queue>

std::stack<int> stk;
stk.push(1); stk.push(2); stk.push(3);
stk.top();   // 3 — LIFO: last pushed is first accessed
stk.pop();

std::queue<int> q;
q.push(1); q.push(2); q.push(3);
q.front();  // 1 — FIFO: first pushed is first accessed
q.pop();

Both default to deque as their underlying container; you can change it: std::stack<int, std::vector<int>>.

Container Selection Guide

When in doubt, start with vector. Profile before switching.

C++17 Structured Bindings with Containers

Structured bindings make iterating over maps and pairs much cleaner by letting you name both halves of each entry directly, eliminating the noisy .first/.second pattern.

#include <map>
#include <tuple>

std::map<std::string, std::pair<int,int>> grid{
    {"A", {1, 2}},
    {"B", {3, 4}},
};

for (const auto& [key, coords] : grid) {
    const auto& [x, y] = coords;   // nested structured binding
    std::cout << key << " -> (" << x << ", " << y << ")\n";
}

Structured bindings also work with std::array, plain arrays, and any type with a get<> specialization.