When std::map/std::set should be used over std::unordered_map/std::unordered_set?

0
votes

As in new standards std::unordered_map/std::unordered_set were introduced, which uses hash function and have in average constant complexity of inserting/deleting/getting the elements, in case where we do not need to iterate over the collection in particular order, it seems there is no reason to use "old" std::map/std::set? Or there are some other cases/reasons when std::map/std::set would be a better choice? Like would they be for ex. less memory consuming, or their only pros over the "unordered" versions is the ordering?

2
c++algorithmc++11hashstd
FWIW, don't use the standard provided unordered containers. They are basically required to be a vector of linked lists. There are better open source hash based containers out there. My advice is only use std::map/std::set if you need to maintain a sorted order. Otherwise use a hash based container. – NathanOliver
The advantage of the ordered map/set is that they're ordered. That's really the only reason I can think of to use them. – Mooing Duck
@NathanOliver the "better" hashmaps out there (like absl for instance) are better for many uses, but not all. I tried replacing unordered_set/map with those alternatives in our library, in some places it was a nice gain, in half of the places it was a catastrophic loss. – Marc Glisse
@Johy The simple answer is that for every use when you need performance, use what's cache friendly, in this case unordered_map and unordered_set. Keep in mind though that if you use these structures for buffers and try to access them from multithreaded context you may experience hiccups, since occasionally the underlaying array will have to grow (same is true for list vs vector). In essence, benchmark and profile before you make final decision. – Michał Kaczorowski
@NathanOliver from my experience with the most popular implementation of robin hood and hopscotch from either tessil, abseil and skarupke they just don't work with anything other than simple types. If you even need to store smart pointers the performance will just tank down, and with bad hash function some of them will simply give up and crash or run out of memory. So I would recommend benchmarking before deciding to use anything other than std. – Michał Kaczorowski

2 Answers

2
votes

They are ordered, and writing < us easier than writing hash and equality.

Never underestimate ease of use, because 90% of your code has trivial impact on your code's performance. Making the 10% faster can use time you would have spent on writing a hash for yet another type.

OTOH, a good hash combiner is write once, and get-state-as-tie makes <, == and hash nearly free.

Splicing guarantees between containers with node based operations may be better, as splicing into a hash map isn't free like a good ordered container splice. But I am uncertain.

Finally the iterator invalidation guarantees differ. Blindly replacing a mature tested moew with an unordered meow could create bugs. And maybe the invalidation features of maps are worth it to you.

0
votes

std::set/std::map and std::unordered_set/std::unordered_map are used in very different problem areas and are not replaceable by each other.

  1. std::set/std::map are used where problem is moving around the order of elements and element access is O(log n) time in average case is acceptable. By using std::set/std::map other information can also be retrieved for example to find number of elements greater than given element.

  2. std::unordered_set/std::unordered_map are used where elements access has to be in O(1) time complexity in average case and order is not important, for example if you want to keep elements of integer key in std::vector, it means vec[10] = 10 but that is not practical approach because if keys drastically very, for example one key is 20 and other is 50000 then keeping only two values a std::vector of size 50001 have to be allocated and if you use std::set/std::map then element access complexity is O(log n) not O(1). In this problem std::unordered_set/std::unordered_map is used and it offers O(1) constant time complexity in average case by using hashing without allocating a large space.