Every standard container, and when to pick it
array, vector, string, deque, list, map, set and their unordered twins, with the one question that picks between them.
Decide by what the program does to the data most often.
- Looked up by a key, not by position? Key with a value → a
map. Key alone → a set. Need sorted order, or the same output on
every platform →
std::map/std::set. Order never matters and speed does → theunordered_versions. - Otherwise it's a sequence. Size fixed when the program is
built →
std::array. Adding or removing at the front as well as the back →std::deque. Inserting and erasing in the middle at iterators you hold, where other iterators must stay valid →std::list. - Everything else →
std::vector. It's contiguous, so walking it is fastest, and it works withstd::spanand C APIs.
Text is a std::string. Whatever you pick, check what its changes
do to iterators you're holding.
Sequences
Section
std::array, a fixed size
Section
std::vector, the default
Section
How a vector grows
Why a full vector reallocates and moves every element into a bigger block.
Section
std::deque and std::list
Looked up by key
Before you rely on it
How they work inside
Section
Counting steps and Big-O
Section
A hash map built from vectors
Section