Creating unordered map in C for counting the pairs-CodePudding

So let's say I have an array, 1 2 1 2 3 4 2 1 and I want to store all the (arr[i], arr[i-1) such that arr[i] != arr[i-1] as a pair in unordered_map for counting these pairs.
For e.g.

(1, 2)  -> 2
(2, 3) -> 1
(3, 4) -> 1
(4, 2) -> 1
(2, 1) -> 1

So the syntax I tried,

unordered_map<pair<int, int>,  int> umap;
int temp; 
cin>>temp;
arr[i]=temp;
for (int i=1; i< n; i  ){
   cin>>temp;
   arr[i]=temp;
            
   umap[(arr[i-1], arr[i])]  ;
}

Next thing, I also tried with proper definition.

unordered_map<pair<int, int>,  int> umap;
cin>>temp;
arr[i]=temp;
for (int i=1; i< n; i  ){
   cin>>temp;
   arr[i]=temp;
   pair<int, int> p(arr[i-1], arr[i]);
   umap[p]  ;
}

Can anybody please help me get the right syntax?

CodePudding user response：

You can't just use unordered_map with a pair because there is no default hash implemented. You can however use map which should work fine for your purpose because pair does implement <. See Why can't I compile an unordered_map with a pair as key? when you really want unordered_map.

You can construct pair with curly braces like this

umap[{arr[i-1], arr[i]}]  ;

I think from C 11 onward, but it might be C 14 or even C 17

CodePudding user response：

The problem in this case is that std::unordered_map requires a hashable key type. (It's implemented as a hashmap)

But std::hash has no overload for std::pair<>, so your std::unordered_map doesn't compile.

using a normal `std::map`

You could fix this by either switching to a normal map which only requires operator<, which is implemented by std::pair:

std::map<std::pair<int, int>,  int> umap;

int values[] = {1, 2, 1, 2, 3, 4, 2, 1};
for (int i=1; i< sizeof(values) / sizeof(int); i  ) {
    umap[std::pair(values[i-1], values[i])]  ;
}

godbolt example

create a hash function

Or if you want to keep the hashmap, you need to provide a hashing function for your pair, e.g.:

struct pair_hash
{
    template <class T, class U>
    std::size_t operator()(std::pair<T, U> const& pair) const {
        return std::hash<T>()(pair.first) ^ std::hash<U>()(pair.second);
    }
};

and then use that for your map:

std::unordered_map<std::pair<int, int>,  int, pair_hash> umap;

int values[] = {1, 2, 1, 2, 3, 4, 2, 1};
for (int i=1; i< sizeof(values) / sizeof(int); i  ) {
    umap[std::pair(values[i-1], values[i])]  ;
}

godbolt example

Warning: In this example the two hashes from the pair just get xor'ed. This is not a very good method to combine hashes in general, and you should replace it with a better function for production use, for example this hash_combine function.

using a normal std::map

create a hash function

using a normal `std::map`