C++ Containers and Iterators

Choose a container from the required lookup, traversal, insertion, erasure, memory locality, and reference-stability properties. Complexity describes an operation under its preconditions; invalidation and ownership determine whether a design remains correct after mutation.

Selecting a Container #

• std::vector is the default sequence for contiguous storage, random access, cache locality, and C interoperation through data(). Appending is amortized constant time. Any capacity growth invalidates every iterator, pointer, and reference; without growth, insertion invalidates iterators and references at or after the insertion point.
• std::deque supports indexed access. End insertion invalidates iterators but not references; its storage is non-contiguous, and middle insertion invalidates iterators and references.
• std::list and std::forward_list retain iterators and references to unaffected nodes across insertion and erasure. Their node allocation and pointer chasing make them a measured choice, not a default.
• std::map and std::set provide ordered traversal and logarithmic lookup. Insertion does not invalidate iterators or references, except erased elements.
• std::unordered_map and std::unordered_set provide average constant-time lookup. Rehash invalidates iterators, although references and pointers to elements remain valid; erasing invalidates only the erased element.

reserve() avoids predicted vector reallocations and can also reduce unordered_* rehashing. It does not make an iterator valid after an operation whose documented rules invalidate it.

Inserting and Transferring Values #

insert accepts an element or range, while emplace constructs an element from arguments in the container’s storage:

#include <string>
#include <utility>
#include <vector>

std::vector<std::string> names;
std::string name = "Ada";

names.push_back(name);            // copies; name remains owned by the caller
names.push_back(std::move(name)); // moves; name stays valid but has unspecified value
names.emplace_back(3, 'x');       // constructs "xxx" in the vector

When an object already exists, insert or push_back(std::move(value)) makes ownership transfer visible. emplace avoids forming a temporary only when its constructor arguments are available; it is neither universally faster nor a substitute for validating the element constructor. Associative emplace may construct and discard an element when a key already exists. try_emplace avoids constructing the mapped value in that duplicate-key case, and insert_or_assign states the replacement policy.

For node-based containers, extract produces a node handle that owns the removed node until it is inserted or destroyed. It can transfer compatible nodes without moving their contained value, but allocator compatibility and the container’s documented preconditions still apply.

Iterators and Preconditions #

Algorithms declare the iterator category they need. Input iterators are single-pass; forward iterators are multipass; bidirectional iterators add decrement; random-access iterators add arithmetic and ordering; contiguous iterators additionally denote adjacent storage. Pass the category an algorithm requires rather than assuming an iterator from one container behaves like another.

Validate range preconditions before calling an algorithm or container member:

auto first = values.begin();
auto last = values.end();
if (first != last) {
    values.erase(first); // `first` is valid and dereferenceable
}

end() is a sentinel, not an element. Never dereference it, and do not compare iterators from different containers except where an API explicitly permits it. Read the specific container’s invalidation table before retaining an iterator across mutation; range-for loops and standard algorithms reduce manual iterator handling but do not suspend those rules.