Ist die konstante Komplexitätsanforderung von begin() zu streng für std::map? ⇐ C++

[Anonymous]

Code: Select all

std::map

erfüllt die Anforderungen eines Containers ([map.overview] p2).
Container erfordert Folgendes:

Code: Select all

b.begin()

Ergebnis: iterator; const_iterator für Konstante b.
Rückgaben: Ein Iterator, der auf das erste Element im Container verweist.
Komplexität: Konstante.

- [container.requirements] begin()
Das erscheint mir unpraktisch.
Ein std::map wird üblicherweise als selbstausgleichender binärer Suchbaum implementiert, und Sie benötigen normalerweise logarithmische Komplexität, um den Knoten ganz links zu finden, an dem die Iteration beginnen muss.
Wie würden Sie begin() in konstanter Zeit implementieren? Erfüllen Standardbibliotheksimplementierungen dies tatsächlich?