CODEWITHSUNDEEP
c++c++11unordered-mapstdmap
Johy
Johy

Reputation: 303

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

The C++11 standard introduced std::unordered_map and std::unordered_set, which use a hash function and have (on average) constant complexity of inserting/deleting/getting the elements.

In cases where we do not need to iterate over the collection in a particular order, it seems there is no reason to use "old" std::map or std::set.

Are there some other cases / reasons when std::map or std::set would be a better choice? Would they be for example less memory consuming, or is the ordering their only advantage over the "unordered" versions?

Upvotes: 1

Views: 782

Answers (2)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275385

They are ordered, and writing < is 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.

Upvotes: 3

Vikas Awadhiya
Vikas Awadhiya

Reputation: 308

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.

Upvotes: 1

Related Questions