C++ unordered_map scheitern, wenn Sie mit einem Vektor als Schlüssel

Hintergrund: ich bin kommend aus der Java-Welt und ich bin ziemlich neu in C++ oder Qt.

Um zu spielen mit unordered_map, die ich geschrieben habe, das folgende einfache Programm:

#include <QtCore/QCoreApplication>
#include <QtCore>
#include <iostream>
#include <stdio.h>
#include <string>
#include <unordered_map>

using std::string;
using std::cout;
using std::endl;
typedef std::vector<float> floatVector;

int main(int argc, char *argv[]) {
    QCoreApplication a(argc, argv);

    floatVector c(10);
    floatVector b(10);

    for (int i = 0; i < 10; i++) {
        c[i] = i + 1;
        b[i] = i * 2;
    }

    std::unordered_map<floatVector, int> map;

    map[b] = 135;
    map[c] = 40;
    map[c] = 32;

    std::cout << "b -> " << map[b] << std::endl;
    std::cout << "c -> " << map[c] << std::endl;
    std::cout << "Contains? -> " << map.size() << std::endl;

    return a.exec();
}

Leider habe ich folgende Fehler, die nicht inspirierend. Es gibt nicht einmal eine Zeilennummer.

:-1: Fehler: collect2: ld zurückgegeben, 1 exit status

Jede Idee, der Ursprung des Problems?

Vielen Dank im Voraus.

Sie brauchen eine hash-Funktion nimmt einen vector<float>
Dies ist nicht ein runtime-Fehler.
Das war es, was ich dachte, war das problem zu kommen. Jedoch, es scheint mir, dass eine Klasse als Basis als Vektor sollte eine Standard-hash-Funktion. Wenn es nicht der Fall ist, könnten Sie mir erklären, wie ein oder zeigen Sie mir etwas material. Danke!!!
Vielen Dank für den Hinweis.
Gültige und interessante Frage, aber ich sehe nicht ein Anwendungsfall, wo es klug sein, um die Verwendung einer Liste, die als Schlüssel in einer map.
Die int ist das Ergebnis einer Berechnung aus dem der Vektor ist der Eingang. Das Ergebnis einmal berechnet werden müssen, um Zugang zu vielen Zeiten und schnell.

InformationsquelleAutor Pierre-Antoine | 2012-05-01

c++c++11 qt unordered-map vector

26

§23.2.5 Absatz 3 sagt:

Jeder ungeordnete assoziative container wird parametrisiert durch Key durch ein function-Objekt Typ Hash entspricht der Hash-Anforderungen (17.6.3.4) und fungiert als eine hash-Funktion für das argument die Werte des Typs Key, und durch ein binäres Prädikat Pred, die induziert eine aquivalenzrelation auf Werte des Typs Key.

Mit vector<float> als Key und nicht ausdrücklich hash-und äquivalenz-Prädikat-Typen bedeutet, dass die Standard - std::hash<vector<float>> und std::equal_to<vector<float>> verwendet werden.

Den std::equal_to für die äquivalenz-relation ist gut, denn es ist ein operator == für Vektoren, und das ist, was std::equal_to verwendet.

Gibt es jedoch keine std::hash<vector<float>> Spezialisierung, und das ist wahrscheinlich das, was der linker-Fehler, den Sie nicht zeigen uns sagt. Sie müssen Ihre eigenen hasher für diese zu arbeiten.

Einfache Art und Weise das schreiben so hasher ist die Verwendung boost::hash_range:
```
template <typename Container> //we can make this generic for any container [1]
struct container_hash {
    std::size_t operator()(Container const& c) const {
        return boost::hash_range(c.begin(), c.end());
    }
};
```
Dann können Sie verwenden:
```
std::unordered_map<floatVector, int, container_hash<floaVector>> map;
```
Natürlich, wenn Sie brauchen unterschiedliche Semantik der Geschlechter in der Karte, die Sie brauchen, um zu definieren, die hash-und äquivalenz-relation angemessen.

_{1. Vermeiden Sie es jedoch, diese für das hashing ungeordnete Container, verschiedene Aufträge produzieren unterschiedliche hashes, und die Reihenfolge, in der ungeordnete container ist nicht garantiert.}
- Vielen Dank das hat tatsächlich mein problem gelöst. Hinweis für Leute, die das gleiche problem haben: die Verwendung von boost::hash_range müssen Sie #include < - boost - /Funktions - /hash.hpp>
- Das ist buchstäblich die erste Sache auf, die doc-Seite. ;-]
- Martinho Fernandes : Wenn Sie noch beobachten, werden die Dokumente in dieser Seite zu sagen: "hash_range ist empfindlich auf die Reihenfolge der Elemente so wäre es nicht angemessen, dies durch eine ungeordnete container." Hat, die nahelegen, dass die obige Verwendung ist falsch?
- Ich denke, was das bedeutet, ist, dass der Aufruf hash_range (unordered_container) ist eine schlechte Idee, weil es kann zu unterschiedlichen Ergebnissen führen, jedes mal.
- aber warum hat die map<vector<int>, int> arbeiten Sie?
- Das ist, weil die Karte verwendet rote und schwarze Bäume auf das backend und nicht um die Art der gespeicherten Daten. In der Erwägung, unordered_map im wesentlichen muss eine hash-Funktion. Und es kann nur berechnet werden, sobald die Art der Daten, gespeichert in dem Vektor ermittelt.
InformationsquelleAutor R. Martinho Fernandes
3

Fand ich R. Martinho Fernandes Antwort ungeeignet für wettbewerbsfähige Programmierung da die meisten der Zeiten, die Sie haben, um mit einem IDE-und können nicht verwenden Sie eine externe Bibliothek wie boost. Sie können die folgende Methode verwenden, wenn Sie möchten, machen Sie das beste aus STL.

Wie bereits oben erwähnt, brauchen Sie nur zu schreiben, eine hash-Funktion. Und es sollte sich spezialisieren, für die Art von Daten, gespeichert in dem Vektor. Die folgenden hash-Funktion übernimmt int Typ Daten:
```
struct VectorHasher {
    int operator()(const vector<int> &V) const {
        int hash=0;
        for(int i=0;i<V.size();i++) {
            hash+=V[i]; //Can be anything
        }
        return hash;
    }
};
```
Beachten Sie, dass Sie jede Art von operation generiert einen hash. Sie müssen nur kreativ zu sein, so dass Kollisionen minimiert werden. Zum Beispiel hash^=V[i], hash|=V[i], hash+=V[i]*V[i] oder sogar hash+=(V[i]<<i)*(V[i]<<i)*(V[i]<<i) alle gültig bis natürlich, dein hash nicht überläuft.

Schließlich, um diesen hash-Funktion mit Ihrem unordered_map, wie folgt initialisieren:
```
unordered_map<vector<int>,bool,VectorHasher> hashMap;
```
- Sollte nicht der zweite template-parameter sein int statt bool?
- Es funktioniert mit jedem gestattet Datenstruktur/ - Typ(Karte, Vektor, set, queue, stack, int, float, ...etc). Hängt von Ihrem Anwendungsfall.
InformationsquelleAutor Chirag Arora

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.