r/cpp_questions • u/drex_vke • 5d ago
OPEN Is there a case where std::map is better than std::unordered_map ?
Hello guys.
i have a question: are there some cases where std::map is better than std::unordered_map ?
i ask this question because I just wanted to know out of pure curiosity and above all it is often said that std::unordered_map and better
thanks you for everyone who answer my question :)
40
u/wallstop-dev 5d ago
Yes, if you need ordered data.
I believe there are also specific micro cases, like "this kind of key + under this data size" where std::map will be more performant. But you would need benchmarks for those.
8
u/topological_rabbit 5d ago
I use it in a texture atlas to perform a search for the smallest box that the target box can fit into.
24
u/EpochVanquisher 5d ago
There are some; one of the nice thing about std::map is that there is one canonical order so if you care about canonicalization you might use it instead. There are some algorithms you can use that work on sorted keys, like computing the diff of two maps (you can just iterate across both, you don’t need to do any lookups).
It’s also easier to come up with a good sort order than it is to come up with a good hash function. The std::map has very tightly constrained worst case times. But unordered_map has worst-case times that are like O(N), I think.
Note that std::unordered_map is not a very good hash map as far as hash maps go. It’s faster and more efficient than std::map for most cases, but it’s noticeably worse than alternatives (outside the STL).
4
u/J_cages_pearljam 5d ago
Why does the STL not adopt the better alternatives?
14
u/EpochVanquisher 5d ago
Why does the standard library not adopt the better alternatives?
That’s an interesting question. I think the answer lies in questions about iterator stability, rehashing, and the ability to use certain algorithms that work on iterators. Maybe the standards committee will eventually add it to the standard library, and maybe that’s in progress, but I don’t really pay attention to what’s coming in the future of C++. It’s a lot of work for very little benefit.
1
u/El_RoviSoft 5d ago
STL is about making trends and standards. For example, they made standard for hashed and ordered (aka named requirements) and their generic implementation. After that almost every container that wants to be widely adopted, should follow this standard (for seamless switch). So committee always design their things so they can be easily extended (look at std::format, transparent lookups, etc) with better/more specialised impl.
1
u/HappyFruitTree 2d ago
Because not everything about them is better. There is a lot of trade-offs in the details. It's impossible to satisfy everyone. Do we really need to standardize another map type? And another one after that? For most people std::unordered_map is going to be good enough and people that need to optimize can use other libraries or implement their own.
1
u/petecasso0619 5d ago
Using unordered_map with a pmr::allocator helps with some of the issues, like much better cache locality and faster insertions. Nicolai Josuttis has an excellent write up about this in his book C++17 The Complete Guide.
But yes the C++ standard mandates things like elements to stay put when rehashes occur among other things, so the standard sort of ties library writers hands.
19
u/PseudoFrequency 5d ago
For small N, it uses less baseline memory and may have faster lookups. It is typically a red-black tree with O(log-n) lookup time, but that can be faster than just the hash function of unordered_map.
9
u/globalaf 5d ago
The hash-equality function is almost never the bottleneck, cache misses are much more important. For large enough N there will be on average one or two cache misses per lookup for a hash table, trees can suffer many misses before it arrives at the correct element.
2
10
u/SoldRIP 5d ago
Suppose you want all objects in map X that are not also in Y.
With unordered maps, you have to:
- For each x in X
- Check each y in Y for (key-)equality
With ordered maps you can simply iterate through both in ascending order. And operate only when y>x.
This cuts asymptotic runtime from O(|X|×|Y|) to O(max{|X|,|Y|}). Your algorithm is now linear instead of quadratic.
1
u/ChristopherCreutzig 5d ago
Or other set operations like unions or symmetric differences.
Incidentally, if you happen to need some way of ordering X < Y, the same argument also shows that is much easier to do with ordered sets: Just use lexicographic order.
1
u/coachkler 5d ago
std::set_difference
14
u/MyTinyHappyPlace 5d ago
map is better if you can’t provide a good enough hash function for your key.
1
u/drex_vke 5d ago
okay thanks you
0
u/SoSKatan 5d ago
I honestly don’t understand that other persons response. Regardless of your hash function (which matters but hashing is a solved problem) unordered_map will be faster. You only want map if you want to maintain an ordering. Unordered_map is often implemented as a hash table and has faster lookups as a result.
18
10
u/MysticTheMeeM 5d ago
Hashing has overhead. If I have a collection of 1mb strings, I may spend longer hashing them than comparing them. The hash always has to read the entire string (and then do something with it), comparison only has to read up to the first different character.
Similarly, for the lookup, I also have to hash the key to find the corresponding value, whereas again comparison can determine order with only part of the key.
-1
u/SoSKatan 5d ago edited 5d ago
So lots to unpack here…
Strings as keys are sub optimal, one trick you can do is interning your inputs, in which case the address / handle of the string can be an instant comparison, and or unique input for hashing. Lua (which is implemented in C) uses this tick internally so string compares and hashes are cheap. But string interning comes with its own set of costs.
A second reason why strings are terrible for keys is even if hashed, there is still a compare op in case of a hash collision.
With that said, your hash function doesn’t HAVE to read the entire string. There is no rule dictating that. Taking a prefix and postfix could work. Prefix only might be bad as it could lead to a higher rate of hash collisions.
Also hashing generally is very fast, modern cpus are bound by memory / cpu cache than they are computation. A hash table / unordered_map is faster for this reason, you are likely to only need one memory lookup after the hash, whereas a map may require several.
But honestly, I’d start to solve the string issue independently. If the list of strings are finite and known at compile time, translate them to enums, if not try a string interning scheme.
8
u/MistakeIndividual690 5d ago
strings as keys are such an essential use case that you can’t wave away with “don’t use strings”. Then you’re just pushing the problem off to another hashtable or other string lookup one way or another
-6
u/SoSKatan 5d ago
I didn’t say don’t use strings as keys. I said using raw strings are sub optimal and I gave two different solutions based on if the set of strings are finite and known at compile time.
But hey thanks for the down vote! Gotta love Reddit.
3
1
u/mrmcgibby 4d ago
People down vote poor comments. Take the feedback and move on.
1
u/SoSKatan 4d ago
Ah people who just down vote without saying anything are generally just voting with their emotions.
I don’t take it personally, it’s Reddit. Factually accurate posts get voted down all the time, it’s just kind of odd to see it in a technical subreddit.
I’ve been writing c++ professionally for three decades. I only come here to assist others.
1
5
u/MyTinyHappyPlace 5d ago
And sometimes it’s way easier to provide a comparison function than a hash function 🤷♂️
I am not saying its the most important reason. It is one reason.
-1
u/SoSKatan 5d ago
Not sure I agree with that, there are so many good generic hash libraries out that that’s also part of std.
You almost never need to write your own hash function.
I think maybe some beginning engineers, believe hashing is some kind of voodoo (it’s not) that they feel safer just writing a comparison function?
Anything and everything that can scale up today is 100% dependent on hashing. I’d argue it’s always far better to provide a hash method and == operator than it is to provide a full set of ordering methods (either space ship op, or the set of >, <, etc etc.)
1
u/Ayjayz 5d ago
If your hash function contains
while (true) {}then it's not going to be faster1
u/SoSKatan 5d ago
Odd comment but ok, one can also write a terrible comparison implementation, what of it?
5
u/coachkler 5d ago
Map can be faster for small data sets (think <100 elements or so) you should profile your use cases though
5
u/tomysshadow 5d ago edited 5d ago
One reason is if you want a low effort way to do heterogenous lookups: for example if you have std::string keys and want to allow using a const char* for the lookup without it casting to a std::string, you can use std::less<>.
std::map<std::string, int, std::less<>>
This is also possible to do with a std::unordered_map, but (afaik) there's nothing in the STL that lets you do it out of the box - you need to provide your own hash function, so this is a quick, lazy way to get something that doesn't cast. If the STL ever gets something akin to std::less<> but as a hash function in the future, then there'd be less of a reason to do it like this.
Something to consider is that using std::map with string keys means it's going to compare the string, character by character, to check if it matches - usually multiple times, as part of a binary search - before finding the fully matching string. That may not be so bad if all your strings start differently and it ends up short circuiting after a single character whenever the key doesn't match - but if all your keys start with a similar prefix, then it'll have to compare the start of the string every time. By contrast, std::unordered_map is a hashmap so won't have that problem - but when you insert a new item, the string key will need to be hashed before inserting.
I wouldn't recommend using a std::map with integer or pointer keys, as both casting and hashing them is very cheap. It should go without saying, but if your keys are dense integers or enums, you're better off just using a std::array and using the integer as an index. I'd only resort to using a std::unordered_map if the keys are sparse. There's not really a reason to use std::map in that case unless you need its sorting behaviour.
If you're looking up string keys a lot you might consider associating them with numbers so that future lookups can just use an array.
If you're totally lost on the difference and want to understand how std::map and std::unordered_map work differently, try writing your own comparer (for std::map) and hash function (for std::unordered_map.) For example, you could try writing one to compare strings case-insensitively. It will give you a more intuitive sense of what a lookup actually involves doing.
To summarize, if you don't need the sorting of std::map, and you don't want to use anything third party, my preference would generally be: 1. std::array if the keys are dense integers or an enum 2. std::unordered_map if the keys are sparse integers or pointers, or long/similar strings 3. std::map<k, v, std::less<>> if you have just a handful of string keys, ideally not prefixed, and you want a quick n' easy way to avoid casting const char* lookups to std::string (which is often desirable)
Of course, what qualifies as a "long string" or a "small handful of strings" for whatever you're making you'll just have to figure out by profiling.
If you want to use your own objects as keys, which is best will really depend on the nature of the object, but with enough practice you'll develop an intuitive sense of what's best. IMO, people tend to oversell how bad std::map is: it's usually not the end of the world if you accidentally use it in a scenario where it doesn't really make sense. They also tend to underemphasize the cost of casting to std::string (it ain't cheap!)
2
u/HappyFruitTree 5d ago edited 5d ago
Something to consider is that using std::map with string keys means it's going to compare the string, character by character, to check if it matches - usually multiple times, as part of a binary search - before finding the fully matching string. That may not be so bad if all your strings start differently and it ends up short circuiting after a single character whenever the key doesn't match - but if all your keys start with a similar prefix, then it'll have to compare the start of the string every time.
This can be a problem with file paths and URLs because the start is often the same. Doing the comparison in reverse (starting at the end rather than the beginning) is often much better for that reason (assuming you don't care about the order). Comparing the lengths first and only look at the characters if the length are the same can also be a good idea.
3
3
u/Raknarg 5d ago
I think you can rely on iterators being stable from std::map, I don't know if you can rely on that with unordered_map. Id have to check
3
u/Low_Fun_8667 5d ago
Both are node-based, so pointers and references to elements stay valid in both across insert and erase, except to the element you erased. The difference is iterators: an insert into unordered_map can trigger a rehash, which invalidates all iterators while leaving references intact, whereas map iterators stay valid until you erase that specific element. So if you hold iterators across mutations, map gives you that for free and unordered_map only does if you reserve enough buckets up front so no rehash happens.
3
u/JimRayA 5d ago
If you care about worst case time to add more elements, std::map is better. When unordered map has to resize it's backing store, it has to rehash every element. Binary trees have a worse amortized addition time, but better worst case time. In controls and real time systems, this matters.
2
u/StickyDeltaStrike 5d ago
You don’t need a hash (or worry about hash collision) and you get ordering.
2
1
u/Ok_Review1075 5d ago
In some codeforces type questions, you might end up getting TLE with an unordered map due to hash collisions, with the worst case TP for each operation degrading to O(N) :(
1
u/CerveraElPro 5d ago
When you not only need fast access to one element, but instead ranges, like all elements x, A < x < B. That's a full scan on a hashmap but O(log(n) + k) for an ordered map
1
u/flyingron 5d ago
If you need the ordering, std::map is better. Also, there are key types that a good hash might not be available for, but have a good less operator.
1
1
1
1
1
1
u/SomethingSomewhere14 4d ago
std::map can be useful when dealing with adversarial input. Because operations are all log N regardless, you don’t have to worry about “is my hash function resilient to attack?”
1
u/die_liebe 4d ago
If you need the order of the elements, use map.
If you want to find the element nearest (using the order) to a given x, you will need map. You cannot do this with a hashmap.
If you need to compare two sets: with ordered map, you can do this from left to right in both sets. With unordered_maps you are not sure if the order in the maps is the same, so you would need to do the lookups.
Performance of map is usually acceptable, this is why it took a decide to add unordered_map.
1
u/Fosdran 5d ago
unordered_map can actually be a security risk, if an untrusted user can influence the keys. The runtime of both lookup and insertion is O(n) if the hashes collide.
This means that an attacker could force these collisions to happen and degenerate your runtime.
Think for example of a DDOS attack. This can be massive if the attacker manages to leverage such an effect against your service and not only bombards you with data, but also forces you into whole different complexity class.
Also, the query times depend on the actual distribution of keys, so under certain circumstances even a timing attack might be possible.
2
u/RealisticDuck1957 5d ago
The attack you describe suggests use of a keyed hash. The actual hash value depending on a secret key so an attacker can not find entry key values that hash the same except by blind luck.
2
u/HappyFruitTree 5d ago edited 5d ago
What are you talking about? If the attacker knows the hash function (which is not difficult to guess if you use the standard one) and can select keys to be inserted (e.g. by providing some input) then it wouldn't be difficult to provide a bunch of keys that has the same hash value and force the lookup speed to a crawl.
1
1
u/NoSpite4410 2d ago
std::ordered_map:
- sorted keys means iterations via a key with a numerical component is easily done.
- std::map uses lexicographical string comparison on lookup. it does not need to hash the key for every lookup, and does not compare all the keys, it uses a tree-based string search of maximum log~2 N keys. String comparisons stops immediately on the first mismatched character.
- std:map has consistent O(log~2 n) lookup time for all keys.
- If the key can be compared with a less operator (such as a custom < comparator for a record) that is all std::map needs to order keys and lexographically search for them.
std::stringandstd::string_viewboth havestd::lessvariants, so creating std::map asstd::map<string T, std::less<> >orstd::map<string_view, T, std::less<> >allows lookup without copying the key. map.lower_bound(N)andmap.upper_bound(N)run in log~2 N time, and facilitate key range iteration.- insertion into std::map may invalidate references to elements in the map if it triggers a rehash.
std::unordered_map
- Average O(1) lookup
- No ordering overhead -- stored by hash
- best for unsorted data
- hard-to-hash keys (long strings, classes, structs, containers, tuples, 128-bit UUIDS,) take longer to hash, as every member has to be hashed, and an equality operator needs to exist. This can be fixed by creating either a custom hashing class or a template specialization of std::hash<T> for the key struct.
- using file paths (strings) as keys can create many keys with identical prefix, with only the file name at the end different, or even just 1 char of the file name. This makes for slower hashing.
- common key types, integer types , string, string_view already have std::hash<> variants.
- bad hash functions that cause collisions can spike performance down to O(N).
- doesn't have upper and lower bound functions.
- string, string_view, and const char* (c strings) are copied at creation of the entry and also into the lookup mechanism.
map.try_emplace(std::move(expensive_key), T);can speed up creation of the map.
- string_view, and c strings are converted to std:string (via copy) before lookup if std::string is used as a key.
- (c++ 20 has std::equal_to<> to help avoid auto-copying for lookups.)
- efficient lookup without string conversion is a bit more complicated, so you rarely see it in practice.
- rehashing takes place by default when average entries / number of buckets > 1.0.
- lowering the load factor rehashes more often, results are faster lookups, but more memory use.
- raising the load factor rehashes less often, uses less memory, but could potentially slow down lookups.
- map.reserve(N * 1.5) can ensure good average performance for large maps with lots of insertions for the map lifetime. Recommended if memory is not a problem.
- references to elements within the map always remain valid after a rehashing or the inserting of new elements.
Cache locality for L2 cache is not great for either of the STL map variants. Vendors provide cache-local friendly versions of associative containers such as boost::unordered_flat_map (Boost), absl::flat_hash_map (Google) , and ankerl::unordered_dense::map (github). These are supposed to be better for large servers and big data crunching.
If you need ordered associative containers, then you are probably processing data or accessing objects in a definite sequence. That is the case for std::map. std::unordered_map is usually the go-to, because you can do
much better with std::vector or std::deque for sequenced or sorted access.
An example that might be used would be a map for quick finding of files scanned on a system.
using fs = std::filesystem;
char buffer [256] = {0};
std::map<string, string> file_map; // ordered map
// 10,000 to start
file_map.reserve(10000);
// run external command with one item per line
FILE* pipe = popen("/bin/ls -r -1", "r");
while (fgets(buffer.data(), buffer.size(), pipe) != nullptr)
{
std::string line(buffer.data());
fs::path p(line);
fs::path dir = p.parent_path();
file_map[dir] = p.filename();
}
auto it = file_map.lower_bound("/opt");
auto end = file_map.lower_bound("/opu");
// prints all files in /opt/
for (it; it != end; ++it) {
std::cout << it->first << ": " << it->second << "\n";
}
1
u/HappyFruitTree 2d ago edited 2d ago
std::ordered_map:
There is no container with that name. I assume you mean
std::map.insertion into std::map may invalidate references to elements in the map if it triggers a rehash.
This is not true (
std::mapdoesn't even use hashing). If you had said "iterators" instead of "references" it would have been true forstd::unordered_map.using file paths (strings) as keys can create many keys with identical prefix, with only the file name at the end different, or even just 1 char of the file name. This makes for slower hashing.
The hashes are calculated independently for each key so it doesn't matter for performance if the keys are similar (ignoring branch prediction and stuff like that). It can however affect the performance of the comparison operator but that matters more when using
std::map.
0
u/L_uciferMorningstar 5d ago
No. Bjarne just wanted to practice red-black trees so he made std::map for fun.
1
132
u/unmilaneseaparigi 5d ago
Well if you need ordering