Containers

Containers provide storage for collections of objects. The Standard Library supplies a family of containers that differ in allocation strategy, ordering guarantees, and performance characteristics. Choose a container that matches the required usage pattern. The default choice is std::vector because it stores elements contiguously, which gives good cache locality and enables constant‑time random access.

std::vector: the default container

std::vector<T> owns a dynamically allocated array of T. Elements are stored next to each other in memory. The implementation allocates a capacity that can be greater than the current size. When the size grows past the capacity, the vector allocates a new, greater block, copies or moves existing elements, and frees the old block. This reallocation invalidates all pointers, references, and iterators that refer to the previous storage.

Because reallocation can be expensive, two techniques reduce its impact:

• Reserve: call reserve(10) before inserting ten or greater number of elements. The vector allocates space for at least n elements up front, so later push_back or emplace_back calls cannot trigger a reallocation.
• Emplace: emplace_back(args…) constructs a new element directly in the storage. The arguments are forwarded to the element’s constructor, avoiding an extra copy or move.

Both techniques tie back to earlier chapters. Chapter 07 described the lifetime‑safety analysis that flags dangling pointers after a reallocation. Reserving ahead of time eliminates that risk for the most common case. Chapter 08 explained why passing arguments by value or reference matters. emplace_back constructs in place, satisfying the principle of “construct where you use”.

The vector grows geometrically, typically doubling capacity. This yields amortised constant‑time push_back. Use reserve when the final size is known to avoid intermediate reallocations and iterator invalidation.

Erasing an element from the middle of a vector shifts every later element down by one, so removal is O(n) in the number of elements after the erased position. erase and the C++20 erase/erase_if free functions return the new logical end. When you only need to drop the last few elements, pop_back or resize is cheaper.

std::vector<bool> is a partial specialization that packs bits, so operator[] returns a proxy object rather than a bool&. This breaks generic code that expects a real reference, and it is the one standard container that is not a true container. Prefer std::vector<char> or std::bitset when you need a sequence of individual bit values with normal reference semantics.

#include <vector>
#include <print>

int main() {
    std::vector<int> v;
    v.reserve(10);
    v.emplace_back(1);
    v.emplace_back(2);
    v.emplace_back(3);
    std::println("vector size: {}", v.size());
    return 0;
}

std::array: fixed size on the stack

std::array<T, N> stores exactly N objects of type T. The size is known at compile time, and the array lives in the surrounding object’s storage, which is the stack for local variables. No dynamic allocation occurs.

A classic C array (T a[N]) decays to a pointer when passed to a function, losing its size information. std::array retains its size via the member function size(). It also provides standard container interfaces (begin(), end(), operator[]), so generic algorithms work uniformly.

#include <array>
#include <print>

int main() {
    std::array<int,5> a{{1,2,3,4,5}};
    std::println("array size: {}", a.size());
    std::println("first element: {}", a[0]);
    return 0;
}

The example fills an std::array<int,5> with the values 1 through 5, prints the size, and prints the first element.

std::array is an aggregate, so it can be copy‑assigned and returned by value with no hidden allocation, and its size is part of the type. Prefer it over std::vector when N is small and fixed, because the data sits in the parent object with no pointer chase. Reach for std::vector once the size is dynamic or larger than a few dozen elements.

Sequence containers with different insertion properties

All three store elements non‑contiguously. The lack of cache locality makes them slower for tight loops that iterate over a large number of elements. Use them only when the insertion pattern outweighs the cache penalty.

// Example of a deque that pushes at both ends.
std::deque<int> dq;
for (int i = 0; i < 5; ++i) dq.push_back(i);
for (int i = 5; i < 10; ++i) dq.push_front(i);

A std::deque stores elements in fixed‑size chunks rather than one block, which is why pushing at the front never moves the existing elements and never invalidates their iterators. The trade‑off is a double indirection on access and a larger per‑element overhead than vector.

Ordered associative containers: std::map and std::set

std::map<Key, Value> and std::set<Key> are implemented as red‑black trees. They keep keys in sorted order defined by operator< (or a custom comparator). Lookup, insertion, and removal take O(log n) time. Iterators remain valid across insertions and deletions, except when the element itself is erased.

Use these containers when ordered iteration, range queries, or stable iterator validity are required.

Use operator[] to find or insert, and at() when a missing key must raise std::out_of_range instead of creating a default. The ordering follows operator< on the key by default. A custom comparator changes both the order and the equality test. std::multimap and std::multiset permit duplicate keys when that is needed.

std::set stores keys only and is the right choice when you need a sorted, deduplicated collection rather than key‑value pairs. Both map and set gain a contains member in C++20 that tests membership without constructing an iterator.

std::map<std::string, int> word_counts;
word_counts["apple"] = 3;
word_counts["banana"] = 5;
for (const auto& [w, c] : word_counts) {
    std::println("{}: {}", w, c);
}

Unordered associative containers: std::unordered_map and std::unordered_set

std::unordered_map<Key, Value> and std::unordered_set<Key> are hash tables. Average‑case lookup, insertion, and removal are constant time. The containers do not preserve any ordering of keys. The key type must be hashable. The standard library provides std::hash for fundamental types and for std::string. Custom types need a specialization of std::hash and an equality operator.

Because hash tables store elements in buckets, iterator invalidation rules differ from ordered containers: inserting does not invalidate iterators, but rehashing (which can occur when the load factor exceeds a threshold) invalidates all iterators.

An unordered_map has a higher per‑operation constant cost than a vector search over tiny sets, and it allocates buckets, so prefer it only once the keyed lookup actually pays off. reserve and max_load_factor let you tune the bucket count before a bulk insert.

Iteration order over an unordered_map is not specified and can change between runs, so never depend on it. The contains member tests membership in average constant time.

std::unordered_map<int, std::string> id_to_name{{1, "Alice"}, {2, "Bob"}};
if (auto it = id_to_name.find(1); it != id_to_name.end()) {
    std::println("Found {}", it->second);
}

std::span: a non‑owning view over contiguous data

A std::span<T> is a lightweight object that refers to a contiguous sequence of T. It does not own the elements. It only stores a pointer and a length. Because it is non‑owning, it can be created from multiple sources: a std::vector<T>, a std::array<T, N>, or a raw C array.

Using std::span allows algorithms to accept any of those sources without copying. The container’s lifetime must outlive the span. Otherwise the span becomes dangling, which the lifetime‑safety analysis flags.

#include <vector>
#include <array>
#include <span>
#include <print>

void print_span(std::span<const int> s) {
    std::print("span elements:");
    for (int v : s) {
        std::print(" {}", v);
    }
    std::println("");
}

int main() {
    std::vector<int> v{1, 2, 3};
    std::array<int,3> a{{4,5,6}};
    print_span(v);
    print_span(a);
    return 0;
}

The print_span function takes a std::span<const int> and prints each element. The main function calls it with a std::vector<int> and an std::array<int,3>, demonstrating the uniform interface.

A std::span can carry a compile‑time extent (std::span<T, N>) or a dynamic one. The static form lets the compiler prove bounds in some algorithms. first, last, and subspan produce new spans over subranges without copying, which is how zero‑copy parsing pipelines stay allocation free.

A span exposes size, empty, and data, and it converts to a std::vector only through an explicit constructor, never by accident. This keeps ownership explicit at every call site.

Choosing the right container

When you start a new piece of code, follow this decision guide:

1. Begin with std::vector. Its contiguous storage gives the best cache performance for most workloads.
2. Switch to std::array if the number of elements is known at compile time and the total size fits within typical stack limits (e.g., ≤ 1 KB).
3. Select an associative container when you need O(1) average‑case lookup by key. Choose std::map if you require ordered iteration or range queries. Choose std::unordered_map for constant‑time performance when ordering does not matter.
4. Consider std::deque only when you need efficient insertion or removal at both ends and cannot accept the iterator invalidation of a vector during growth.
5. Use std::list or std::forward_list only when you must insert or erase frequently in the middle of a large sequence and the cache penalty is tolerable.
6. Use std::span to write generic algorithms that operate on any contiguous view without taking ownership.

Prefer contiguous, owning containers such as std::vector (default) or std::array when size is fixed. Use std::span for non‑owning views and std::pmr allocators to customise allocation without changing the container type. The same cache‑locality reasoning applies to std::string, while std::string_view follows the view pattern described earlier.

Try this

Write a program that:

1. Declares a std::vector<int>.
2. Calls reserve(10).
3. Uses emplace_back to add the values 1, 2, 3.
4. Creates a std::span<int> that references the vector.
5. Computes and prints the sum of the elements in the span.

No solution is provided. The reader must fill in the code.