Warum kann ich nicht kompilieren, ein unordered_map mit ein paar als Schlüssel?

Ich versuche zum erstellen einer unordered_map zuordnen-Paare mit ganzen zahlen:

#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 habe ein Unordered_map als privates Mitglied.

Bin ich aber immer folgende Fehlermeldung, wenn ich versuche zu kompilieren:

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: Implizite Instanziierung "undefined" template " std::__1::hash, std::__1::basic_string > >'

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 Mapplet | 2015-09-20

c++dictionary keyvaluepair unordered-map

52

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.

Sie verweisen hash_value aber der link geht zu hash. Ich denke hash ist der richtige Standort, weil docs für hash_value empfehlen hash. Ich dachte, ich würde Sie Bearbeiten, anstatt es selbst zu tun...
ist dokumentiert auf der Seite habe ich ein link. Hast du einen besseren link?
mit Augean Der link ist richtig, aber ich schlage vor, dass der text von dem link sagen, 'hash' anstatt 'hash_value'
Vorsichtig: "Paare, die sich nur durch permutation wird die gleiche hash". Um es unverblümt: pair_hash({a, b}) ==pair_hash({b, a}) ist selten das, was Sie wollen! (Der Täter ist dem XOR. return h1 ^(h2 << 1); sollte es beheben.)
Das ist etwas besser, aber noch nicht groß; z.B. die hashes von permuted noch ziemlich nah beieinander. Es gibt Fragen auf dieser Website auf wie man es richtig macht.

InformationsquelleAutor Baum mit Augen
9

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.

Viel Glück dabei, dass für pair<string,string> als OP will.
Auch wenn der OP das machen will für pair<string,string> - das ist doch ein guter Weg, dies zu tun für pair<int,int> weil key ist bijektive. Kann jemand helfen!

InformationsquelleAutor Zhuoran He

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 Felix Guo

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;
}
```
Ich denke du meinst const Vote& v
Abstimmung&" und "Stimme const&", sind genau die gleichen.stackoverflow.com/questions/5503352/const-before-or-const-after
Ich denke, dies ist Undefined Behavior: Es ist erlaubt hinzufügen von template-Spezialisierungen für alle standard-library-Vorlage auf den namespace std nur, wenn die Erklärung hängt davon ab, in einen benutzerdefinierten Typ und die Spezialisierung erfüllt alle Anforderungen, die original-Vorlage.

InformationsquelleAutor bku_drytt
0

Ich weiß, das ist zu naive Implementierung im Vergleich zu anderen Antworten, aber es gibt einen workaround.

Wenn Sie die Eingabe von Paaren, nur hash-das koppeln mit einem integer in ein unordered_hash während der Einnahme von input und verwenden Sie dann dieses integral den Wert indirekt auf die hash-pair, d.h.
```
unordered_hash<int, Vote> h;
using Unordered_map = unordered_map<i, int>; //i is corresponding value to pair
```
InformationsquelleAutor Gaurav Pant
0

In den Kommentaren auf der Antwort von Baum mit Augen, die Benutzer Joe Black gefragt nach einem Beispiel sich auf die Verwendung eines lambda-Ausdrücke statt der Definition einer hash-Funktion. Ich Stimme mit der Meinung von Baum mit Augen, dass dieser Schaden zufügen könnte, Lesbarkeit, vor allem, wenn Sie möchten, implementieren Sie eine weitere Universelle Lösung. Deshalb möchte ich, dass mein Beispiel kurz durch die Fokussierung auf eine spezifische Lösung für std::pair<std::string, std::string>, präsentiert von der OP. Das Beispiel verwendet auch eine handgefertigt Kombination von std::hash<std::string> Funktion ruft:
```
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

InformationsquelleAutor honk

Wenn mit pair ist nicht zwingend erforderlich, Sie können einfach mit Karte zweimal.

#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

InformationsquelleAutor Efreeto

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.