webentwicklung-frage-antwort-db.com.de

unordered_map mit Schlüsselpaar - nicht kompilierend

Ich versuche, eine unordered_map zu erstellen, um Paare mit ganzen Zahlen abzubilden. 

#include <unordered_map>

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;

Ich habe eine Klasse, in der ich eine Unordered_map als privates Mitglied deklariert habe. 

Ich erhalte jedoch diese Fehlermeldung, wenn ich versuche zu kompilieren:

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: Implicit instantiation of undefined template 'std::__1::hash<std::__1::pair<std::__1::basic_string<char>, std::__1::basic_string<char> > >'

Ich erhalte diese Fehlermeldung nicht, wenn ich eine normale Map wie map<pair<string, string>, int> anstelle einer ungeordneten Map verwende.

Kann pair nicht als Schlüssel in ungeordneten Karten verwendet werden?

c++dictionarykeyunordered-mappair
36
Mapplet

Sie müssen eine geeignete Hash-Funktion für Ihren Schlüsseltyp bereitstellen. Ein einfaches Beispiel:

#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;
}

Dies funktioniert, hat aber nicht die besten Hash-Eigenschaften†. Wenn Sie die Hashes kombinieren, möchten Sie vielleicht etwas wie boost.hash_combine sehen, um bessere Ergebnisse zu erhalten.

Für den praktischen Einsatz: Boost bietet auch die Funktion set hash_value , die bereits eine Hashfunktion für std::pair sowie std::Tuple und die meisten Standardcontainer bereitstellt.

†Genauer gesagt, werden zu viele Kollisionen erzeugt. Zum Beispiel wird jedes symmetrische Paar einen Hashwert von 0 und Paare, die sich nur durch die Permutation unterscheiden, haben den gleichen Hashwert. Dies ist wahrscheinlich für Ihre Programmierübung in Ordnung, kann jedoch die Leistung von realem Code ernsthaft beeinträchtigen.

44
Baum mit Augen

Mein bevorzugter Weg, dieses Problem zu lösen, besteht darin, eine key-Funktion zu definieren, die Ihr Paar in eine eindeutige Ganzzahl (oder einen beliebigen Hash-Datentyp) umwandelt. Dieser Schlüssel ist nicht der Hash-Schlüssel. Es ist die eindeutige ID des Datenpaares, die vom unordered_map optimal gehasht wird. Sie wollten beispielsweise einen unordered_map des Typs definieren

  unordered_map<pair<int,int>,double> Map;

Und Sie möchten Map[make_pair(i,j)]=value oder Map.find(make_pair(i,j)) verwenden, um die Karte zu bearbeiten. Dann müssen Sie dem System mitteilen, wie ein Ganzzahlpaar make_pair(i,j) gehasht wird. Anstelle dessen können wir definieren

  inline size_t key(int i,int j) {return (size_t) i << 32 | (unsigned int) j;}

und ändern Sie dann den Typ der Karte in

  unordered_map<size_t,double> Map;

Wir können jetzt Map[key(i,j)]=value oder Map.find(key(i,j)) verwenden, um auf der Karte zu arbeiten. Jeder make_pair ruft jetzt die inline key-Funktion auf.

Diese Methode garantiert, dass der Schlüssel optimal gehasht wird, da der Hash-Teil jetzt vom System ausgeführt wird. Dabei wird immer die interne Hash-Tabellengröße als Primwert ausgewählt, um sicherzustellen, dass jeder Bucket gleich wahrscheinlich ist. Sie müssen sich jedoch zu 100% sicher sein, dass key für jedes Paar eindeutig ist, d. H., Zwei verschiedene Paare können nicht denselben Schlüssel haben oder es ist sehr schwierig, Fehler zu finden.

6
Zhuoran He

Für die Pair-Taste können wir die Boost-Pair-Hash-Funktion verwenden:

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
using namespace std;

int main() {
  unordered_map<pair<string, string>, int, boost::hash<pair<string, string>>> m;

  m[make_pair("123", "456")] = 1;
  cout << m[make_pair("123", "456")] << endl;
  return 0;
}

Ähnlich können wir Boost-Hash für Vektoren verwenden,

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
  unordered_map<vector<string>, int, boost::hash<vector<string>>> m;
  vector<string> a({"123", "456"});

  m[a] = 1;
  cout << m[a] << endl;
  return 0;
}
5
Felix Guo

Wie Ihr Kompilierungsfehler anzeigt, gibt es keine gültige Instanziierung von std::hash<std::pair<std::string, std::string>> in Ihrem std-Namespace.

Laut meinem Compiler:

Fehler C2338 Der C++ - Standard stellt hierfür keinen Hash bereit Art. C:\Programmdateien (x86)\Microsoft Visual Studio 14.0\vc\include\xstddef 381

Sie können Ihre eigene Spezialisierung für std::hash<Vote> wie folgt anbieten:

#include <string>
#include <unordered_map>
#include <functional>

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;

namespace std
{
    template<>
    struct hash<Vote>
    {
        size_t operator()(Vote const& v) const
        {
            // ... hash function here ...
        }
    };
}

int main()
{
    Unordered_map m;
}
3
bku_drytt

Wenn die Verwendung von pair nicht unbedingt erforderlich ist, können Sie map einfach zweimal verwenden.

#include <unordered_map>

using namespace std;
using Unordered_map = unordered_map<string, unordered_map<string, int>>;

Unordered_map um;
um["Region1"]["Candidate1"] = 10;
cout << um["Region1"]["Candidate1"];    // 10
2
Efreeto

In den Kommentaren zur Antwort von Baum mit Augen bat der Benutzer Joe Blackum ein Beispiel über die Verwendung von Lambda-Ausdrücken statt Definieren einer Hash-Funktion. Ich stimme der meinung von Baum mit Augen zu, dass dies die Lesbarkeit beeinträchtigen kann, insbesondere wenn Sie eine universellere Lösung implementieren möchten. Deshalb möchte ich mich kurz fassen, indem ich mich auf eine spezifische Lösung für std::pair<std::string, std::string> konzentriert, wie sie vom OP vorgestellt wird. Das Beispiel verwendet auch eine handcrafted Kombination von std::hash<std::string> Funktionsaufrufen:

using Vote = std::pair<std::string, std::string>;
auto hash = [](const Vote& v){
    return std::hash<std::string>()(v.first) * 31 + std::hash<std::string>()(v.second);
};
using Unordered_map = std::unordered_map<Vote, int, decltype(hash)>;
Unordered_map um(8, hash);

Code auf Ideone

0
honk

Ich weiß, dass dies im Vergleich zu anderen Antworten zu naiv ist, aber es gibt eine Problemumgehung.

Wenn Sie die Eingabe von Paaren nehmen, hashen Sie einfach das Paar mit einer anderen Ganzzahl in einem unordered_hash, während Sie die Eingabe übernehmen, und verwenden Sie diesen Integralwert dann indirekt zum Hashing des Paares, d. H.

unordered_hash<int, Vote> h;
using Unordered_map = unordered_map<i, int>; // i is corresponding value to pair
0
Gaurav Pant