Ik probeer een aangepaste klasse te gebruiken als sleutel voor een unordered_map, zoals het volgende:
#include <iostream>
#include <algorithm>
#include <unordered_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;
}
G++ geeft me echter de volgende foutmelding:
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
Ik denk dat ik de tell C++ nodig heb hoe de hash-klasse Nodemoet worden gebruikt, maar ik weet niet precies hoe ik dat moet doen. Hoe kan ik deze taken uitvoeren?
Antwoord 1, autoriteit 100%
Om std::unordered_map(of een van de andere ongeordende associatieve containers) te kunnen gebruiken met een door de gebruiker gedefinieerd sleuteltype, moet u twee dingen definiëren:
-
Een hash-functie; dit moet een klasse zijn die
operator()overschrijft en de hash-waarde berekent gegeven een object van het sleuteltype. Een bijzonder eenvoudige manier om dit te doen, is door de sjabloonstd::hashte specialiseren voor uw sleuteltype. -
Een vergelijkingsfunctie voor gelijkheid; dit is vereist omdat de hash niet kan vertrouwen op het feit dat de hash-functie altijd een unieke hash-waarde zal bieden voor elke afzonderlijke sleutel (dwz hij moet in staat zijn om met botsingen om te gaan), dus hij heeft een manier nodig om twee gegeven sleutels te vergelijken voor een exacte match. U kunt dit implementeren als een klasse die
operator()overschrijft, of als een specialisatie vanstd::equal, of – het gemakkelijkst van alles – door deoperator==()voor uw sleuteltype (zoals u al deed).
Het probleem met de hash-functie is dat als uw sleuteltype uit meerdere leden bestaat, u de hash-functie gewoonlijk hash-waarden voor de afzonderlijke leden laat berekenen en ze vervolgens op de een of andere manier combineert tot één hash-waarde voor het hele object. Voor goede prestaties (d.w.z. weinig botsingen) moet u goed nadenken over hoe u de afzonderlijke hash-waarden combineert om te voorkomen dat u te vaak dezelfde uitvoer voor verschillende objecten krijgt.
Een redelijk goed startpunt voor een hashfunctie is er een die bitverschuiving en bitsgewijze XOR gebruikt om de individuele hashwaarden te combineren. Bijvoorbeeld, uitgaande van een sleuteltype als dit:
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);
}
};
Hier is een eenvoudige hash-functie (aangepast van degene die wordt gebruikt in het cppreference-voorbeeld voor door de gebruiker gedefinieerde hash-functies):
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);
}
};
}
Als dit op zijn plaats is, kun je een std::unordered_mapinstantiëren voor het key-type:
int main()
{
std::unordered_map<Key,std::string> m6 = {
{ {"John", "Doe", 12}, "example"},
{ {"Mary", "Sue", 21}, "another"}
};
}
Het gebruikt automatisch std::hash<Key>zoals hierboven gedefinieerd voor de hash-waardeberekeningen, en de operator==gedefinieerd als lidfunctie van Keyvoor gelijkheidscontroles.
Als u de sjabloon niet wilt specialiseren in de stdnaamruimte (hoewel dit in dit geval volkomen legaal is), kunt u de hash-functie definiëren als een aparte klasse en deze toevoegen aan het sjabloonargument lijst voor de kaart:
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"}
};
}
Hoe definieer je een betere hashfunctie? Zoals hierboven vermeld, is het definiëren van een goede hashfunctie belangrijk om botsingen te voorkomen en goede prestaties te krijgen. Voor een echt goede moet je rekening houden met de verdeling van mogelijke waarden van alle velden en een hashfunctie definiëren die die verdeling projecteert naar een ruimte met mogelijke resultaten die zo breed en gelijkmatig mogelijk is verdeeld.
Dit kan moeilijk zijn; de XOR/bit-shifting methode hierboven is waarschijnlijk geen slecht begin. Voor een iets betere start kunt u de functiesjabloon hash_valueen hash_combineuit de Boost-bibliotheek gebruiken. De eerste werkt op een vergelijkbare manier als std::hashvoor standaardtypen (recentelijk ook inclusief tupels en andere nuttige standaardtypen); de laatste helpt je om individuele hash-waarden in één te combineren. Hier is een herschrijving van de hash-functie die de Boost-helperfuncties gebruikt:
#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;
}
};
En hier is een herschrijving die geen boost gebruikt, maar toch een goede methode gebruikt om de hashes te combineren:
namespace std
{
template <>
struct hash<Key>
{
size_t operator()( const Key& k ) const
{
// Compute individual hash values for first, second and third
// http://stackoverflow.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;
}
};
}
Antwoord 2, autoriteit 4%
Ik denk dat jogojapaneen zeer goed en uitgebreid antwoordheeft gegeven. Je moet het zeker eens bekijken voordat je mijn bericht leest. Ik wil echter het volgende toevoegen:
- Je kunt een vergelijkingsfunctie voor een
unordered_mapafzonderlijk definiëren, in plaats van de gelijkheidsvergelijkingsoperator (operator==) te gebruiken. Dit kan bijvoorbeeld handig zijn als u de laatste wilt gebruiken om alle leden van tweeNode-objecten met elkaar te vergelijken, maar alleen enkele specifieke leden als sleutel van eenunordered_map. - U kunt ook lambda-expressiesgebruiken in plaats van de hash- en vergelijkingsfuncties te definiëren .
Al met al zou de code voor uw Node-klasse als volgt kunnen worden geschreven:
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);
Opmerkingen:
- Ik heb zojuist de hash-methode aan het einde van het antwoord van jogojapan hergebruikt, maar je kunt het idee voor een meer algemene oplossing hier(als je Boost niet wilt gebruiken).
- Mijn code is misschien een beetje te verkleind. Voor een iets beter leesbare versie, zie deze code op Ideone.
Antwoord 3
De meest eenvoudig mogelijke kopieer/plak-compleet uitvoerbaar voorbeeld van het gebruik van een aangepaste klasse als de sleutel voor een unordered_map(basisimplementatie van een schaarse matrix):
// 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;
}
Antwoord 4
Voor ENUM-type, denk ik dat dit een geschikte manier is, en het verschil tussen de les is hoe u Hash-waarde kunt berekenen.
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_;
Antwoord 5
STL biedt geen hash-functie voor paren. U moet het zelf implementeren en specificeren als sjabloonparameter of in NameSpace Std, van waaruit deze automatisch wordt opgehaald. Volgende https://github.com/howardhinnant/hash_append/blob/master/n3876 .h is erg handig voor het implementeren van aangepaste hash-functies voor structures. Meer details worden goed uitgelegd in de andere antwoorden op deze vraag, dus ik zal dat niet herhalen. Er is ook soortgelijke dingen (hash_combine) IN DE BOOST.
Antwoord 6
Controleer de volgende link HTTPS://WWW.GEEKSFORGEEKS.org/How-to-create-an-unordered_map-of-user-definined-class-in-cpp/ voor meer informatie.
- De aangepaste klasse moet de ==-operator
- moet een hash-functie maken voor de klasse (voor primitieve typen zoals INT en ook typen zoals string De Hash-functie is vooraf gedefinieerd)
implementeren