Appearance
C++ Containers, Iterators, Algorithms, and Ranges
Standard containers are best selected by ownership, invalidation, lookup behavior, and complexity—not by finding the nearest class from another language.
vector is the default sequence
cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{8, 3, 5, 3};
std::ranges::sort(values);
values.erase(std::unique(values.begin(), values.end()), values.end());
for (int value : values) std::cout << value << ' ';
std::cout << '\n';
}vector owns contiguous elements, offers constant-time indexed access and amortized constant-time append, and works well with caches and C APIs through data(). Growth can invalidate all references and iterators; erasure invalidates positions at and after the erased element.
Use array<T, N> for a fixed compile-time extent, deque for stable-ended growth characteristics, and linked lists only when their specific node/invalidation properties outweigh allocation and locality costs.
Associative containers encode lookup policy
map and set maintain ordered keys with logarithmic operations. unordered_map and unordered_set use hashing with average constant-time lookup, subject to hash quality and rehashing. Ordering, iterator stability, denial-of-service considerations, memory overhead, and key semantics matter more than a slogan about Big O.
Iterators separate traversal from storage
An iterator identifies a position under a container-specific validity contract. Algorithms accept iterator pairs or ranges:
cpp
auto found = std::ranges::find(values, requested);
if (found != values.end()) {
use(*found);
}Never dereference the end iterator. Mutation may invalidate iterators; consult the container operation's contract.
Algorithms communicate operations
Use algorithms where the named operation clarifies intent—find, sort, transform, copy_if, accumulate. A straightforward loop remains appropriate for complex stateful logic. Functional-looking code is not automatically clearer.
C++20 ranges reduce iterator-pair noise and allow projections and composable views:
cpp
auto positives = values | std::views::filter([](int value) { return value > 0; });Views are generally lazy and non-owning. Their source must remain alive, and mutation/invalidation rules still apply.
Complexity is part of the interface
Reserve vector capacity when a known count avoids repeated growth and invalidation. Avoid operator[] on a map when mere lookup should not insert. Use at when bounds/key failure should be explicit. Measure before replacing contiguous storage with a theoretically attractive structure.
Optional prompts
Explain: Why is vector often preferable to list even for repeated traversal?
Answer: Contiguous storage has low allocation overhead and good cache locality. A list's stable nodes and constant-time insertion help only when the algorithm can exploit them and already has the position.
Predict: Does a ranges view normally own copied elements?
Answer: No. Most views lazily refer to an underlying range, so owner lifetime and invalidation remain relevant.