The sequence/view foundation, linked lists and hash containers explain the mechanisms. This extension practices the actual library operations and the promises callers can rely on. An algorithm can return correct values and still break a caller by invalidating its pointers.
Start with ownership, access and mutation
A container owns its elements; span and string_view borrow another object's storage. array stores a fixed number of live elements inline; inplace_vector has inline capacity with a variable number of live elements. Neither type implies stack allocation: it may be a global, a class member or part of a heap allocation. vector owns a separately allocated contiguous sequence.
Use a table to separate guarantees from typical implementations:
| Need | Useful starting point | Mutation caveat |
|---|---|---|
| Contiguous growable data and indexed access | vector | Reallocation invalidates element handles |
| Fixed inline storage | array / inplace_vector | Moving the owner moves the inline storage |
| Both-end sequence growth with stable element references | deque | End insertion invalidates iterators, though existing references survive |
| Relinking existing sequence nodes | list | Erased nodes are gone; transferred nodes retain identity |
| Forward-only nodes | forward_list | Erase needs the predecessor |
| Ordered unique keys and stable live nodes | map / set | An erased/extracted node requires special care |
| Exact lookup without order | unordered_map / unordered_set | Rehash invalidates iterators, preserving references to live elements |
| Stable block storage under churn | hive design | No insertion-order or random-access promise; see the reference-backed extension |
Tree colors, vector growth factors, small-string capacities, deque move
noexcept behavior and exact view object sizes are implementation details or
conditional properties. Read the operation's specified guarantee and query
traits for the exact type/allocator in use. std::is_nothrow_move_constructible_v<T>
is a useful local fact, not a cross-implementation promise.
Moving list nodes does not copy their values
list::splice transfers nodes. A pointer to a transferred integer still points
to the same integer, now in the other list. Equal allocators are a precondition
for transferring between these lists. Do not generalize that into "every move
keeps all handles": moving a container, moving a value and splicing nodes are
three different operations.
#include <list>
#include <iterator>
#include <cstdio>
int main() {
std::list<int> source{1,2,3},destination{9};
auto element=std::next(source.begin());int* address=&*element;
destination.splice(destination.end(),source,element);
std::printf("same node %d, value %d\n",&destination.back()==address,*address);
}forward_list exposes before_begin, insert_after and erase_after because a
singly linked node does not know its predecessor. During a removal loop, keep
the predecessor unchanged after erasure and inspect the returned next iterator.
Otherwise consecutive matches can be skipped. Member sort and merge work
with list links; a random-access sorting algorithm cannot be applied to those
iterators merely because the element type is sortable.
Detach a map node before changing its key
Map iterators expose a const key to protect ordering. C++17 node handles let an owner temporarily detach a node, change its key and insert it again without replacing its mapped object. Check collisions before extraction when the public contract promises that rejection leaves the original map unchanged.
#include <map>
#include <string>
#include <cstdio>
int main() {
std::map<std::string,int> entries{{"old",7}};int* saved=&entries.at("old");
auto node=entries.extract("old");node.key()="new";
entries.insert(std::move(node));
std::printf("same mapped object %d\n",&entries.at("new")==saved);
}Pointers/references retained before extraction become usable again after successful reinsertion; an old iterator to the extracted element stays invalid. Pointers obtained while a node handle owns the element have their own rules. Different allocators can also violate node-insertion preconditions. The exercise uses equal default allocators, checks collisions first and never accesses an extracted node through an invalid handle.
The build combines real splice, predecessor erasure, node-handle renaming and array borrowing. Tests compare identities as well as values. Continue with duplicate-key containers, packed booleans, mdspan and stable hive storage for their specialized contracts.