Frage zu std::unordered_set

Hallo,

ich benötige einen container, in dem ich schnell suchen kann. eine map kommt nicht in frage. nun habe ich überlegt eine std::unordered_set einzusetzen. die frage ist, wenn ich eine klasse A habe, die ich in den std::unordered_set reinstecken will, wie sieht dann die methode aus, die dafür implementiert werden muss.

ich denke A muss irgend einen hash liefern oder?

cooky451

http://stackoverflow.com/questions/9927208/requirements-for-elements-in-stdunordered-set

http://en.cppreference.com/w/cpp/utility/hash

SeppJ

bobo7788 schrieb:

Hallo,

ich benötige einen container, in dem ich schnell suchen kann.

Erzähl mal mehr.

eine map kommt nicht in frage.

map? Meinst du set? Warum kommt es nicht in Frage?

nun habe ich überlegt eine std::unordered_set einzusetzen. die frage ist, wenn ich eine klasse A habe, die ich in den std::unordered_set reinstecken will, wie sieht dann die methode aus, die dafür implementiert werden muss.

ich denke A muss irgend einen hash liefern oder?

Ja. Du kannst die Hashfunktion entweder als zweiten Templateparameter des unordered_set angeben oder du kannst std::hash für deine Klasse spezialisieren. Dies ist eine der ausnahmen, wo man selber neue Funktionalität in den Namensraum std einbringen darf.

Je nachdem, was du auf die erste Gegenfrage antwortest, kommen aber eventuell auch ganz andere Strukturen in Frage. Zum Beispiel ein sortierter Sequenzcontainer.

SeppJ schrieb:

Je nachdem, was du auf die erste Gegenfrage antwortest, kommen aber eventuell auch ganz andere Strukturen in Frage. Zum Beispiel ein sortierter Sequenzcontainer.

ok, die klasse A hat ein member, das eindeutig ist, nämlich einen string.

in der regel wird nach einem objekt mit einem spezifischen string gesucht, aber eben nicht immer.

dennoch soll beispielsweise die suche nach einem objekt mit dem string "adam" möglichst sehr schnell ablaufen.

es werden sehr viele objekte vom typ A im container landen. deshalb scheidet std::vector aus.

es werden sehr viele objekte vom typ A im container landen. deshalb scheidet std::vector aus.

Die Aussage ist nicht wirklich plausibel.

Manchmal kann es sinvoll sein, eindeutige Strings in fortlaufende IDs zu mappen. Dann muss jeder String nur einmal gesucht werden und dann geht der Zugriff enorm schnell.

typedef int class_id;

struct string_mappers {
  std::unordered_map<std::string, class_id> strings;
  class_id get(std::string const& s) {
    class_id& id = strings[s];
    if (id == 0) id = strings.size(); // new element
    return id;
  }
};

class KlasseA { // von der du geredet hast
  class_id id;
};

string_mappers allIds;
std::vector<KlasseA> sehrVieleObjekteVomTypA;

KlasseA& search_for(class_id id) { return sehrVieleObjekteVomTypA[id]; }

// nach "adam" suchen:
static class_id adam_id = allIds.get("adam"); // muss ich nur einmal suchen
KlasseA& adam = search_for(adam_id);

Wutz

Nimm die unordered_map, mit dem eindeutigen string als key und der Klasse als value, wobei hier das string-Element natürlich redundant ist und du Speicher sparen kannst, wenn du es hier einfach weglässt.
Zunächst kannst du erstmal die von deinem Compiler eingebaute string-Hashfunktion nehmen und wenn du einen repräsentativen Datenbestand simulieren kannst, kannst du immer noch eigene Hash-Funktionen ausprobieren, ob sie denn schneller arbeiten.
Das Suchen nach anderen Kriterien als dem String in deiner großen Map wird dann allerdings langsam sein und sollte auf Ausnahmefälle beschränkt bleiben.

Eisflamme

Nimm die unordered_map, mit dem eindeutigen string als key und der Klasse als value, wobei hier das string-Element natürlich redundant ist und du Speicher sparen kannst, wenn du es hier einfach weglässt.

Sehr böse. Redundanz kann alle möglichen "Anomalien" begünstigen und den String aus der Klasse zu nehmen, ~~um Speicher zu sparen~~ um diese "Anomalien" (keine DB, aber der Begriff passt hier trotzdem, finde ich) zu vermeiden verstümmelt die Klasse auf Grund der Einsatzmethode, das kann man doch nicht empfehlen.

Ich fände std::inordered_set okay, dann ist der Hash eben nur vom string abhängig und gut. Leider sind Sets ... "ungeschickt" implementiert und man kann nicht so einfach Werte ändern, selbst wenn diese die Ordnung nicht ändern, das ist bei unordered_set auch so. Wenn sich eh nichts ändern, sondern nur löschen oder einfügen lassen soll, ist das natürlich egal.

Wonach soll sonst gesucht werden? boost::multiindex legt auch Hierarchien an, man kann aber eben mehrere Indizes anlegen und hat die Probleme mit der Set-Unlogik nicht.

Ja, Redundanzen will ich natürlich vermeiden.

Bei einem unordered_set habe ich natürlich das Problem, dass ich nicht genau nach einen Key vom Typ std::string suchen kann.

Die Objekte A innerhalb von dem set haben zwar den std::string als Member, aber der Aufruf set.find() erwartet natürlich ein Objekt A und kein std::string.

Eisflamme

Du kannst doch eigene Vergleichsoperatoren für das Set definieren. Oder für die Klasse selbst eben, wenn das eben das Haupt-Vergleichskriterium ist.

Was spricht denn gegen ein normales set? Da gibt es keinen Overhead wegen doppelten Strings oder Hashfunktionen.

struct A{
    std::string name;
    //anderer Kram
};

std::set<A, [](const A &a1, const A &a2){return a1.name < a2.name;}> Aset;

//noch eine Hilfsfunktion dazu:
const A *findObject(const std::string &s){
    static A a; //dummy A zum Suchen
    a.name = s;
    auto it = Aset.find(a);
    if (it == Aset.end()) //das kann man sicher noch hübscher machen, vielleicht einfach den Iterator zurück geben
        return 0;         //oder den Dummy oder den entsprechenden Wert ins set einfügen und eine Referenz darauf zurück geben
    return &(*it);
}

Dann noch eine Changefunktion bauen, die bei Ändern von A::name das Element aus dem Set entfernt, den Namen ändert und wieder hinzufügt und ansonsten per const_cast direkt ändert.

Eisflamme schrieb:

Du kannst doch eigene Vergleichsoperatoren für das Set definieren. Oder für die Klasse selbst eben, wenn das eben das Haupt-Vergleichskriterium ist.

Richtig. Ich kann aber nicht nach dem Objekt meiner Wahl mit set.find("MyKey") suchen. Ich muss mit set.find(MyObject) suchen.

http://www.boost.org/libs/intrusive/

nwp3 schrieb:

Was spricht denn gegen ein normales set?

Eigentlich nicht viel.

Ich habe es jetzt tatsächlich mit einem std::set realisiert und verwende einfach ein static Objekt, dem ich den key zuweise.

Die Laufzeit bei vielen Elementen (>100000) ist mit set.find einfach deutlich besser, als mit std::find_if.

Es ist sogar noch besser, als bei einer std::map mit direktem Indexzugriff mymap[key]. Das hat mich erstaunt. Beide liegen aber im selben Bereich, die Abweichung betrifft nur die Zahl hinter dem Komma.

=> Die Laufzeit ist ja bei beiden O(logn)

SeppJ

bobo7788 schrieb:

Es ist sogar noch besser, als bei einer std::map mit direktem Indexzugriff mymap[key]. Das hat mich erstaunt. Beide liegen aber im selben Bereich, die Abweichung betrifft nur die Zahl hinter dem Komma.

=> Die Laufzeit ist ja bei beiden O(logn)

Das ist sicherlich nur eine Messschwankung. map sollte (wenn die Macher einigermaßen faul waren) als ein set<pair<key, value>> mit passender Vergleichsfunktion und den map-Methoden implementiert sein.

bobo7788 schrieb:

Ich habe es jetzt tatsächlich mit einem std::set realisiert und verwende einfach ein static Objekt, dem ich den key zuweise.

Bin mir noch unsicher, ob ich mich freuen oder ärgern soll, dass du dasselbe erfunden hast was ich gepostet hatte. Ich sag einfach mal "Great minds think alike" und freue mich

SeppJ schrieb:

bobo7788 schrieb:

Es ist sogar noch besser, als bei einer std::map mit direktem Indexzugriff mymap[key]. Das hat mich erstaunt. Beide liegen aber im selben Bereich, die Abweichung betrifft nur die Zahl hinter dem Komma.

=> Die Laufzeit ist ja bei beiden O(logn)

Das ist sicherlich nur eine Messschwankung. map sollte (wenn die Macher einigermaßen faul waren) als ein set<pair<key, value>> mit passender Vergleichsfunktion und den map-Methoden implementiert sein.

Die Schwankung scheint aber regelmäßig zu sein. Bei 500000 Elementen habe ich im Release mit std::find_if eine Zeit von 0.00465415, mit set.find 1.20115e-006 und mit map[key] einer Zeit von 4.20402e-006.

map uns set sind praktisch gleichauf, aber dennoch schneidet set immer ein klitzewenig besser ab.

SeppJ

Ist 10^-6 Sekunden überhaupt noch innerhalb der Auflösung des Timers? Eventuell misst du hier die kleine if-Abfrage, die bei der map bei nicht-finden ein neues Element anlegt, wohingegen set dann einfach end() liefert. Versuch doch mal das find von der map anstatt operator[].

P.S.: Das heißt, deine set- und map-Codes sind nicht äquivalent, falls ein Element nicht vorhanden sein sollte. Ich nehme an, das hast du schon bedacht, oder?

Eisflamme

Die Laufzeit bei vielen Elementen (>100000) ist mit set.find einfach deutlich besser, als mit std::find_if.

Ja ach, find_if ist ja eine lineare Suche. Vergleich's mit std::binary_search (Sortierung natürlich vorausgesetzt).

Set ist schon echt okay, wenn man nichts ändern will.

SeppJ schrieb:

Ist 10^-6 Sekunden überhaupt noch innerhalb der Auflösung des Timers? Eventuell misst du hier die kleine if-Abfrage, die bei der map bei nicht-finden ein neues Element anlegt, wohingegen set dann einfach end() liefert. Versuch doch mal das find von der map anstatt operator[].

P.S.: Das heißt, deine set- und map-Codes sind nicht äquivalent, falls ein Element nicht vorhanden sein sollte. Ich nehme an, das hast du schon bedacht, oder?

Jup, das hatte ich berücksichtigt. Die Messung habe ich mit dem QueryPerformanceCounter durchgeführt.

Aber wie gesagt, sowohl set, als auch map haben O(logn) und liegen praktisch gleichauf. Man merkt bei std::find_if deutlich O(n).