unordered_map mit Paar als Schlüssel - nicht kompilieren

Ich versuche zum erstellen einer unordered_map zu anzeigen Paaren mit Ganzzahlen.

#include <unordered_map>

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

Habe ich eine Klasse, wo ich erklärt haben, eine Unordered_map als privates Mitglied.

Bin ich allerdings immer 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 bin nicht immer diese Fehlermeldung, wenn ich eine reguläre Karte wie map<pair<string, string>, int> statt einer unordered_map.

Ist es nicht möglich pair als Schlüssel im unsortierten Karten?

InformationsquelleAutor der Frage Mapplet | 2015-09-20

  1. 33

    Müssen Sie eine geeignete hash-Funktion für die Schlüssel zu geben. 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 funktionieren wird, aber nicht die besten hash-Eigenschaften†. Möchten Sie vielleicht einen Blick auf so etwas wie boost.hash_combine für höhere Qualität der Ergebnisse erzielt, wenn man die hashes.

    Für die Reale Welt verwenden: Boost bietet auch die Funktion set hash_value die bereits eine hash-Funktion für std::pair sowie std::tuple und die meisten standard-Containern.

    †genauer, es produziert zu viele Kollisionen. E. g., jedes symmetrische paar wird in der hash auf 0 und Paare, die sich nur durch permutation haben den gleichen hash. Dies ist wahrscheinlich gut für die Programmierung übung, aber kann schwer verletzt die Leistung der realen Welt code.

    InformationsquelleAutor der Antwort Baum mit Augen

  2. 4

    Meine bevorzugte Methode, dieses problem zu lösen ist, um eine key Funktion, verwandelt sich das paar in eine eindeutige ganze Zahl (oder jede hashable-Datentyp). Dieser Schlüssel ist nicht die Raute-Taste. Es ist die eindeutige ID der paar Daten, die dann optimal hashed durch die unordered_map. Zum Beispiel, Sie wollten, definieren Sie eine unordered_map von der Art

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

    Sind und Sie verwenden möchten Map[make_pair(i,j)]=value oder Map.find(make_pair(i,j)) zu betreiben, auf der Karte. Dann müssen Sie dem system mitteilen, wie Sie hash ein paar von ganzen zahlen make_pair(i,j). Anstatt, dass wir definieren können,

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

    und ändern Sie dann die Art der Karte, um

      unordered_map<size_t,double> Map;

    Wir können jetzt Map[key(i,j)]=value oder Map.find(key(i,j)) zu betreiben, auf der Karte. Jeder make_pair wird nun zum Aufruf der inline - key Funktion.

    Diese Methode garantiert, dass der key wird optimal gehasht, weil jetzt die hashing-Teil erledigt das system, die wählen immer die interne hash-Tabelle Größe prime, um sicherzustellen, dass jeder Eimer ist gleich wahrscheinlich sind. Aber Sie haben, um sich 100% sicher, dass die key ist einzigartig für jedes paar ist, d.h., keine zwei unterschiedliche Paare haben den gleichen Schlüssel, oder es kann sehr schwierig sein, bugs zu finden.

    InformationsquelleAutor der Antwort Zhuoran He

  3. 3

    Als Ihre Zusammenstellung Fehler zeigt, dass es keine gültige Instanziierung std::hash<std::pair<std::string, std::string>> in Ihrem std-namespace.

    Laut meinem compiler:

    Fehler C2338 Der C++ - Standard nicht bieten eine hash für diesen
    Typ. c:\program files (x86)\microsoft visual studio
    14.0\vc\include\xstddef 381

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

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

    InformationsquelleAutor der Antwort bku_drytt

  4. 3

    Für die pair-Taste können wir die Verwendung von boost-pair-hash-Funktion:

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

    Ebenso können wir die Verwendung von boost-hash für Vektoren,

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

    InformationsquelleAutor der Antwort Felix Guo

Schreibe einen Kommentar