CODEWITHSUNDEEP
c++dictionary
user2943111
user2943111

Reputation: 461

What is the default behavior of a std::map if, rather than the value, the KEY is a std::list or std::vector?

For example, these cases:

using stringlist = std::list<string>;
    
std::map<stringlist, int> orderedMap;
std::unordered_map<stringlist, int> unorderedMap;

How will comparing keys in orderedMap work? Would it compare all items ('sub-keys') in the key one by one in lexical order?

How will computing hash in unorderedMap work?

Upvotes: 2

Views: 78

Answers (1)

Sebastian Redl
Sebastian Redl

Reputation: 71909

An ordered map, by default, uses std::less to compare keys, which by default just does lhs < rhs.

The behavior of vector's operator < is described here: https://en.cppreference.com/w/cpp/container/vector/operator_cmp

And that of list is here: https://en.cppreference.com/w/cpp/container/list/operator_cmp

Yes, they just do a lexicographical comparison, i.e. they compare their elements one by one.

You can override the behavior by supplying a custom comparison as the third template parameter to map.

The default behavior of unordered_map is to use std::hash. std::hash does not have specializations for vector and list, so they are not usable as keys. The code should not compile. Try it here: https://godbolt.org/z/kgKmKS

You need to override the behavior by supplying a custom hasher as the third template argument to unordered_map. You can use Boost.Hash, which supports the standard containers: https://www.boost.org/doc/libs/1_73_0/doc/html/hash/reference.html

Upvotes: 11

Related Questions