C ++ tut Beginn / Ende / rbegin / rend für std :: set, std :: map, usw. in konstanter Zeit durchführen?

Question

Für Datentypen wie std :: set und std :: map, wo Nachschlagen in logarithmischer Zeit auftritt, wird die Umsetzung erforderlich, um die beginnen und enden Iteratoren zu halten? Hat Zugriff auf Beginn und Ende impliziert eine Lookup, die in logarithmischer Zeit auftreten könnten?

Ich habe immer davon ausgegangen, dass beginnen und enden immer in konstanter Zeit auftreten, aber ich kann keine Bestätigung dafür in Josuttis finden. Nun, da ich arbeite an etwas, wo ich über die Leistung anal sein, ich möchte sicherstellen, dass meine Basen zu decken.

Danke

Answer 1

Sie passieren in konstanter Zeit. Ich bin auf Seite 466 der ISO suchen / IEC 14882: 2003 Standard:

Tabelle 65 - Container requiments

a.begin (); (konstante Komplexität)

a.end (); (konstante Komplexität)

Tabelle 66 - Reversible Container Anforderungen

a.rbegin (); (konstante Komplexität)

a.rend (); (konstante Komplexität)

Answer 2

Ja, nach http://www.cplusplus.com/reference/stl/, begin (), Ende () usw. sind alle O (1).

Answer 3

In der C ++ Standard Tabelle 65 in 23,1 (Container Requirements) Listen begin () und end () als konstante Zeit erfordert. Wenn Ihre Implementierung dieser verletzt, nicht entspricht.

Answer 4

Schauen Sie einfach auf dem Code, hier können Sie die Iteratoren in den std :: map in dem GNU libstdc siehe ++

std::map

Sie werden sehen, dass alle Ende Rend cend ... alle in konstanter Zeit umgesetzt werden.

Answer 5

obwohl

Seien Sie mit hash_map vorsichtig. begin () nicht konstant ist.

Answer 6

Für std :: set

beginnen: konstant, Ende: konstant, rbegin: Konstante, zerteilen: Konstante,

Für std :: map

Sie sind auch konstant (alle)

Wenn Sie irgendwelche Zweifel haben, nur überprüfen www.cplusplus.com