Which map and set variants fit which job comes down to one question. Do you need the elements in a defined order, and does the cost of that order matter? The ordered containers, which are std::map, std::set and std::multimap, keep their elements sorted using a tree and they give you a logarithmic lookup. The unordered ones, which are std::unordered_map and std::unordered_set, use a hash table and they give you an average constant-time lookup with no ordering at all.
The previous lesson in this module covered "How Does std::vector Grow and When Should You Care?", and the next lesson in this module is about "When Do stack, queue and deque Beat vector?".
The four containers
the container what it holds
-------------------- ----------------------------------------------
std::map unique keys mapped to values, sorted by key
std::multimap the same, but several keys may share a value
std::set unique elements, sorted
std::multiset sorted elements that may repeat
std::unordered_map unique keys mapped to values, in no order
std::unordered_set unique elements, in no order
And the ordered versions are built on a balanced tree, while the unordered versions are built on a hash table.
A map associates keys with values
A std::map stores the key-value pairs, sorted by the key, with a lookup in logarithmic time.
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> weights = {
{"p-003", 12},
{"p-001", 4},
{"p-002", 30}
};
weights["p-004"] = 8;
for (const auto& entry : weights) {
std::cout << entry.first << " -> " << entry.second << '\n';
}
std::cout << "p-002 weight: " << weights["p-002"] << '\n';
std::cout << "count: " << weights.size() << '\n';
return 0;
}The output shows the entries in the key order, regardless of the order that they were inserted.
p-001 -> 4
p-002 -> 30
p-003 -> 12
p-004 -> 8
p-002 weight: 30
count: 4And notice that the square brackets on a map create the key with a default value if it is missing. That is convenient and it is occasionally surprising.
A set holds unique elements
A std::set stores the elements with no duplicates and it keeps them sorted.
#include <iostream>
#include <set>
#include <string>
int main() {
std::set<std::string> zones = {"north", "south", "north", "east"};
std::cout << "size: " << zones.size() << '\n';
for (const std::string& zone : zones) {
std::cout << zone << ' ';
}
std::cout << '\n';
std::cout << "has north: " << (zones.count("north") > 0) << '\n';
std::cout << "has west: " << (zones.count("west") > 0) << '\n';
return 0;
}The output shows the duplicate removed and the elements sorted.
size: 3
east north south
has north: 1
has west: 0And the count() on a set returns zero or one, which makes it a convenient membership test.
The unordered variants
The unordered containers make no promises about the order of the elements, but they are usually faster for the large collections because a hash lookup avoids the pointer chasing of a tree.
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> weights = {
{"p-003", 12},
{"p-001", 4},
{"p-002", 30}
};
std::cout << "p-002 weight: " << weights["p-002"] << '\n';
std::cout << "count: " << weights.size() << '\n';
std::cout << "bucket count: " << weights.bucket_count() << '\n';
return 0;
}The output shows the same lookup behaviour with no ordering.
p-002 weight: 30
count: 3
bucket count: 13Ordered or unordered
The decision comes down to three questions.
Do you need the elements in order? If you iterate and you need the sorted output, or you need lower_bound() and upper_bound() to find a range, then you need an ordered container.
Is the key type hashable? The unordered containers require a hash function. The standard library provides one for every built-in type and for std::string, but a user-defined type needs its own specialisation.
How big is the collection? For a handful of the elements the difference does not matter. For the hundreds of thousands, the unordered containers usually win.
the property std::map std::unordered_map
------------------ ----------------------- ------------------------
the order sorted by key unspecified
the lookup logarithmic average constant
the insertion logarithmic average constant
the iterators stay valid on insert invalidated by a rehash
the memory one node per element the buckets plus the nodes
Finding ranges in an ordered map
The ordered containers support the range queries, and that is the reason to choose them when you need them.
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<int, std::string> orders = {
{100, "alpha"}, {200, "bravo"}, {300, "charlie"}, {400, "delta"}
};
auto first = orders.lower_bound(200);
auto last = orders.upper_bound(400);
std::cout << "between 200 and 400:\n";
for (auto it = first; it != last; ++it) {
std::cout << " " << it->first << " -> " << it->second << '\n';
}
return 0;
}The output shows the two entries in the half-open range.
between 200 and 400:
200 -> bravo
300 -> charlie
400 -> deltaChoosing the right container
what you need the container
------------------------------------- ---------------------------------
the lookup by key, no order needed std::unordered_map
the lookup by key, and the entries std::map
sorted
the membership test, no order needed std::unordered_set
the membership test, and the elements std::set
sorted, or the minimum and the maximum
several values for the same key std::multimap
a sorted range query std::map with lower_bound
and upper_bound
Quick reference
- The
std::mapand thestd::setkeep the elements sorted, and the lookup is logarithmic. - The
std::unordered_mapand thestd::unordered_setuse hashing, and the lookup is average constant. - The ordered containers give you the range queries, and the unordered ones do not.
- The unordered containers need a hash function, which the user-defined types must provide.
- The
count()on a set is a membership test. - Rehashing invalidates the iterators into an unordered container.
Try it yourself: store a set of the parcel records in a std::map that is keyed by the identifier, then look one up and print its weight. Next, convert it to a std::unordered_map and time a thousand lookups in each. Finally, use lower_bound() and upper_bound() on the ordered map to list every parcel whose identifier starts with a given letter.