STL Containers

The Standard Template Library (STL) provides robust, efficient containers. Knowing which one to use is key to writing high-performance C++.

Sequence Containers

std::vector (The Default Choice)

A dynamic array that grows automatically. The elements are stored contiguously in memory, which is friendly to CPU caches.

• Access: O(1)
• Insert at end: Amortized O(1)
• Insert in middle: O(n) (shifting elements is expensive)

graph LR
    subgraph "std::vector Memory Layout"
    direction LR
    v0["Item 0"] --- v1["Item 1"] --- v2["Item 2"] --- v3["(Reserved)"]
    end
    style v3 stroke-dasharray: 5 5

Tip: Use reserve() if you know the size in advance to avoid reallocations.

#include <vector>

std::vector<int> numbers;
numbers.reserve(100); // Pre-allocate memory
numbers.push_back(1);
numbers.emplace_back(2); // Construct in-place (more efficient)

std::deque (Double-Ended Queue)

Pronounced "deck". Similar to std::vector, but allows fast insertion/deletion at both ends. It is not contiguous in memory (it's a collection of fixed-size arrays).

• Access: O(1)
• Insert at start/end: O(1)
• Insert in middle: O(n)

graph TD
    subgraph "std::deque Structure"
    Map[Controller] --> B1[Block 1]
    Map --> B2[Block 2]
    end

    subgraph B1 [Block 1]
    d1[ ]---d2[0]---d3[1]
    end
    style d1 stroke-dasharray: 5 5

    subgraph B2 [Block 2]
    d4[2]---d5[3]---d6[4]
    end

#include <deque>

std::deque<int> d = {1, 2, 3};
d.push_front(0); // [0, 1, 2, 3] - Fast!
d.push_back(4);  // [0, 1, 2, 3, 4]

std::list (Doubly Linked List)

Elements can be scattered in memory, linked by pointers.

• Access: O(n) (No random access, must iterate)
• Insert/Delete anywhere: O(1) (if you have an iterator to the position)

graph LR
    subgraph "std::list (Doubly Linked)"
    direction LR
    N1((10)) <--> N2((20)) <--> N3((30))
    end

When to use: When you need frequent insertion/removal in the middle of the container and don't need random access.

#include <list>

std::list<int> l = {10, 20, 30};
auto it = l.begin();
++it; // Move to second element
l.insert(it, 15); // [10, 15, 20, 30] - Fast insertion

std::array (Fixed Size)

A thin wrapper around C-style arrays. Allocated on the stack (usually). - Size: Fixed at compile-time. - Size: Fixed at compile-time. - Performance: Zero overhead. Unlike std::vector, it doesn't use the heap.

graph TD
    subgraph "Memory Comparison"

    subgraph Stack
    Arr["std::array<int, 3> (On Stack)"]
    VecPtr["std::vector (Pointer on Stack)"]
    end

    subgraph Heap
    VecData["Vector Data (On Heap)"]
    end

    VecPtr -.-> VecData
    end

#include <array>

std::array<int, 3> point = {10, 20, 30};

std::string

A specialized container for text. - Small String Optimization (SSO): Short strings are stored directly in the object, avoiding heap allocation. - starts_with / ends_with (C++20): Check prefix/suffix easily.

graph TD
    subgraph "Small String Optimization (SSO)"
    S1[Short String object]
    S1Content["'Hello' (stored inside)"]
    S1 --- S1Content
    end

    subgraph "Long String (Heap Allocation)"
    S2[Long String object]
    HeapMem["'This is a very long string...' (on Heap)"]
    S2 -.-> HeapMem
    end

std::string s = "hello.txt";
std::string s_hello = "Hello"; // Renamed to avoid redefinition
if (s.ends_with(".txt")) { // C++20
    // ...
}

Associative Containers

std::map vs std::unordered_map

Feature	std::map	std::unordered_map
Implementation	Balanced Binary Tree (Red-Black)	Hash Table
Order	Sorted by Key	Undefined
Search Time	O(log n)	O(1) Average

graph LR
    subgraph "std::unordered_map (Hash Table)"
    direction LR
    Key["Key: 'Alice'"] --> HashFunc[Hash Function]
    HashFunc --> Bucket1[Bucket 1]

    Bucket0[Bucket 0]
    Bucket1[Bucket 1] --- Val1["('Alice', 100)"]
    Bucket2[Bucket 2]
    end

graph TD
    subgraph "std::map (Tree Structure)"
    Root((Bob)) --- Left((Alice))
    Root --- Right((Charlie))
    end

#include <map>
std::map<std::string, int> scores;
scores["Alice"] = 100;
scores["Bob"] = 90;
// Iterating prints Alice then Bob (Alphabetical)

// C++20: contains()
if (scores.contains("Alice")) {
    // Found! simpler than scores.find("Alice") != scores.end()
}

std::set and std::unordered_set

Similar to maps, but store unique keys only. Useful for checking if an element exists.

#include <set>

std::set<int> prime_numbers = {2, 3, 5, 7};
if (prime_numbers.contains(3)) { // C++20
    std::cout << "3 is prime!";
}
prime_numbers.insert(3); // Duplicate ignored

Multimap and Multiset

Standard maps and sets allow only unique keys. If you need multiple elements with the same key, use std::multimap or std::multiset.

#include <map>

std::multimap<std::string, int> grades;
grades.insert({"Alice", 85});
grades.insert({"Alice", 92}); // Both entries are kept

Modern Containers (C++23)

std::flat_map and std::flat_set (C++23)

These behave like maps and sets but store data in sorted vectors. This provides O(log n) search but with better cache locality and less memory overhead than node-based containers. - Trade-off: Insertion/deletion is O(n) (like vector). Use for read-heavy workloads.

std::mdspan (C++23)

A multi-dimensional view of a contiguous data array. It does not own memory but provides array-like indexing (e.g., matrix[x, y]).

#include <mdspan>
#include <vector>

std::vector<int> data(100); // 10x10 matrix linearized
auto matrix = std::mdspan(data.data(), 10, 10);
// matrix[1, 2] accesses data[1 * 10 + 2]

Pairs and Tuples

Utilities to bundle multiple values.

std::pair

Holds two values.

std::pair<int, std::string> p = {1, "Apple"};
std::cout << p.first << ": " << p.second;

std::tuple

Holds N values.

#include <tuple>
std::tuple<int, double, std::string> t = {1, 3.14, "Pi"};
std::cout << std::get<0>(t); // 1

Iterators

Iterators are objects that point to elements in a container. They generalize pointers.

• begin(): Points to the first element.
• end(): Points past the last element.

std::vector<int> v = {10, 20, 30};
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

Modern Views (Non-owning)

These are lightweight objects that refer to data owned by other containers. They prevent unnecessary copies.

std::string_view (C++17)

A read-only view of a string (or part of it).

void print_prefix(std::string_view str) {
    // No copy is made, even if passed a long std::string or char*
    std::cout << str.substr(0, 3);
}

std::span (C++20)

A view of a contiguous sequence of objects (like an array or vector).

#include <span>

void process_buffer(std::span<uint8_t> buffer) {
    for (auto& byte : buffer) {
        byte ^= 0xFF; // Invert bits
    }
}

uint8_t raw_data[1024];
std::vector<uint8_t> vec_data(500);

process_buffer(raw_data); // Works!
process_buffer(vec_data); // Works!

Container Adapters

These are wrappers around other containers (usually std::deque or std::vector) to provide a restricted interface.

• std::stack: LIFO (Last In, First Out). Think of a stack of plates.
• std::queue: FIFO (First In, First Out). Think of a line at a store.
• std::priority_queue: Elements are popped in priority order (default: largest first).

#include <stack>
#include <queue>

// Stack
std::stack<int> s;
s.push(1); s.push(2);
s.pop(); // Removes 2

// Priority Queue
std::priority_queue<int> pq;
pq.push(10); pq.push(5); pq.push(20);
// pq.top() is 20

Choosing the Right Container

Generally, default to std::vector. It's the most efficient for most cases due to data locality (CPU cache friendly).

flowchart TD
    Start([Start]) --> KV{Key-Value Pair?}

    KV -- Yes --> Order{Order Matters?}
    Order -- Yes, Sorted --> Map[std::map]
    Order -- No --> UMap[std::unordered_map]

    KV -- No --> Process{Processing Order?}

    Process -- LIFO --> Stack[std::stack]
    Process -- FIFO --> Queue[std::queue]
    Process -- Priority --> PQueue[std::priority_queue]
    Process -- Both Ends --> Deque[std::deque]

    Process -- None --> Middle{Insert in Middle?}

    Middle -- Yes --> List[std::list]

    Middle -- No --> Size{Fixed Size?}
    Size -- Yes --> Array[std::array]
    Size -- No --> Vector[std::vector]

    style Vector fill:#bbf,stroke:#333,stroke-width:2px