std::vector stores elements contiguously in memory, giving it excellent cache performance for iteration and making it the right default for most sequential data, even in cases that superficially sound like they need a linked list. std::list is a genuine doubly-linked list, offering O(1) insertion/removal at any known position but poor cache locality — it's the right choice specifically when frequent mid-sequence insertion/removal on large data is the actual bottleneck, which is rarer than intuition suggests. std::map keeps keys sorted (implemented as a balanced tree, O(log n) operations); std::unordered_map uses a hash table for average O(1) operations but no ordering — pick based on whether sorted iteration is actually needed.
vector: the default choice
push_back is amortized O(1) (occasionally reallocating and copying, but rarely enough that the average cost stays constant); contiguous storage means iterating a vector is dramatically more cache-friendly than the equivalent list traversal, in practice.
std::vector<int> v = {1, 2, 3};
v.push_back(4); // amortized O(1)
v[0] = 10; // O(1) random access
for (int x : v) { /* fast — contiguous memory */ }map vs unordered_map: ordering vs raw speed
map keeps keys in sorted order automatically, useful when iterating in order matters; unordered_map is typically faster for pure lookup/insert workloads that don't care about order at all.
std::map<std::string, int> sorted;
sorted["banana"] = 2;
sorted["apple"] = 1;
for (auto& [key, value] : sorted) { /* iterates in SORTED key order: apple, banana */ }
std::unordered_map<std::string, int> fast;
fast["banana"] = 2;
fast["apple"] = 1;
// iteration order is UNSPECIFIED — but lookups are typically faster on averageWhen list genuinely earns its place
Frequent insertion/removal in the MIDDLE of a large sequence, where the position is already known (via an existing iterator), is list's real strength — vector would need to shift every following element, while list just relinks a couple of pointers.
std::list<int> l = {1, 2, 3, 4, 5};
auto it = std::find(l.begin(), l.end(), 3);
l.insert(it, 99); // O(1) — just relinks pointers, no shifting needed
// the equivalent vector.insert() would need to shift every element after position 3