Std::Unordered_Map::Find Using a Type Different Than the Key Type

In practice, when `std::unordered_map` must be used instead of `std::map`?

I know the difference between them, say internal implementation,time complexity for searching element

In that case, you should know that that the average asymptotic element lookup time complexity of unordered map is constant, while the complexity of ordered map is logarithmic. This means that there is some size of container at which point the lookup will be faster when using unordered map.

But I really can't find a circumstance where std::unordered_map could not be replaced by std::map indeed.

If the container is large enough, and if you cannot afford the cost of ordered map lookup, then you cannot choose to replace the faster unordered map lookup.

Another case where ordered map cannot be used is where there doesn't exist a cheap function to compare relative order of the key.

How to find by a key of type std::wstring_view in std::unordered_map<std::wstring, T>?

What you are trying to do is called "heterogeneous lookup" (basically, the type of the map and the type you're trying to use to lookup are different types). In C++20, thanks to P0919, we are going to get new overloads of unordered_map::find() that will allow what you're trying to do to work.

Until then, the only relevant overload takes, specifically, a Key const&. And basic_string's constructor from basic_string_view is explicit (see #10). So in C++17, you have to write:

map.find("asdf"s)

or

map.find(std::string("asdf"sv));

unordered_map: Lookup pair of std::string with a pair of std::string_view

With C++20's heterogeneous lookups this can be done (see documentation of unordered_map::find()). For this to work a hash functor and a equality functor have to be defined, e.g.:

struct hash {
    template <typename T>
    auto operator()(const std::pair<T, T>& pair) const {
        return std::hash<T>{}(pair.first) ^ std::hash<T>{}(pair.second); // not to be used in production (combining hashes using XOR is bad practice)
    }

    using is_transparent = void; // required to make find() work with different type than key_type
};

struct equal {
    template <typename A, typename B>
    auto operator()(const std::pair<A, A>& a,
                    const std::pair<B, B>& b) const {
        return a.first == b.first && a.second == b.second;
    }

    using is_transparent = void; // required to make find() work with different type than key_type
};

The type of the map then has to be changed to std::unordered_map<std::pair<std::string, std::string>, int, hash, equal> in order to use the defined functors.

find() now works as intended:

using namespace std::literals;

std::unordered_map<std::pair<std::string, std::string>, int, hash, equal> map{};

map.insert({std::pair{"a"s, "b"s}, 42});

if (auto it = map.find(std::pair{"a"sv, "b"sv}); it != map.end())
  std::cout << it->second << std::endl;

if (auto it = map.find(std::pair{"x"s, "y"s}); it != map.end())
  std::cout << it->second << std::endl;

// prints 42

The implementation can be played with here

How does std::unordered_map determine the location of a specific key in a hash table?

Typically a hash map keeps an array of buckets inside. A bucket, on the other hand is a list of entries. And so something like this:

template<class TKey, class TValue>
class HashMap {
    vector<vector<pair<TKey, TValue>>> Buckets;
};

Then when you do a lookup, it simply takes the key, computes its hash, say hash, goes to Buckets[hash % Buckets.size], which is of type vector<pair<TKey,TValue>> and does a linear search on it. This makes the amortized (average) lookup complexity constant, while in the worst case (e.g. bad hashing function) it is linear. And indeed, this is the guarantee you get with the unordered_map.

Note that the top level vector will eventually grow when you add elements (maybe even when you remove), in order to allow more entries and avoid collisions. Rehashing is likely to take place in such case. And so adding/removing elements is not trivial, and can be expensive from time to time.

Also note that since vector allocates memory on the heap under the hood, then there is no issue with using more than one map. They share nothing (well, they may share something, but it doesn't affect the behaviour). But even if an implementation does not use vector (which is not mandatory, its just an example), some form of dynamic malloc has to be used to guarantee that.

Using A Struct As Key For std::unordered_map

To use a structure as a key in an unordered_map, you need two things:

• A "hasher", something that will take a const test & and compute a hash, which defaults to std:hash<test>, and

• A comparison predicate, which defaults to std::equal_to<test>.

You've got the second one covered with your spaceship operator, but not the first. There is no std::hash<test>.

See C++ unordered_map using a custom class type as the key for an example as how to define your own hasher.

How can I get around from using [] operator on const unordered_map in C++?

Use the method "find" which is const :
https://en.cppreference.com/w/cpp/container/unordered_map/find

In your case, something like :

int lookupWithFallback(const StringIntMap& wordcount_map, const std::string& key, int fallbackVal) {
     auto it = wordcount_map.find(key);
     if(it != wordcount_map.end())
        return it->second;
     else
       return fallbackVal;
}

The operator [] is not const because if the key doesn't exist, it will be created.
https://en.cppreference.com/w/cpp/container/unordered_map/operator_at

---

Related Topics