C++ · 5 · STL23 / 36 · 64%
map, unordered_map & set
Ordered tree vs hash table — pick by access pattern, not by habit.
Examples: std::map, unordered_map, set, find
shortcuts: ← prev · → next · M mark
1
Ordered vs Hashed
map is a red-black tree; unordered_map is a hash table.
Example
example
std::map<std::string, int> ordered; // sorted by key
std::unordered_map<std::string, int> hashed; // no order
ordered["ada"] = 36;
if (auto it = hashed.find("ada"); it != hashed.end())
std::cout << it->second;balanced tree vs bucket array
2
Cost
The numbers that drive the choice.
Complexity
| map insert / find / erase | O(log n) | sorted iteration free |
| unordered_map insert / find | O(1) avg | O(n) worst |
| map iteration | O(n) sorted | |
| unordered_map iteration | O(n) arbitrary order |
3
operator[] Inserts
Reading a missing key with [] silently creates it.
Example
example
std::map<std::string,int> m;
if (m["missing"] == 0) { } // just inserted "missing" -> 0 !
int v = m.at("missing"); // throws std::out_of_range instead
auto it = m.find("missing"); // no insertion, no throwWATCH OUT
operator[] also requires the value type to be default-constructible, and it is non-const.
4
Modern Insertion
C++17 gives you clearer, cheaper insertion APIs.
Example
example
auto [it, inserted] = m.try_emplace("ada", 36); // no overwrite
m.insert_or_assign("ada", 37); // overwrite
m.emplace("linus", 54);
std::set<int> s{3,1,2}; // sorted unique: 1 2 3