This is the central index for the C++ containers series. The goal is to keep the overview short and link to focused notes for each container family.

The series uses C++20 as its default teaching baseline. Operations introduced in C++20 or later are labelled where they appear; the core containers and most of their interfaces are available in earlier standards.

Core Sequence Containers

1. Vector and String
2. Deque and Sliding Windows
3. List and LRU Patterns

Associative Containers

1. Maps and Hashing
2. Sets and Multisets

Container Adapters

1. Queue, Stack, and Priority Queue

Iterator Rules

1. Iterators and Invalidation

Container Selection

Complexity is only one selection criterion. Also consider:

• Access pattern: indexed access, sequential traversal, ordered lookup, or membership only.
• Storage: contiguous elements improve locality and interoperability with pointer-based APIs; node-based containers provide stable element addresses at an allocation cost.
• Ordering: ordered associative containers support bounds and range traversal; unordered containers do not.
• Mutation: insertion and erasure may invalidate iterators, references, and pointers differently.
• Cardinality: choose a unique-key or duplicate-key container deliberately.
• Workload evidence: constant factors, allocation volume, key distribution, and cache behavior can outweigh asymptotic notation.

Complexity Summary

Engineering Checklist

• Use vector when index access and traversal are central.
• Use unordered_map or unordered_set when fast lookup is central and order does not matter.
• Use map, set, or multiset when sorted order or range queries matter.
• Use queue for FIFO work and stack for LIFO work when their restricted interfaces express the intended invariant.
• Use priority_queue for repeated best/min/max extraction.
• Use deque when efficient mutation at both ends is required.
• Use list only when stable iterators or node movement matter.
• Be careful: map[key] and unordered_map[key] insert default values when the key is missing.
• Be careful: vector reallocation invalidates existing pointers, references, and iterators.
• Check empty-container preconditions before front, back, top, or pop when emptiness is possible.
• Treat complexity tables as a starting point, then measure representative data and operations.

Further Reading

• C++ working draft: containers library