Putting a vector of pairs in an unordered_map vs a map

Question

So consider this code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_map<vector<pair<int,int>>,int> mp ;
    for(int i=0;i<10;i++)
    {
        vector<pair<int,int>> v ;
        for(int j=0;j<10;j++)
            v.push_back(make_pair(j,2*j)) ;
        mp[v] = i ;

    }
    return 0;
}

What I'm doing here is creating an unordered_map with keys of the type vector<pair<int,int>>. As you can see here, this raises an error.

But when I change this unordered_map to just a map, this error doesn't occur anymore. That is:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    map<vector<pair<int,int>>,int> mp ;
    for(int i=0;i<10;i++)
    {
        vector<pair<int,int>> v ;
        for(int j=0;j<10;j++)
            v.push_back(make_pair(j,2*j)) ;
        mp[v] = i ;

    }
    return 0;
}

Works well.

So what is with unordered_maps and putting vectors in them as keys? What is going on here?

```85:34: error: no match for call to ‘(const std::hash > >) (const std::vector >&)```is not this error message clear enough ? just read what requirement for key class has ```map``` and ```unordered_map``` — Andrew Kashpur, Nov 01 '19 at 08:18
This might be helpful: https://thispointer.com/map-vs-unordered_map-when-to-choose-one-over-another/. The difference between map and unordered map is the way keys are handled internally. From the log, it appears that the hash function for the key vector> is missing. — Yasir Khan, Nov 01 '19 at 08:26
Why on earth would you ever want to use a vector of pairs of ints as a key? — Indiana Kernick, Nov 01 '19 at 08:40
`map` is using operator `<` for vectors to define an ordering. `unordered_map` requires a hash value to put the key in an appropriate bucket but since you haven't specified it, it's throwing an error. — srt1104, Nov 01 '19 at 09:07
Unrelated, but possibly helpful for the future: [Why should I not #include](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Also please post error messages directly in the question to save us some time. — Lukas-T, Nov 01 '19 at 09:53

score 2 · Accepted Answer · edited Mar 10 '22 at 19:42

To elaborate a little on this: For std::map:

std::map is a sorted associative container that contains key-value pairs with unique keys.Keys are sorted by using the comparison function Compare. [...] Maps are usually implemented as red-black trees.

Said "function Compare" is a template parameter with default value std::less<Key>. So a map needs to compare values using < to sort them into the red-black-tree. std::vector supports (such a comparison)[https://en.cppreference.com/w/cpp/container/vector/operator_cmp].

std::unordered_map on the other hash requires a hash-function to put keys into hash buckets. The used hash function is a template parameter with a default value of std::hash<Key>.

std::hash has only an overload for vector<bool>, not for any generic vector. Unless you provide a custom hash function, the unordered_map has no way of computing a hash for the keys, that's what the errors message tells you too.

Putting a vector of pairs in an unordered_map vs a map

1 Answers1