[C++]: mapping vs find()

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" );

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

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