C++ unordered_map с использованием пользовательского типа класса в качестве ключа
Я пытаюсь использовать пользовательский класс в качестве ключа для unordered_map, как показано ниже,
#include <iostream>
#include <algorithm>
#include <unordered_map>
//#include <map>
using namespace std;
class node;
class Solution;
class Node {
public:
int a;
int b;
int c;
Node(){}
Node(vector<int> v) {
sort(v.begin(), v.end());
a = v[0];
b = v[1];
c = v[2];
}
bool operator==(Node i) {
if ( i.a==this->a && i.b==this->b &&i.c==this->c ) {
return true;
} else {
return false;
}
}
};
int main() {
unordered_map<Node, int> m;
vector<int> v;
v.push_back(3);
v.push_back(8);
v.push_back(9);
Node n(v);
m[n] = 0;
return 0;
}
Я думаю, мне нужно сказать C++, как хэшировать класс Node, однако я не совсем уверен, как это сделать. Есть ли пример для такого рода задач?
Вот ошибка из g++:
In file included from /usr/include/c++/4.6/string:50:0,
from /usr/include/c++/4.6/bits/locale_classes.h:42,
from /usr/include/c++/4.6/bits/ios_base.h:43,
from /usr/include/c++/4.6/ios:43,
from /usr/include/c++/4.6/ostream:40,
from /usr/include/c++/4.6/iostream:40,
from 3sum.cpp:4:
/usr/include/c++/4.6/bits/stl_function.h: In member function ‘bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Node]’:
/usr/include/c++/4.6/bits/hashtable_policy.h:768:48: instantiated from ‘bool std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_M_compare(const _Key&, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type, std::__detail::_Hash_node<_Value, false>*) const [with _Key = Node, _Value = std::pair<const Node, int>, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable.h:897:2: instantiated from ‘std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node* std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_find_node(std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node*, const key_type&, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type) const [with _Key = Node, _Value = std::pair<const Node, int>, _Allocator = std::allocator<std::pair<const Node, int> >, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = false, bool __unique_keys = true, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node = std::__detail::_Hash_node<std::pair<const Node, int>, false>, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::key_type = Node, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable_policy.h:546:53: instantiated from ‘std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type& std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::operator[](const _Key&) [with _Key = Node, _Pair = std::pair<const Node, int>, _Hashtable = std::_Hashtable<Node, std::pair<const Node, int>, std::allocator<std::pair<const Node, int> >, std::_Select1st<std::pair<const Node, int> >, std::equal_to<Node>, std::hash<Node>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, false, false, true>, std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type = int]’
3sum.cpp:149:5: instantiated from here
/usr/include/c++/4.6/bits/stl_function.h:209:23: error: passing ‘const Node’ as ‘this’ argument of ‘bool Node::operator==(Node)’ discards qualifiers [-fpermissive]
make: *** [threeSum] Error 1
8 ответов
Чтобы иметь возможность использовать std::unordered_map (или один из других неупорядоченных ассоциативных контейнеров) с определяемым пользователем типом ключа, вам нужно определить две вещи:
Хеш-функция; это должен быть класс, который переопределяет
operator()и вычисляет значение хеш-функции, заданное для объекта типа ключа. Одним из особенно простых способов сделать это является специализацияstd::hashшаблон для вашего типа ключа.Функция сравнения на равенство; это необходимо, поскольку хеш-функция не может полагаться на тот факт, что хеш-функция всегда будет предоставлять уникальное хеш-значение для каждого отдельного ключа (т. е. она должна иметь возможность обрабатывать коллизии), поэтому ей нужен способ сравнения двух заданных ключей. для точного соответствия. Вы можете реализовать это либо как класс, который переопределяет
operator()или как специализацияstd::equalили - проще всего - перегрузкойoperator==()для вашего типа ключа (как вы уже сделали).
Сложность хеш-функции заключается в том, что если ваш тип ключа состоит из нескольких элементов, у вас обычно есть хеш-функция, которая вычисляет значения хеш-функции для отдельных элементов, а затем каким-то образом объединяет их в одно значение хеш-функции для всего объекта. Для обеспечения хорошей производительности (т. Е. Нескольких коллизий) вы должны тщательно продумать, как объединить отдельные значения хеш-функции, чтобы избежать слишком частого получения одинакового вывода для разных объектов.
Достаточно хорошей отправной точкой для хеш-функции является та, которая использует битовое смещение и битовое XOR для объединения отдельных хеш-значений. Например, предполагая тип ключа, подобный этому:
struct Key
{
std::string first;
std::string second;
int third;
bool operator==(const Key &other) const
{ return (first == other.first
&& second == other.second
&& third == other.third);
}
};
Вот простая хеш-функция (адаптированная из той, которая использовалась в примере cppreference для пользовательских хеш-функций):
namespace std {
template <>
struct hash<Key>
{
std::size_t operator()(const Key& k) const
{
using std::size_t;
using std::hash;
using std::string;
// Compute individual hash values for first,
// second and third and combine them using XOR
// and bit shifting:
return ((hash<string>()(k.first)
^ (hash<string>()(k.second) << 1)) >> 1)
^ (hash<int>()(k.third) << 1);
}
};
}
С этим на месте, вы можете создать экземпляр std::unordered_map для типа ключа:
int main()
{
std::unordered_map<Key,std::string> m6 = {
{ {"John", "Doe", 12}, "example"},
{ {"Mary", "Sue", 21}, "another"}
};
}
Это будет автоматически использовать std::hash<Key> как определено выше для вычислений значения хеша, и operator== определяется как функция-член Key для проверки на равенство.
Если вы не хотите специализировать шаблон внутри std Пространство имен (хотя в данном случае это совершенно законно), вы можете определить хеш-функцию как отдельный класс и добавить ее в список аргументов шаблона для карты:
struct KeyHasher
{
std::size_t operator()(const Key& k) const
{
using std::size_t;
using std::hash;
using std::string;
return ((hash<string>()(k.first)
^ (hash<string>()(k.second) << 1)) >> 1)
^ (hash<int>()(k.third) << 1);
}
};
int main()
{
std::unordered_map<Key,std::string,KeyHasher> m6 = {
{ {"John", "Doe", 12}, "example"},
{ {"Mary", "Sue", 21}, "another"}
};
}
Как определить лучшую хэш-функцию? Как сказано выше, определение хорошей хеш-функции важно, чтобы избежать коллизий и получить хорошую производительность. Для действительно хорошего вы должны принять во внимание распределение возможных значений всех полей и определить хеш-функцию, которая проецирует это распределение в пространство возможных результатов как можно более широкое и равномерное распределение.
Это может быть сложно; описанный выше метод XOR/ битового сдвига, вероятно, неплохое начало. Для лучшего начала вы можете использовать hash_value а также hash_combine шаблон функции из библиотеки Boost. Первый действует так же, как std::hash для стандартных типов (недавно также включая кортежи и другие полезные стандартные типы); последнее помогает вам объединить отдельные значения хеша в одно. Вот переписать хеш-функцию, которая использует вспомогательные функции Boost:
#include <boost/functional/hash.hpp>
struct KeyHasher
{
std::size_t operator()(const Key& k) const
{
using boost::hash_value;
using boost::hash_combine;
// Start with a hash value of 0 .
std::size_t seed = 0;
// Modify 'seed' by XORing and bit-shifting in
// one member of 'Key' after the other:
hash_combine(seed,hash_value(k.first));
hash_combine(seed,hash_value(k.second));
hash_combine(seed,hash_value(k.third));
// Return the result.
return seed;
}
};
И вот переписывание, которое не использует boost, но использует хороший метод объединения хэшей:
namespace std
{
template <>
struct hash<Key>
{
size_t operator()( const Key& k ) const
{
// Compute individual hash values for first, second and third
// http://stackru.com/a/1646913/126995
size_t res = 17;
res = res * 31 + hash<string>()( k.first );
res = res * 31 + hash<string>()( k.second );
res = res * 31 + hash<int>()( k.third );
return res;
}
};
}
Я думаю, джогоджапан дал очень хороший и исчерпывающий ответ. Вы обязательно должны взглянуть на это, прежде чем читать мой пост. Тем не менее, я хотел бы добавить следующее:
- Вы можете определить функцию сравнения для
unordered_mapотдельно, вместо использования оператора сравнения равенства (operator==). Это может быть полезно, например, если вы хотите использовать последний для сравнения всех членов двухNodeобъекты друг к другу, но только некоторые конкретные члены в качестве ключаunordered_map, - Вы также можете использовать лямбда-выражения вместо определения хеш-функций и функций сравнения.
В общем, для вашего Node класс, код может быть записан следующим образом:
using h = std::hash<int>;
auto hash = [](const Node& n){return ((17 * 31 + h()(n.a)) * 31 + h()(n.b)) * 31 + h()(n.c);};
auto equal = [](const Node& l, const Node& r){return l.a == r.a && l.b == r.b && l.c == r.c;};
std::unordered_map<Node, int, decltype(hash), decltype(equal)> m(8, hash, equal);
Заметки:
- Я просто повторно использовал метод хеширования в конце ответа jogojapan, но вы можете найти идею для более общего решения здесь (если вы не хотите использовать Boost).
- Мой код, возможно, слишком минимизирован. Для немного более читаемой версии, пожалуйста, смотрите этот код на Ideone.
Самый простой возможный полный запускаемый пример копирования / вставки использования настраиваемого класса в качестве ключа для
unordered_map (базовая реализация разреженной матрицы):
// UnorderedMapObjectAsKey.cpp
#include <iostream>
#include <vector>
#include <unordered_map>
struct Pos
{
int row;
int col;
Pos() { }
Pos(int row, int col)
{
this->row = row;
this->col = col;
}
bool operator==(const Pos& otherPos) const
{
if (this->row == otherPos.row && this->col == otherPos.col) return true;
else return false;
}
struct HashFunction
{
size_t operator()(const Pos& pos) const
{
size_t rowHash = std::hash<int>()(pos.row);
size_t colHash = std::hash<int>()(pos.col) << 1;
return rowHash ^ colHash;
}
};
};
int main(void)
{
std::unordered_map<Pos, int, Pos::HashFunction> umap;
// at row 1, col 2, set value to 5
umap[Pos(1, 2)] = 5;
// at row 3, col 4, set value to 10
umap[Pos(3, 4)] = 10;
// print the umap
std::cout << "\n";
for (auto& element : umap)
{
std::cout << "( " << element.first.row << ", " << element.first.col << " ) = " << element.second << "\n";
}
std::cout << "\n";
return 0;
}
Для типа перечисления я думаю, что это подходящий способ, и разница между классами заключается в том, как вычислить хеш-значение.
template <typename T>
struct EnumTypeHash {
std::size_t operator()(const T& type) const {
return static_cast<std::size_t>(type);
}
};
enum MyEnum {};
class MyValue {};
std::unordered_map<MyEnum, MyValue, EnumTypeHash<MyEnum>> map_;
STL Не предоставляет хеш-функцию для пар. Вам нужно реализовать его самостоятельно и либо указать в качестве параметра шаблона, либо поместить в пространство имен std, откуда он будет автоматически выбран. Следуя https://github.com/HowardHinnant/hash_append/blob/master/n3876.h , очень полезно для реализации пользовательских хэш-функций для структур. Более подробная информация подробно описана в других ответах на этот вопрос, поэтому я не буду повторять это. Также есть похожая штука (
hash_combine) в Boost.
Нам нужно сделать два пункта:
- минимизировать столкновения
- хеш(а,б)!=хеш(б,а)
Я предлагаю такой способ:
численно имеем такой алгоритм:
a = hash1
b = hash2
p = a+b
result_hash = p*(p+1)/2+b
но если мы уменьшим алгоритм, на коллизии это не повлияет:
a = hash1
b = hash2
p = a+b
result_hash = p*p+b
мы можем проверить это (в Python):
N=256 # number of different values of hash
d = {}
for a in range(N):
for b in range(N):
p = a+b
x = (p*p+b)%N
if x in d:
d[x]+=1
else:
d[x]=1
#print(format(x,'04b'),end='\t')
#print()
print(max(v for k,v in d.items()))
Итак, наконец у нас есть такие методы:
p = a+b
return p*p+b
return (a<<1)^b
return a*31+b
return (17*31+a)*31+b
Ответы здесь были весьма полезными, но я все еще изо всех сил пытался понять это, поэтому, возможно, мои извлеченные уроки будут полезны. У меня была немного уникальная ситуация по сравнению с ОП; мойkeyбыл настраиваемым классом UUID , которым я не владел. В том, что я считаю ошибкой/оплошностью, этот класс не определил хеш-функцию или перегрузку дляoperator()(это определилоoperator==, так что я был установлен там). Да, у меня был исходный код, но он был широко распространен и контролировался, поэтому модифицировать его было невозможно. Я хотел использовать этот UUID в качестве ключа вstd::unordered_mapчлен, как
std::unordered_map<UUID, MyObject> mapOfObjs_;
В Visual Studio я в конце концов остановился на этом решении:
// file MyClass.h
namespace myNamespace
{
static auto staticUuidHashFunc = [](const UUID& n)
{
// XORed the most and least significant bits, not important
}
...
class MyClass
{
...
private:
std::unordered_map<UUID, std::unique_ptr<MyObject>, decltype(staticUuidHashFunc)> mapOfObjs_;
};
}
Это отлично работало в Windows. Однако, когда я, наконец, перенес свой код в gcc в Linux, я получил предупреждение (перефразируя)
'MyClass'есть поле'mapOfObjs_'чей тип использует анонимное пространство имен
Я даже получил это предупреждение со всеми отключенными предупреждениями, поэтому gcc должен считать это довольно серьезным. Я погуглил и нашел этот ответ , в котором говорилось, что мне нужно переместить код хеш-функции в файл .cpp.
В этот момент я также попытался получить класс UUID:
// file MyClass.h
namespace myNamespace
{
struct myUuid : public UUID
{
// overload the operator()
};
...
// and change my map to use this type
std::unordered_map<myUuid, std::unique_ptr<MyObject>> mapOfObjs_;
}
Однако это принесло свой собственный набор проблем. А именно, все части кода, которые использовали (теперь родительский)UUIDclass были несовместимы с моей картой, например:
void MyClass::FindUuid(const UUID& id)
{
// doesn't work, can't convert `id` to a `myUuid` type
auto it = mapOfObjs_.find(id);
...
}
теперь был сломан. Я не хотел менять весь этот код, поэтому я остановился на этом и вернулся к решению «поместить код в файл .cpp». Тем не менее, я упорно пытался сделать несколько вещей, чтобы сохранить хеш-функцию в файле .h. Чего я действительно пытался избежать, так это удаления из определения хеш-функции, так как я не знал и не хотел выяснять, что это за тип. Итак, я попытался:
class MyClass
{
...
private:
static auto staticUuidHashFunc = [](const UUID& n)
{
// my hash function
}
};
Но это (или варианты этого) вернулись с ошибками, такими как «не может иметь статических инициализаторов в классе», «не могу использоватьautoздесь" и т. д.(у меня были жесткие требования к С++ 11). Поэтому я, наконец, согласился, что мне нужно относиться к этому как кstaticпеременную, объявите ее в заголовке и инициализируйте в файле .cpp. Как только я выяснил его тип, все было просто:
// MyClass.h
namespace myNamespace
{
class MyClass
{
...
private:
static std::function<unsigned long long(const UUID&)> staticUuidHashFunc;
std::unordered_map<UUID, std::unique_ptr<MyObject>, decltype(staticUuidHashFunc)> mapOfObjs_;
};
}
И, наконец, в файле .cpp:
// MyClass.cpp
namespace myNamespace
{
std::function<unsigned long long(const UUID&)> MyClass::staticUuidHashFunc = [](const UUID& n)
{
// the hash function
};
MyClass::MyClass()
: mapOfObjs_{ std::unordered_map<UUID, std::unique_ptr<MyObject>, decltype(staticUuidHashFunc)> (MyClass::NUMBER_OF_MAP_BUCKETS, staticUuidHashFunc)}
{ }
...
}
Ключевым моментом было определение статической хеш-функции в файле .cpp. После этого и Visual Studio, и gcc остались довольны.
проверьте следующую ссылку https://www.geeksforgeeks.org/how-to-create-an-unordered_map-of-user-defined-class-in-cpp/ для получения более подробной информации.
- пользовательский класс должен реализовывать оператор ==
- должен создать хеш-функцию для класса (для примитивных типов, таких как int, а также для таких типов, как string, хеш-функция предопределена)