Hallo, ich hab zum erstem Mal ein Usecase für ein std::unordered_set, dies ist ähnlich der unordered_map aber eben nur mit dem Key und ohne assoziierenden Wert. Es fällt auf, dass das unordered_set kein mapping vom key zum Value unterstützt wie es die map kann. Es gibt kein Operator. Dies bedeutet der Zugriff muss bei set über find() stattfinden, was wiederum dazu führt, dass man zum löschen eines Elementes set.erase(set.find(111)); schreiben muss anstatt wie bei der map ohne find(). Ebenso beim Erstellen benötigt man set.insert(111); bei der Map kann man einfach schreiben map[111]. Meine Frage ist nun, wirkt sich diese Indirektion auch auf die Performance aus? Kann man durch das fehlende Mapping davon ausgehen, dass das Erstellen und Löschen von Einträgen bei unordered_set langsamer ist als bei der unordered_map? Oder tut intern das Mapping bei map durch den Operator genau das selbe wie find() oder insert() beim set? Grüße
Anton+ schrieb: > Es fällt auf, dass das unordered_set kein mapping vom key zum Value > unterstützt wie es die map kann. Es gibt kein Operator. Ja klar, ist ja auch kein Value da.
Sven P. schrieb: > Anton+ schrieb: >> Es fällt auf, dass das unordered_set kein mapping vom key zum Value >> unterstützt wie es die map kann. Es gibt kein Operator. > Ja klar, ist ja auch kein Value da. Mit Value meine ich in dem Satz nicht einen assoziierende Wert wie bei Map sondern den Wert des Keys den man bei map einfach in die Klammer schreibt und man beim set mit find() erst suchen lassen muss.
Anton+ schrieb: > Usecase für ein std::unordered_set Wenn Du wirklich unordered_set meinst: http://www.cplusplus.com/reference/unordered_set/unordered_set/erase/ Erase ist eine Überladene Memberfunction (method overload) -- erase key ist also vorhanden. Hier (2) und im Beispiel myset.erase ( "France" );
Anton+ schrieb: > Tatsache! da war ich mit der Annahme völlig auf dem Holzweg :-) Jein, ich glaube eher, deine Vorstellung von einem set ist nicht ganz reif, daher meinte provokante Antwort als Denkanstoß... Du kannst dir in den allermeisten Fällen ein set vorstellen wie ein map, bei dem alle Einträge irgendeinen uninteressanten Wert haben, weil dich ja ohnehin nur die Keys interessieren. Manche Bibliotheken (Qt etwa) implementieren ihr set<T> auch einfach als map<T, void>. Folglich gibt es auch keine Indirektion, wie du vermutest. find() sucht in O(log n) nach dem Key, und operator[] tut es genauso, und at() auch. Ganz naiv könnte man at(x) als *find(x) implementieren. operator[] ist nichts anderes, nur dass es einen Wert einfügt, falls der Key nicht existiert.
Sven P. schrieb: > find() sucht > in O(log n) nach dem Key, Erstens, er hatte nach std::unordered_set gefragt, und das ist in der Regel als Hash Table implementiert, also O(1). Siehe https://stackoverflow.com/questions/1349734/why-would-anyone-use-set-instead-of-unordered-set Und letztendlich hatte er nur übersehen, dass erase() sehr wohl einen key als Parameter akzeptiert.
Stefan S. schrieb: > Erstens, er hatte nach std::unordered_set gefragt, und das ist in der > Regel als Hash Table implementiert, also O(1). Kann sein, dann wäre es aber immer noch maximal O(n) und nur im Mittel O(1). Wo der TO ja so um Peformance besorgt ist. Stefan S. schrieb: > Und letztendlich hatte er nur übersehen, dass erase() sehr wohl einen > key als Parameter akzeptiert. Seiner Beschreibung nach hat(te) er noch mehr übersehen...
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.