STL Containers

The Standard Template Library provides a family of containers — each a different trade-off between access patterns, insertion cost, and memory layout. Choosing the right one is one of the most important performance decisions in C++.

std::map and std::multimap

Ordered key-value store backed by a balanced binary tree. O(log n) for all operations. Keys are unique in map; multimap allows duplicates:

#include <iostream>
#include <map>

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

    for (const auto& [name, score] : scores) {   // iterates in key order
        std::cout << name << ": " << score << "\n";
    }

    if (auto it = scores.find("Bob"); it != scores.end()) {
        it->second += 5;   // update in place
    }

    std::cout << scores.count("Dave") << "\n";   // 0 — not present
}

std::unordered_map and std::unordered_set

Hash table. O(1) average for lookups and insertions; no ordering guarantee:

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> word_freq;
for (const char* w : {"the", "cat", "sat", "on", "the", "mat"})
    word_freq[w]++;

for (const auto& [w, n] : word_freq)
    std::cout << w << ": " << n << "\n";

Use unordered_map when order does not matter and performance is critical.

std::set and std::unordered_set

Stores unique values. set is ordered (binary tree); unordered_set uses hashing:

#include <set>

std::set<int> s = {5, 3, 1, 4, 1, 5};  // duplicates dropped
for (int x : s) std::cout << x << " ";  // 1 3 4 5

s.insert(2);
s.erase(4);
std::cout << s.contains(3) << "\n";     // 1 — C++20

std::deque

Double-ended queue. O(1) push/pop at both front and back; random access:

#include <deque>

std::deque<int> dq = {2, 3, 4};
dq.push_front(1);
dq.push_back(5);
// dq: {1, 2, 3, 4, 5}
std::cout << dq.front() << " " << dq.back() << "\n";  // 1 5

std::list

Doubly linked list. O(1) insert/erase anywhere with an iterator; no random access:

#include <list>

std::list<int> lst = {1, 2, 4, 5};
auto it = std::next(lst.begin(), 2);
lst.insert(it, 3);   // insert 3 before element at index 2
// lst: {1, 2, 3, 4, 5}

Use std::list when you need stable iterators and frequent mid-sequence insertions. For most cases, std::vector is faster due to cache locality.

std::stack and std::queue

Container adapters that restrict the interface:

#include <stack>
#include <queue>

std::stack<int> stk;
stk.push(1); stk.push(2); stk.push(3);
std::cout << stk.top() << "\n";   // 3
stk.pop();

std::queue<int> q;
q.push(1); q.push(2); q.push(3);
std::cout << q.front() << "\n";   // 1
q.pop();

std::priority_queue

A max-heap by default. The largest element is always at the top:

#include <queue>

std::priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(4); pq.push(1); pq.push(5);
while (!pq.empty()) {
    std::cout << pq.top() << " ";
    pq.pop();
}
// 5 4 3 1 1

Choosing the right container