STL Containers in C++

The standard library’s containers cover nearly every data-structure need, and picking the right one matters more than any micro-optimization. The deciding factor is often memory layout: contiguous storage is fast to walk, node-based storage isn’t.

std::vector — the Default

vector is a contiguous, growable array: O(1) indexing and amortized O(1) push_back, but inserting or erasing in the middle shifts everything after it.

#include <iostream>
#include <stdexcept>
#include <vector>

void show(const char* label, const std::vector<int>& v) {
    std::cout << label;
    for (int x : v) std::cout << x << " ";
    std::cout << "(size " << v.size() << ", capacity " << v.capacity() << ")\n";
}

int main() {
    std::vector<int> v;
    v.reserve(8);
    for (int i = 0; i < 6; ++i) v.emplace_back(i * i);
    show("built:  ", v);
    v.insert(v.begin() + 2, 99);          // shifts 4, 9, 16, 25 right
    show("insert: ", v);
    v.erase(v.begin());                   // shifts everything left
    show("erase:  ", v);
    std::cout << "v[2] = " << v[2] << ", back() = " << v.back() << "\n";
    try {
        v.at(10);
    } catch (const std::out_of_range& e) {
        std::cout << "at(10): " << e.what() << "\n";
    }
}

$ g++ -std=c++20 -Wall -Wextra -o vector_ops vector_ops.cpp
$ ./vector_ops
built:  0 1 4 9 16 25 (size 6, capacity 8)
insert: 0 1 99 4 9 16 25 (size 7, capacity 8)
erase:  1 99 4 9 16 25 (size 6, capacity 8)
v[2] = 4, back() = 25
at(10): vector::_M_range_check: __n (which is 10) >= this->size() (which is 6)

reserve(8) meant no reallocation happened — capacity stayed 8 through every step. insert at position 2 shifted four elements right and erase at the front shifted all of them left; both are O(n). v[2] has no bounds check, at() does, and its libstdc++ message names both the index and the size.

emplace_back vs push_back

push_back takes an object; emplace_back takes the constructor’s arguments and builds the element in place. A logging type shows the difference:

#include <iostream>
#include <string>
#include <vector>

struct Tracer {
    std::string name;
    Tracer(std::string n) : name(std::move(n)) { std::cout << "  construct " << name << "\n"; }
    Tracer(const Tracer& o) : name(o.name) { std::cout << "  copy " << name << "\n"; }
    Tracer(Tracer&& o) noexcept : name(std::move(o.name)) { std::cout << "  move " << name << "\n"; }
};

int main() {
    std::vector<Tracer> v;
    v.reserve(4);                          // no reallocation noise below
    std::cout << "push_back(Tracer(\"a\")):\n";
    v.push_back(Tracer("a"));
    std::cout << "emplace_back(\"b\"):\n";
    v.emplace_back("b");
    Tracer c("c");
    std::cout << "push_back(c):\n";
    v.push_back(c);

    std::vector<std::string> words;
    words.emplace_back(5, 'x');            // calls std::string(5, 'x')
    std::cout << words[0] << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o emplace emplace.cpp
$ ./emplace
push_back(Tracer("a")):
  construct a
  move a
emplace_back("b"):
  construct b
  construct c
push_back(c):
  copy c
xxxxx

push_back(Tracer("a")) built a temporary and then moved it into the vector. emplace_back("b") built it directly — one line, no move. Neither helps with an existing lvalue: push_back(c) must copy, because c is still needed afterwards. words.emplace_back(5, 'x') forwards to std::string(5, 'x').

Emplacing into an aggregate (a struct with no constructor) depends on the standard:

#include <iostream>
#include <vector>

struct Point { double x, y; };             // aggregate: no constructor

int main() {
    std::vector<Point> pts;
    pts.push_back({1.0, 2.0});
    pts.emplace_back(3.0, 4.0);            // needs Point(3.0, 4.0) to be valid
    std::cout << pts[1].x << "," << pts[1].y << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o aggregate aggregate.cpp
$ ./aggregate
3,4

$ g++ -std=c++17 -Wall -Wextra -o aggregate aggregate.cpp 2>&1 | grep -m2 error
/usr/include/c++/13/bits/new_allocator.h:191:11: error: new initializer expression list treated as compound expression [-fpermissive]
/usr/include/c++/13/bits/new_allocator.h:191:11: error: no matching function for call to 'Point::Point(double)'

emplace_back(3.0, 4.0) constructs with parentheses, Point(3.0, 4.0). C++20 allows parenthesized initialization of aggregates; C++17 doesn’t, and the error surfaces deep inside the allocator header.

std::deque — Both Ends

deque adds O(1) push_front and pop_front, and still supports indexing.

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {2, 3};
    dq.push_front(1);                      // O(1) at the front too
    dq.push_back(4);
    dq.push_front(0);
    for (int x : dq) std::cout << x << " ";
    std::cout << "| dq[2] = " << dq[2] << "\n";   // still random access
    dq.pop_front();
    dq.pop_back();
    for (int x : dq) std::cout << x << " ";
    std::cout << "\n";

    int& first = dq.front();
    for (int i = 0; i < 1000; ++i) dq.push_back(i);  // grows in chunks, no relocation
    std::cout << "reference to front still valid: " << first << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o deque deque.cpp
$ ./deque
0 1 2 3 4 | dq[2] = 2
1 2 3 
reference to front still valid: 1

A deque stores elements in fixed-size chunks rather than one block, so growing never relocates existing elements: the reference to the front survived a thousand push_backs. (Iterators are invalidated by that growth; references aren’t.) A vector reference would have dangled after the first reallocation.

std::list — Doubly Linked List

Each list element is its own heap node with two pointers. Insertion and erasure at an iterator are O(1), and other iterators stay valid.

#include <iostream>
#include <iterator>
#include <list>

void show(const std::list<int>& l) {
    for (int x : l) std::cout << x << " ";
    std::cout << "\n";
}

int main() {
    std::list<int> lst{1, 2, 3, 4, 5};
    auto three = std::next(lst.begin(), 2);          // walk two nodes: O(n)
    lst.insert(three, 99);                           // O(1): new node before 3
    show(lst);
    for (int i = 0; i < 100; ++i) lst.push_front(-i);
    std::cout << "iterator still points at " << *three << "\n";   // never invalidated
    lst.erase(lst.begin(), std::next(lst.begin(), 100));
    lst.splice(lst.begin(), lst, std::prev(lst.end()));             // relink last node
    show(lst);
    lst.remove(99);
    lst.reverse();
    show(lst);
}

$ g++ -std=c++20 -Wall -Wextra -o list list.cpp
$ ./list
1 2 99 3 4 5 
iterator still points at 3
5 1 2 99 3 4 
4 3 2 1 5 

std::next(lst.begin(), 2) walks node by node — lists have no random access. After 100 push_fronts the three iterator still points at 3. splice relinks the last node to the front without copying anything, and remove/reverse are member functions because the generic algorithms can’t rearrange nodes efficiently.

The cost of nodes shows up when you walk them. Summing a million ints twenty times, with -O2:

#include <chrono>
#include <iostream>
#include <list>
#include <numeric>
#include <vector>

template <typename C>
void time_sum(const char* name, const C& c) {
    auto t0 = std::chrono::steady_clock::now();
    long long total = 0;
    for (int rep = 0; rep < 20; ++rep) total += std::accumulate(c.begin(), c.end(), 0LL);
    auto ms = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0);
    std::cout << name << ": " << ms.count() << " ms (total " << total << ")\n";
}

int main() {
    const int n = 1'000'000;
    std::vector<int> v(n);
    std::iota(v.begin(), v.end(), 0);
    std::list<int> l(v.begin(), v.end());
    time_sum("vector", v);
    time_sum("list  ", l);
}

$ g++ -std=c++20 -Wall -Wextra -O2 -o locality locality.cpp
$ ./locality
vector: 6.84115 ms (total 9999990000000)
list  : 82.5317 ms (total 9999990000000)

The totals match; the time doesn’t — the list took roughly an order of magnitude longer. Timings vary from run to run — repeated runs here put the list at about 9× to 18× the vector — but the gap stays large. The vector’s elements are adjacent, so every cache line fetched is fully used and the hardware prefetcher can stream ahead; each list node is a separate allocation reached through a pointer. Use list when you truly need stable iterators with frequent mid-sequence splicing, not by default.

std::map — Ordered Key-Value

map is a balanced tree: keys stay sorted and every operation is O(log n).

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

int main() {
    std::map<std::string, int> scores = {{"Carol", 92}, {"Alice", 95}, {"Bob", 87}};
    for (const auto& [name, score] : scores) std::cout << name << ": " << score << "\n";

    if (auto it = scores.find("Bob"); it != scores.end())
        std::cout << "found Bob: " << it->second << "\n";

    std::cout << "Dave via []: " << scores["Dave"] << "\n";   // inserts Dave = 0!
    std::cout << std::boolalpha << "size now " << scores.size() << ", contains Eve? "
              << scores.contains("Eve") << "\n";              // C++20, no insert

    auto lb = scores.lower_bound("B");                         // first key >= "B"
    auto ub = scores.upper_bound("Carol");                     // first key > "Carol"
    std::cout << "lower_bound(\"B\") = " << lb->first
              << ", upper_bound(\"Carol\") = " << ub->first << "\n";
    scores.erase("Dave");
    std::cout << "after erase: " << scores.size() << " entries\n";
}

$ g++ -std=c++20 -Wall -Wextra -o map map.cpp
$ ./map
Alice: 95
Bob: 87
Carol: 92
found Bob: 87
Dave via []: 0
size now 4, contains Eve? false
lower_bound("B") = Bob, upper_bound("Carol") = Dave
after erase: 3 entries

Iteration is in key order no matter how the map was built. The trap is scores["Dave"]: operator[] inserts a default value (0) for a missing key, so a read grew the map to 4 entries. Use find or C++20’s contains to look without inserting. Sorted keys enable range queries: lower_bound("B") finds the first key ≥ “B” (Bob), and upper_bound("Carol") the first key > “Carol” — which is the accidental Dave.

std::unordered_map — Hash Table

unordered_map hashes keys into buckets for average O(1) operations, and gives up ordering.

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> freq;
    for (const char* w : {"apple", "banana", "apple", "cherry", "banana", "apple"})
        ++freq[w];                                  // missing key starts at 0
    for (const auto& [word, count] : freq)          // order is unspecified
        std::cout << word << " -> " << count << "\n";

    std::cout << "buckets " << freq.bucket_count()
              << ", load factor " << freq.load_factor() << "\n";

    std::unordered_map<int, int> big;
    big.reserve(1000);                              // enough buckets for 1000 keys
    auto before = big.bucket_count();
    for (int i = 0; i < 1000; ++i) big[i] = i;
    std::cout << "reserved buckets " << before << ", after 1000 inserts "
              << big.bucket_count() << " (no rehash)\n";
}

$ g++ -std=c++20 -Wall -Wextra -o unordered unordered.cpp
$ ./unordered
cherry -> 1
banana -> 2
apple -> 3
buckets 13, load factor 0.230769
reserved buckets 1031, after 1000 inserts 1031 (no rehash)

++freq[w] is where operator[]’s insert-a-zero behaviour is useful. The iteration order — cherry, banana, apple — is neither insertion order nor sorted; it depends on hash values and bucket count, and can change between library versions. reserve(1000) sized the table up front (libstdc++ picks the prime 1031), so no rehash occurred during the inserts.

std::set and std::unordered_set

Sets store unique keys: sorted in set, hashed in unordered_set.

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

int main() {
    std::vector<int> data{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    std::set<int> sorted_unique(data.begin(), data.end());
    for (int x : sorted_unique) std::cout << x << " ";
    std::cout << "(" << sorted_unique.size() << " of " << data.size() << ")\n";

    auto [it, inserted] = sorted_unique.insert(4);
    std::cout << std::boolalpha << "insert 4 again: " << inserted << "\n";

    std::unordered_set<int> seen;
    for (int x : data)
        if (!seen.insert(x).second) std::cout << "duplicate " << x << "\n";

    std::multiset<int> all(data.begin(), data.end());   // keeps duplicates
    std::cout << "multiset count(5) = " << all.count(5) << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o sets sets.cpp
$ ./sets
1 2 3 4 5 6 9 (7 of 10)
insert 4 again: false
duplicate 1
duplicate 5
duplicate 3
multiset count(5) = 2

Building a set from ten values sorts and deduplicates them in one step. insert returns (iterator, bool), and the bool is the idiom for “have I seen this before?” — here reporting the three duplicates in the order they appear. multiset keeps duplicates.

Container Adapters

stack, queue and priority_queue restrict an underlying container to one access discipline.

#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

int main() {
    std::stack<int> stk;
    for (int x : {1, 2, 3}) stk.push(x);
    std::cout << "stack pops: ";
    while (!stk.empty()) { std::cout << stk.top() << " "; stk.pop(); }

    std::queue<int> q;
    for (int x : {1, 2, 3}) q.push(x);
    std::cout << "\nqueue pops: ";
    while (!q.empty()) { std::cout << q.front() << " "; q.pop(); }

    std::priority_queue<int> maxq;                             // largest first
    std::priority_queue<int, std::vector<int>, std::greater<int>> minq;
    for (int x : {5, 1, 8, 3}) { maxq.push(x); minq.push(x); }
    std::cout << "\nmax-heap:   ";
    while (!maxq.empty()) { std::cout << maxq.top() << " "; maxq.pop(); }
    std::cout << "\nmin-heap:   ";
    while (!minq.empty()) { std::cout << minq.top() << " "; minq.pop(); }
    std::cout << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o adapters adapters.cpp
$ ./adapters
stack pops: 3 2 1 
queue pops: 1 2 3 
max-heap:   8 5 3 1 
min-heap:   1 3 5 8 

stack is last-in-first-out, queue first-in-first-out. priority_queue always pops the largest element by default; passing std::greater<int> as the comparator turns it into a min-heap, the shape Dijkstra’s algorithm and schedulers need. Note that pop() returns nothing — read top() or front() first.

Structured Bindings with Containers

Map entries are pairs, and structured bindings name their parts; bindings nest.

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

int main() {
    std::map<std::string, std::pair<int, int>> grid{{"B", {3, 4}}, {"A", {1, 2}}};
    for (const auto& [key, coords] : grid) {
        const auto& [x, y] = coords;                 // nested binding
        std::cout << key << " -> (" << x << ", " << y << ")\n";
    }
    for (auto& [key, coords] : grid) coords.first *= 10;   // auto& writes through
    std::cout << "A.first now " << grid["A"].first << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o nested nested.cpp
$ ./nested
A -> (1, 2)
B -> (3, 4)
A.first now 10

The inner const auto& [x, y] = coords unpacks the pair value. With auto& on the loop, coords refers into the map, so *= 10 changed the stored data.

Container Selection Guide

When in doubt, start with vector and measure before switching.

Practice

1. In emplace.cpp, remove v.reserve(4). Which extra lines appear, and why?

   Solution

   Extra move lines appear when the vector reallocates: after construct b, a is moved into the new buffer; after copy c, a and b are moved. The new element is built in the new buffer first, then the old ones are relocated. They’re moves rather than copies because Tracer’s move constructor is noexcept.

2. Rewrite the scores["Dave"] line in map.cpp so it prints Dave: not found without inserting anything.

   Solution

   if (auto it = scores.find("Dave"); it != scores.end())
       std::cout << "Dave: " << it->second << "\n";
   else
       std::cout << "Dave: not found\n";

   size() then stays 3, and upper_bound("Carol") returns end() — dereferencing it would be undefined, so check it against scores.end() first.

3. Print the word frequencies from unordered.cpp in alphabetical order.

   Solution

   std::map<std::string, int> sorted(freq.begin(), freq.end());
   for (const auto& [word, count] : sorted) std::cout << word << " -> " << count << "\n";

   Copying into a std::map sorts by key: apple 3, banana 2, cherry 1.

4. Use a std::priority_queue of std::pair<int, std::string> to pop tasks highest-priority first.

   Solution

   std::priority_queue<std::pair<int, std::string>> tasks;
   tasks.push({2, "write"});
   tasks.push({5, "fix prod"});
   tasks.push({1, "lunch"});
   while (!tasks.empty()) {
       std::cout << tasks.top().second << "\n";
       tasks.pop();
   }

   Pairs compare by first, then second, so it prints fix prod, write, lunch.

5. Change locality.cpp to use std::deque as a third contender. Where does it land?

   Solution

   Add std::deque<int> d(v.begin(), v.end()); time_sum("deque ", d);. Expect it close to the vector and far ahead of the list: its elements are contiguous within each chunk, so most accesses are cache-friendly. Exact numbers vary by run.