Under what situation (if any) does the ordered map win over the unordered? I find it difficult to believe it is always an improvement, what's the niche uses?
back
4 comments
Some stuff I can think of:
- Hashing can be slower than comparison (or vice-versa), depending on the input. (e.g., imagine if your keys are multi-gigabyte files - hashing them would require reading all of their contents, whereas comparing might only need to read the first few bytes.)
- Ordered maps guarantee good worst-case performance. Unordered maps only guarantee average case. Usually you don't need to care, but with adversarial input you might.
- Ordered maps can guarantee low latency (well, to the extent your allocator can). Unordered maps can't - they suddenly block your program until the whole table is rehashed. Again, usually you don't need to care, but in some situations you might.
- Ordered maps have stable iterators; unordered maps "only" have stable pointers.
- Ordered maps have a guaranteed iteration order that depends solely on their contents; unordered maps don't.
- Any time the ordering itself is useful (see sibling comment)
That was very helpful, my initial mistake was I forgot about the data and only looked at what was being done too it, but I also neglected how we access that data. My background in analog electronics has made this one of the more difficult things in programming for me, I am used to my data as a stream not as something stored.
Any time you actually need to use the ordering property. For instance, if you have an ordered map with string keys, you can very efficiently find all the keys with a given prefix. With an unordered_map, you'd have to iterate through the entire data structure.
Doing a string prefix search in an ordered map is actually not maximally efficient since you end up comparing the shared prefix over and over again during the binary search. You'd definitely don't want to be doing this with long prefixes.
Thanks for explaining the obvious, my self taught programming skills are unordered and my biggest obstacle is generally my not seeing what is right in front of me.
All of <algorithm> uses ordering operators as well. If you have a "regular" type with proper comparison and assignment operators, it works for everything, container keys, sorting, etc, etc.
There may be contrived situations where std::map<T> is actually faster due to the operator < work being possibly cheaper than doing the full hash of the key, but that will only work if the key type is very well distributed early on in the key (i.e. for very long strings, with the first few characters in long strings all being different among items in the std::map, providing the ability to short-circuit quickly) and the number of items in the map is less than what's needed to meet the short-circuit threshold that makes it technically more efficient.
But that's very unlikely, and in such a contrived scenario it's likely doing a linear std::find() over an array of keys would be as fast or faster anyway, due to better caching/pre-fetching/branch-prediction.
If you want to store an object that implements operator< but doesn't have a hash function. While working on a leetcode problem I stored vector<int> in a set<vector<int>> instead of unordered_set<vector<int>> in order to eliminate duplicates.
Do you know about std::unique? Generally sets are a poor tool for removing duplicates.
Doesn't std::unique only generally work on consecutive items, and effectively requires the items to already be in a container (or at the very least have access to iterators to the items)?
If so, that sounds fairly limiting to me (i.e. potential extra storage - of duplicates, sorting required, etc).
This person is already putting sets inside vectors, so I don't think they are worried about storage.
But yes, you either need to stop occasionally and remove the duplicates or use a set, if the storage is prohibitive.
Otherwise in terms of performance, sorting and unique is much faster than inserting one element at a time in a set.