[C++]: mapping vs find()

[Anton+ (Gast)]

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

[Sven P. (Gast)]

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.

[Anton+ (Gast)]

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.

[Stefan S. (Gast)]

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+ (Gast)]

Tatsache! da war ich mit der Annahme völlig auf dem Holzweg :-)

[Sven P. (Gast)]

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.

[Stefan S. (Gast)]

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.

[Sven P. (Gast)]

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...