CODEWITHSUNDEEP
c++unordered-map
JobHunter69
JobHunter69

Reputation: 2270

Unordered_map of unordered_map vs custom hash function for pair key C++?

I have some keys that are pair<string, string>. I was originally going to write my own hash function but thought that it might be easier to just implement an unordered_map<string, unordered_map<string, val>>. Are there any performance differences between these two I should be aware of?

Upvotes: 2

Views: 1448

Answers (2)

Mansoor
Mansoor

Reputation: 2438

Defining a simple hash function in your case is trivial and performant. If the std::pair is semantically the key, then this approach makes your intent clear. It also allows duplicates of the first member of the std::pair in your map, as you only need the entire key to be unique. In terms of usage, you also avoid the additional layer of indirection, with nested maps.

Example implementation:

Godbolt

...

using pairSS = std::pair<std::string, std::string>;

namespace std
{
    template<> struct hash<pairSS>
    {
        std::size_t operator()(pairSS const& pair) const noexcept
        {
            return std::hash<std::string>{}(pair.first) ^
                (std::hash<std::string>{}(pair.second) << 1);
        }
    };
}

int main()
{
    std::pair myPair = {"Hi", "bye"};

    std::cout << std::hash<pairSS>{}(myPair) << std::endl;

    struct val{};
    std::unordered_map<pairSS, val> hashMap;
}

Upvotes: 1

PiotrNycz
PiotrNycz

Reputation: 24412

I would use std::unordered_map<std::pair<std::string, std::string>, Value, [pair_hash][1]> for two reasons:

  1. Performance

Of course, you can measure your two versions with your favorite profiler, but basing on my experience - the number of allocation is what matters here the most - so see:

flat_map.insert(key, value)); will create on average just one new bucket (or extend one), whilst

auto it = map2.insert(make_pair(key.first, map1{}));
it->second.insert(make_pair(key.second, value));

have to create empty map1 - what might not be zero-cost. Then it has to add/extend two buckets (list associated with the given hash value).

  1. Maintainability/Readability

The Second reason is more important for me. Flat(one) map is easy to use. You could see in insert example already that it is more complicated, but consider erase - it is so complicated, that it is easy to make a mistake:


void remove(
   std::unordered_map<std::string, 
           std::unordered_map<std::string, Value>>& map,
    std::pair<std::string, std::string> const& key)
{
   auto it1 = map.find(key.first);
   if (it1 == map.end()) return;
   it1->second.erase(key.second);
   // easy to forget part
   if (it1->second.empty())
   {
       map.erase(it1);
   }
}

Upvotes: 1

Related Questions