Komplaexitaet von std::tr1::unordered_map::size()
-
Ist die irgendwo definiert/festgelegt, oder stehts dem Implementierer frei, da zu meistern wie er lustig ist?
Selbst wenn sie nicht vorgegeben ist, unordered_map ist wird vermutlich ja als Hashmap implementiert sein, somit sollte size() idR O(1) haben. Oder gibts andere bekannte Implementierungsmoeglichkeiten?
-
Warum sollte irgendein beliebiger Container, wie er auch immer implementiert ist, für size eine andere Komplexität haben als O(1)?
-
manni66 schrieb:
Warum sollte irgendein beliebiger Container, wie er auch immer implementiert ist, für size eine andere Komplexität haben als O(1)?
Es ist nicht immer Praktisch, und fuer manche Anwendungsbeispiele ist es sogar hinderlich, wenn man size immer mitfuehrt. Nimm z. B. die 3. Variante von folgender Methode: http://www.cppreference.com/wiki/stl/list/splice
(EDIT: aus diesem Grund ist z. B. std::list::size() nicht garantiert O(1) ).
-
Bietet denn unordered_map irgendwas splice-artiges an, was dazu führen könnte, dass size() nicht O(1) implementierbar ist?
-
TR1 schweigt sich über die Komplexität von unordered_map::size() aus.
Die GNU-Implementation hat für alle unordered_-Container eine size()-Methode konstanter Komplexität, und ich sehe eigentlich auch keinen Grund, warum jemand das anders machen sollte.
Man könnte sich vielleicht auf Tabelle 65 (Container requirements) im Standard berufen, in der size() mit "(Note A)" markiert ist, was bedeutet:
ISO/IEC 14882:2003 schrieb:
Those entries marked ‘‘(Note A)’’ should have constant complexity.
So wie ich das lese, bedeutet das, dass size() generell konstante Komplexität haben sollte, sofern es keine guten Gründe dagegen gibt (wie bei std::list). Soweit ich weiß, ist der gesamten Informatik bislang kein Grund bekannt, bei einer Hashtable die Größe nicht mitzuführen - wenn du also nicht an total bekiffte Compilerentwickler (oder so geniale, dass sie einen sehr guten Grund dafür aus dem Hut zaubern und dies mit Sicherheit in die Dokumentation schreiben) gerätst, solltest du davon ausgehen können, dass unordered_map::size() konstante Komplexität hat.
-
Danke, das bestaetigt meine Intuition.
