TopolearnPicking the right container is the most common design decision in C++ code and has a big effect on speed and clarity.
The standard library's containers fall into a few families:
- Sequence:
std::vector(the default),std::array(fixed size),std::deque(fast push/pop at both ends),std::list/std::forward_list(linked lists, rarely the right choice). - Ordered associative:
std::map<K, V>andstd::set<K>, kept sorted by key in a balanced tree. Lookup, insert and erase are O(log n), and iteration is in key order. - Unordered associative:
std::unordered_mapandstd::unordered_set, hash tables with average O(1) operations and no ordering. Keys needstd::hashand==. - Adapters:
std::stack,std::queue,std::priority_queue(a heap) on top of another container.
Map APIs have well-known traps. m[key] inserts a default-constructed value if the key is missing, which is convenient for counting (++freq[word]) but surprising for lookups, and unavailable on a const map. To look up without inserting, use find (returns end() when missing), contains (C++20) or at (throws). try_emplace and insert_or_assign are the clear way to insert. Iterate with structured bindings: for (const auto& [key, value] : m).
Rules of thumb: start with vector; use unordered_map for fast key lookup; use map when you need sorted order or range queries like lower_bound. For a small, mostly-read lookup table, a sorted vector often beats both thanks to cache locality; C++23 packages that idea as std::flat_map and std::flat_set.
All containers are RAII values: they free everything they hold, copy deeply and can be moved cheaply.
Example
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
int main() {
std::vector<std::string> words{"to", "be", "or", "not", "to", "be"};
std::unordered_map<std::string, int> freq; // hash table, average O(1)
for (const auto& w : words) ++freq[w]; // [] inserts 0 if missing
std::map<std::string, int> sorted(freq.begin(), freq.end()); // ordered by key
for (const auto& [word, n] : sorted) // structured bindings
std::cout << word << '=' << n << ' '; // be=2 not=1 or=1 to=2
std::cout << '\n';
std::set<std::string> unique(words.begin(), words.end());
std::cout << unique.size() << ' ' << unique.contains("or") << '\n'; // 4 1
if (auto it = freq.find("xyz"); it == freq.end())
std::cout << "no xyz\n"; // find doesn't insert; [] would
std::cout << freq.size() << '\n'; // 4
}Remember
vectorfirst;unordered_mapfor fast lookup;mapfor sorted keysm[k]inserts when k is missing — usefind,containsoratto look up- Iterate maps with
for (const auto& [k, v] : m)
Watch out for
- Using
if (m[key] == 0)to test for presence, which inserts every key you test.