Why can't I compile an unordered_map with a pair as key?
You need to provide a suitable hash function for your key type. A simple example:
#include <unordered_map>
#include <functional>
#include <string>
#include <utility>
// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1,T2> &p) const {
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
// Mainly for demonstration purposes, i.e. works but is overly simple
// In the real world, use sth. like boost.hash_combine
return h1 ^ h2;
}
};
using Vote = std::pair<std::string, std::string>;
using Unordered_map = std::unordered_map<Vote, int, pair_hash>;
int main() {
Unordered_map um;
}
This will work, but not have the best hash-properties†. You might want to have a look at something like boost.hash_combine
for higher quality results when combining the hashes. This is also discussed in greater detail – including the aforementioned solution from boost – in this answer.
For real world use: Boost also provides the function set hash_value
which already provides a hash function for std::pair
, as well as std::tuple
and most standard containers.
†More precisely, it will produce too many collisions. E.g., every symmetric pair will hash to 0 and pairs that differ only by permutation will have the same hash. This is probably fine for your programming exercise, but might seriously hurt performance of real world code.
pairint,int pair as key of unordered_map issue
This happens because there is no specialization for std::tr1::hash<Key>
with Key = std::pair<int, int>
.
You must to specialize std::tr1::hash<Key>
with Key = std::pair<int, int>
before declaring tr1::unordered_map<Pair,bool> h;
.
This happens because std
don't know how to hash a pair<int, int>
.
Following there is a example of how to specialize std::tr1::hash<>
template <>
struct std::tr1::hash<std::pair<int, int> > {
public:
size_t operator()(std::pair<int, int> x) const throw() {
size_t h = SOMETHING;//something with x
return h;
}
};
Why does std::map accept a std::pair as key, but std::unordered_map does not?
std::map
doesn't hash anything. It uses std::less
as its default comparator. It will work for any type that supports operator<
.
std::unordered_map
sorts its elements using a hash provided by std::hash
.
It so happens that std::pair
provides operator<
, but doesn't have a specialization for std::hash
.
Why is pair not working with unordered_map?
Sometimes the compiler does a lousy job with the error messages. Your problem is the find
algorithm.
unordered_map
& map
have their own find, which take the key as argument and returns an iterator. The algorithm is looking for the key:
auto it = hm.find(key);
if (it != hm.end())
{
// ...
}
The global find algorithm takes a search interval and a value as input. But it works with any container that meets some iterators constrains. In the case of a map the value is not the key, as in the unordered_map::find
but the (key, value) pair. The algorithm is looking for the (key, value) pair. You can declare your target value and use it like this:
unordered_map<int, int>::value_type target{ key, value };
auto it = find(hm.begin(), hm.end(), target);
if (it != hm.end())
{
// ...
}
Creating unordered map in C++ for counting the pairs
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
C++: Using pair of (cpp_int, int) integers as key in unordered_map (where cpp_int are boost multiprecision integers)
Yes, you took the Multiprecision hash I contributed earlier and added the hash for std::pair
. I'm not a fan of handrolling the hash combination (good general hash combination is not trivial).
So I'd do the same with boost::hash_combine
:
template <typename K, typename V>
struct hash<std::pair<K, V> >
{
size_t operator()(std::pair<K, V> const& pair) const {
size_t seed = std::hash<K>{}(pair.first);
boost::hash_combine(seed, pair.second);
return seed;
}
};
Live On MSVC RexTester
#include <iostream>
#include <iomanip>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_int/serialize.hpp>
#include <boost/iostreams/device/back_inserter.hpp>
#include <boost/iostreams/stream_buffer.hpp>
#include <boost/iostreams/stream.hpp>
#include <boost/functional/hash.hpp>
namespace mp_hashing {
namespace io = boost::iostreams;
struct hash_sink {
hash_sink(size_t& seed_ref) : _ptr(&seed_ref) {}
typedef char char_type;
typedef io::sink_tag category;
std::streamsize write(const char* s, std::streamsize n) {
boost::hash_combine(*_ptr, boost::hash_range(s, s+n));
return n;
}
private:
size_t* _ptr;
};
template <typename T> struct hash_impl {
size_t operator()(T const& v) const {
using namespace boost;
size_t seed = 0;
{
iostreams::stream<hash_sink> os(seed);
archive::binary_oarchive oa(os, archive::no_header | archive::no_codecvt);
oa << v;
}
return seed;
}
};
}
#include <unordered_map>
#include <boost/unordered_map.hpp>
namespace std {
template <typename backend>
struct hash<boost::multiprecision::number<backend> >
: mp_hashing::hash_impl<boost::multiprecision::number<backend> >
{};
template <typename K, typename V>
struct hash<std::pair<K, V> >
{
size_t operator()(std::pair<K, V> const& pair) const {
size_t seed = std::hash<K>{}(pair.first);
boost::hash_combine(seed, pair.second);
return seed;
}
};
}
int main() {
using boost::multiprecision::cpp_int;
std::unordered_map<std::pair<cpp_int, int>, int> m {
{ { cpp_int(1) << 111, -1 }, 1 },
{ { cpp_int(2) << 222, -2 }, 2 },
{ { cpp_int(3) << 333, -3 }, 3 },
};
for (auto& p : m)
std::cout << p.first.first << " -> " << p.second << "\n";
}
Why can not I use operator[] for std::unordered_mapstd::pairint,int, int but for same key-value pair of `std::map`?
when doing the same with
std::map
, no error occurs. why? And how can I
make it works withstd::unorderd_map
?
Because they are simply different.
std::unorderd_map
the elements are placed according to the hash of its keys.
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;
whereas the std::map
needs simply a comparison function in order to sort the keys.
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T> >
> class map;
The reason why your std::map<std::pair<int,int>, int>
got compiled is, the operator<
is defined for std::pair
and std::map
uses it to sort its keys, whereas the hash function for std::pair
has not been defined and hence std::unorderd_map
need one to keep elemets in its buckets. This you need to define.
For instance, you can define a custom hash function as follows:
#include <unordered_map>
#include <cstddef>
#include <functional>
struct CustomHash
{
template <typename T, typename U>
std::size_t operator()(const std::pair<T, U> &x) const
{
return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
}
};
int main()
{
std::unordered_map<std::pair<int,int>, int, CustomHash> mp;
mp[std::make_pair(1, 2)]++;
return 0;
}
PS: #include <bits/stdc++.h>
is a bad coding practice. Why? see this .
more efficient structure as unordered_mappairint, int, int
As suggestet, I went with a vector<pair<int, int>>*
with N entries. It's about 40% faster than the unordered_map
.
Related Topics
C++ #Include and #Import Difference
Why Can't We Declare a Namespace Within a Class
Vary Range of Uniform_Int_Distribution
What Is the Meaning of Template<> with Empty Angle Brackets in C++
Why Do We Have Reinterpret_Cast in C++ When Two Chained Static_Cast Can Do Its Job
Why Isn't There an Operator[] for a Std::List
Relative Paths Not Working in Xcode C++
Mock Non-Virtual Method C++ (Gmock)
How to Block Running Two Instances of the Same Program
How to Iterate Over a Std::Tuple in C++ 11
What's the Easiest Way to Generate Xml in C++
What Does 'Return *This' Mean in C++
Why Must I Put a Semicolon at the End of Class Declaration in C++
Literal Initialization for Const References