Containers

Default to vector for cache-friendly iteration. Use map/set for sorted O(log n) lookup, unordered_map/set for average O(1) without ordering, and list only when stable iterators or O(1) splice outweigh cache locality.

Use std::array<T, N> for compile-time fixed sizes — stack allocation, zero-overhead C-array wrapper. Use std::vector<T> for runtime-dynamic sizes or large buffers; it owns a heap block with capacity-based growth.

vector::erase invalidates it and every iterator after it; the next ++it then advances a dangling iterator — UB. Fix: use the return value, it = v.erase(it);, and only ++it when you did not erase. Or std::erase_if(v, pred); (C++20).

Invalidation means an iterator no longer points to a valid element after a mutation. Vector reallocation invalidates everything; list/map insert keeps iterators valid; unordered_map rehash invalidates iterators.

push_back can reallocate the vector's storage when it grows past capacity, invalidating p, which now dangles — UB. Pointers, references, and iterators into a vector are invalidated by reallocation. Fix: re-acquire p after the insert, or reserve capacity up front.

reserve(n) grows capacity() to at least n without constructing elements — useful before a known series of push_backs. resize(n) changes size() to n, value-initialising new elements and destroying excess ones.

Both are adapters that wrap an underlying sequence container (default std::deque) and expose a restricted interface. std::stack gives LIFO push/pop/top; std::queue gives FIFO push/pop/front/back.

std::deque is a page table of pointers to fixed-size chunks: O(1) push/pop on both ends, random access, non-contiguous storage. End push/pop invalidates iterators but keeps references valid; middle insert invalidates everything.

emplace_back(args...) builds the element in place from constructor args, skipping a temporary that push_back(T(a,b)) would create. With an existing T, push_back(std::move(x)) is equivalent and clearer.

Use container.empty() — it is O(1) for all standard containers (including pre-C++11 std::list where size() was O(n)) and expresses the intent directly.

Specialise std::hash<MyKey> in namespace std, or pass a hash callable as the second template argument. Combine fields with hash_combine (not trivial XOR) and provide a consistent operator==.

std::list<T> is a doubly-linked list of individually heap-allocated nodes (value + prev + next pointers) with a sentinel head/tail. O(1) insert/erase anywhere, poor cache locality, O(1) size() since C++11.

std::map is a red-black tree: O(log n) ops, sorted iteration, needs only operator<. std::unordered_map is a hash table: O(1) average (O(n) worst), arbitrary order, needs operator== plus a hash.

Default is a max-heap using std::less<T> over vector<T>; for a min-heap pass std::greater<T> as the comparator. Push/pop are O(log n) via push_heap/pop_heap; top is O(1).

std::remove only shifts non-matching elements forward and returns the new logical end; the tail is unspecified. Call container.erase(new_end, end()) to actually drop the tail — remove cannot do it because it works on any range.

std::string_view (C++17) is a non-owning pointer+length view over a character buffer. It does not extend lifetime: a view bound to a temporary std::string is dangling immediately, so never store it past the source's life.

unordered_map uses separate chaining — each bucket is a linked list of colliding nodes. The bucket API (load_factor, max_load_factor, rehash) tunes when rehash fires; rehash invalidates all iterators.

Standard erase(it) is O(n) because it shifts subsequent elements left. If order is unimportant, use swap-and-pop: swap with the last element and call pop_back() — O(1).

Three pointers (begin, end, end_of_storage) over a contiguous heap block. On overflow a 2x block is allocated, elements move (if noexcept) or copy, then the old block is freed — amortising push_back to O(1).

Six categories: input/output (single-pass), forward (forward_list), bidirectional (list, set, map), random-access (vector, deque, array), and C++20 contiguous (vector, array, string, span).

C++11 mandates O(1) size() via a cached counter; pre-C++11 it was implementation-defined and often O(n). The trade-off: full-list splice became O(n) because the count must be updated.

std::set stores unique keys; insert returns pair<iter, bool> with false for duplicates. std::multiset allows duplicates and always succeeds; use it when duplicates are meaningful and equal_range to walk matches.

Pass a custom allocator as the container's template parameter — it must provide value_type, allocate, deallocate (or use allocator_traits defaults). C++17 std::pmr offers polymorphic memory resources without re-templating.

A ForwardIterator must provide operator*, prefix operator++, operator==/!=, a copy constructor, plus the type aliases (iterator_category, value_type, difference_type, pointer, reference) via nested types or iterator_traits.

shrink_to_fit() is a non-binding request to release unused capacity — implementations may ignore it. The portable fallback is the swap idiom: std::vector<T>(v).swap(v).

std::span<T> (C++20) is a non-owning pointer+length view over any contiguous range. Use it as a function parameter to accept vector, array, or C arrays uniformly without templates; the buffer must outlive the span.

Both are contiguous, but std::string adds a guaranteed null terminator (c_str() is O(1)), small-string optimisation, text APIs (find, substr), and char_traits. vector<char> has none of these — use string for text.

The Allocator template parameter controls a container's memory source via allocate/deallocate. Write a custom one for arena/pool/NUMA/instrumentation; C++17 std::pmr::polymorphic_allocator swaps behaviour at runtime.

std::set/std::map are red-black trees: O(log n) ops, stable iterators on insert. std::unordered_map is a separate-chaining hash table: O(1) average, O(n) worst case if std::hash collides badly.

std::flat_map<K, V> (C++23) is a sorted contiguous container (two parallel vectors): O(log n) binary-search lookup with cache locality beating std::map, but O(n) insert/erase. Best for read-heavy workloads.

SBO embeds a fixed inline buffer of N elements; while size() ≤ N no heap allocation occurs, above it falls back to dynamic. Trade-off: skips heap for small sizes but sizeof(container) grows by N * sizeof(T).