Является ли требование постоянной сложности метода Begin() слишком строгим для std::map? ⇐ C++

[Anonymous]

Код: Выделить всё

std::map

соответствует требованиям контейнера ([map.overview] p2).
для контейнера требуется следующее:

Код: Выделить всё

b.begin()

Результат: итератор; const_iterator для константы b.
Возвращает: итератор, ссылающийся на первый элемент в контейнере.
Сложность: константа.

- [container.requirements] Begin()
Мне это кажется непрактичным.
std::map обычно реализуется как самобалансирующееся двоичное дерево поиска, и вам обычно требуется логарифмическая сложность, чтобы найти самый левый узел, где должна начаться итерация.
Как бы вы реализовали Begin() с постоянным временем? Соответствуют ли этому стандартные реализации библиотек?

Подробнее здесь: https://stackoverflow.com/questions/778 ... for-stdmap