Standard Library and Containers

The C++ standard library provides containers, algorithms, ranges, strings, streams, numerics, time, memory utilities, concurrency, and other facilities. Choose by contract rather than familiarity.

Container guide

Need	Typical type	Important property
Contiguous dynamic sequence	std::vector<T>	Indexed access and cache-friendly iteration
Fixed-size contiguous sequence	std::array<T, N>	Size is part of the type
Efficient operations at both ends	std::deque<T>	Not one contiguous allocation
Stable node addresses and splicing	std::list<T>	No random access; allocation per node is typical
Ordered unique keys	std::set<Key>	Logarithmic operations under comparator contract
Ordered key/value pairs	std::map<Key, T>	Sorted traversal
Hash-based unique keys	std::unordered_set<Key>	Average-case constant lookup under hashing assumptions
Hash-based key/value pairs	std::unordered_map<Key, T>	Rehashing and collision behavior matter

std::vector is the default sequence unless a requirement points elsewhere. Linked lists do not become faster merely because insertion itself is constant once a node position is already known.

Algorithms and ranges

std::vector<int> values{5, 1, 4, 1, 3};
std::ranges::sort(values);
auto unique_end = std::ranges::unique(values).begin();
values.erase(unique_end, values.end());

Prefer standard algorithms because they express intent and carry specified complexity and iterator requirements. An algorithm cannot correct an invalid comparator; ordering relations must meet the documented semantic contract.

Iterators and invalidation

Iterator categories express supported traversal operations. Container mutations have operation-specific invalidation rules. Vector growth may reallocate; unordered-container rehashing invalidates iterators; node-based containers have different guarantees. Consult the exact operation rather than memorizing one rule.

Strings and text

std::string stores a sequence of char values; it does not itself enforce one Unicode encoding or understand grapheme clusters. std::string_view is a non-owning view and can dangle. Internationalized text requires an explicit encoding and text-processing policy.

Complexity contracts

Standard-library complexity is part of the portable contract, but constants, allocators, cache behavior, input distributions, and implementation quality still affect measurements. “Average constant time” for hashing is not a worst- case guarantee.

Exercises

1. Choose containers for a priority scheduler, an ordered dictionary, and a byte buffer.
2. Identify invalidated iterators after a vector insertion that reallocates.
3. Replace a manual search loop with a ranges algorithm.