Chapter 17: Containers and Iterators

The Standard Library containers give you ready made data structures with predictable complexity and value semantics. They pair with iterators, which act like generalized pointers. Together they power generic algorithms; you provide a container, an iterator range, and a policy, then the library does the work efficiently and safely.

Sequence containers

Sequence containers store elements in a specific order and let you access them by position or by traversal. Each choice trades constant factors and iterator capabilities for different workloads. Pick the one that matches your insertion and access patterns, then let algorithms operate on iterator pairs.

vector for contiguous growth

std::vector<T> owns a contiguous block; random access is constant time and cache friendly. Inserting or erasing at the end is amortized constant time; inserting in the middle moves a tail. Reallocation invalidates all iterators and references; push back may trigger it.

std::vector<int> v;
v.reserve(1024);
for (int i = 0; i < 10; ++i) v.push_back(i);
v[3] = 42;  // random access

deque for fast ends

std::deque<T> provides constant time push and pop at both ends with stable references across many operations. It is not one flat array; it is a map of blocks that still offers random access. Choose it for queue like workloads with frequent front operations.

std::deque<int> d{1,2,3};
d.push_front(0);
d.push_back(4);
int x = d[2];  // random access still works

list and forward_list for splicing

std::list<T> is a doubly linked list; std::forward_list<T> is a singly linked list with minimal overhead. They keep iterators valid on insert and erase of other elements, and they offer splice to move nodes between lists without allocation. Traversal is linear and cache locality is poor, so use them when stable node addresses and constant time splicing matter.

std::list<int> a{1,2,3}, b{4,5};
auto it = std::next(a.begin());  // points at 2
b.splice(b.end(), a, it);        // move 2 into b by relinking

Complexity and invalidation summary

Operations differ across sequence containers, especially for insertions and iterator invalidation. The following quick reference helps match structure to workload.

Associative containers: set, map, multiset, multimap

Associative containers organize elements as ordered trees keyed by a comparator. Lookups, inserts, and erases are logarithmic and iterators traverse keys in sorted order. set and map enforce unique keys; the multi versions allow duplicates.

Ordered lookup and hints

Typical operations include find, lower_bound, and range erasure. Insertion can accept a position hint; when correct, the tree can link in the node with minimal work. Value types are Key for set and std::pair<const Key, T> for map.

std::map<std::string, int> m;
m.emplace("alpha", 1);
m.try_emplace("beta", 2);
auto it = m.lower_bound("beta");
m.emplace_hint(it, "beta", 3); // efficient when near the right spot

Ranges and node handles

Node extraction lets you move elements between containers without copy. The extracted node preserves allocation and key; you can modify the key of a map node before reinsertion. Range overloads accept iterator pairs and integrate well with modern algorithms.

auto nh = m.extract("alpha");
if (nh) {
  nh.key() = "aleph";
  m.insert(std::move(nh));
}

Unordered containers and hashing

Unordered containers are hash tables that trade order for expected constant time lookup. Buckets group elements by hash; equal keys reside in the same bucket. Performance depends on load factor, hash quality, and equality comparison.

unordered_set and unordered_map

The interfaces mirror the ordered versions, with bucket level tools for diagnostics. Reserve to reduce rehashing and keep the load factor near a value that suits your workload. Supplying robust hash and equals is essential for custom keys.

std::unordered_map<std::string, int> um;
um.reserve(1024);
um["tea"] = 1;
um["coffee"] = 2;
if (auto it = um.find("tea"); it != um.end()) { /* use it */ }

Custom keys and hash specializations

For your own types, provide a hasher and an equality predicate that agree on equivalence. Combine member hashes using simple integer mixing. Keep equality consistent with the fields you hash; otherwise lookups will miss matches.

struct Point { int x; int y; };

struct PointHash {
  std::size_t operator()(const Point& p) const noexcept {
    std::size_t h1 = std::hash<int>{}(p.x);
    std::size_t h2 = std::hash<int>{}(p.y);
    return h1 ^ (h2 + 0x9e3779b9u + (h1 << 6) + (h1 >> 2));
  }
};

struct PointEq {
  bool operator()(const Point& a, const Point& b) const noexcept {
    return a.x == b.x && a.y == b.y;
  }
};

std::unordered_set<Point, PointHash, PointEq> ps;

Container adaptors

Adaptors expose restricted interfaces built on underlying sequence containers. They enforce specific access patterns and hide operations that would violate the abstraction. You can choose the base container when constructing the adaptor to fit your needs.

stack and queue basics

stack is last in, first out; queue is first in, first out. By default they use deque; you may switch to vector when middle insert is unnecessary and you prefer contiguous storage.

std::stack<int, std::vector<int>> st;
st.push(1); st.push(2);
int t = st.top(); st.pop();

priority_queue for heaps

priority_queue maintains a heap where top returns the largest element under a comparator. It supports push, emplace, pop, and top. For bulk construction, build a vector then call std::make_heap for linear time setup.

std::priority_queue<int> pq;
for (int v : {3,1,4,1,5}) pq.push(v);
int best = pq.top();  // 5

Iterators and iterator categories

Iterators act like generalized pointers that traverse ranges. Categories describe what operations are valid and how algorithms may step. The stronger the category, the more algorithms apply and the more efficient they can be. Since C++20 there is also the contiguous category for memory linearity.

Categories and capabilities

The table lists classic categories plus contiguous, with typical operations and examples. Use category aware algorithms; for example std::advance runs in constant time for random access and linear time for forward.

template<class It>
void skip_even_positions(It first, It last) {
  using cat = typename std::iterator_traits<It>::iterator_category;
  if constexpr (std::is_base_of_v<std::random_access_iterator_tag, cat>) {
    for (; first < last; first += 2) { /* … */ }
  } else {
    bool keep = true;
    for (; first != last; ++first) { if (keep) { /* … */ } keep = !keep; }
  }
}

Iterator adaptors and sentinels

Adaptor types modify traversal without copying data. Examples include std::reverse_iterator, std::move_iterator, and the C++20 range based sentinels where end is a different type from the iterator. These parts stack with algorithms to express intent cleanly.

std::vector<int> v{1,2,3};
std::copy(std::make_move_iterator(v.begin()),
          std::make_move_iterator(v.end()),
          std::ostream_iterator<int>(std::cout, " "));

Allocators and memory resource

Allocators abstract memory acquisition so containers can adapt to different strategies. The classic allocator model uses types like std::allocator<T>; the polymorphic model in std::pmr routes allocations through runtime selected resources that match a use case.

Classic allocators

Every standard container template parameterizes on an Allocator type. Custom allocators let you count bytes, place objects in shared arenas, or map storage to special regions. Correctness requires honoring the allocator interface; performance depends on your allocation pattern more than micro details.

template<class T>
struct CountingAlloc {
  using value_type = T;
  static inline std::size_t bytes = 0;
  T* allocate(std::size_t n) {
    bytes += n * sizeof(T);
    return static_cast<T*>(::operator new(n * sizeof(T)));
  }
  void deallocate(T* p, std::size_t) noexcept { ::operator delete(p); }
};
std::vector<int, CountingAlloc<int>> v;
v.resize(100);

std::pmr and polymorphic resources

Polymorphic memory resources decouple container type from allocation policy at runtime. Use std::pmr::monotonic_buffer_resource for arena style growth, std::pmr::unsynchronized_pool_resource for small block pooling, and wrap containers in their pmr aliases.

std::byte buf[4096];
std::pmr::monotonic_buffer_resource pool{buf, sizeof buf};
std::pmr::vector<std::pmr::string> names{&pool};
names.emplace_back("Ada");
names.emplace_back("Bjarne");

Choosing a resource strategy

Pick monotonic arenas for build once, destroy together lifetimes; pick pool resources for steady churn of small objects; fall back to the default new delete resource when allocations are infrequent. Measure real code with realistic data; allocation profiles often surprise.