std::multimap/std::multiset
Explanation
Like map/set but allows duplicate keys.
See std::multimap and std::multiset.
Time complexity: same as std::map/std::set.
| Operation | Complexity |
|---|---|
find(), count(), contains() | O(log n) |
insert()/emplace() | O(log n) |
erase() by key | O(log n + k) where k = num of matching keys |
Use case
- Multiple values per key, grouping related items.
Code
#include <map>
#include <print>
#include <string>
int main() {
// Multiple symbols can have the same address (aliases)-
std::multimap<uint64_t, std::string> symbols;
symbols.emplace(0x10001000, "_main");
symbols.emplace(0x10001000, "main");
symbols.emplace(0x10002000, "_helper");
auto range = symbols.equal_range(0x10001000);
std::println("Symbols at 0x10001000:");
for (auto it = range.first; it != range.second; ++it) {
// it->second is the value (std::string name)
std::println("{}", it->second);
}
return 0;
}
Output
$ ./src/data-structures/build/std-multimap-std-multiset
Symbols at 0x10001000:
_main
main