Is the constant complexity requirement of begin() too strict for std::map?

std::map meets the requirements of a container ([map.overview] p2).

container requires the following:

b.begin()

Result: iterator; const_iterator for constant b.

Returns: An iterator referring to the first element in the container.

Complexity: Constant.

- [container.requirements] begin()

This seems impractical to me. A std::map is commonly implemented as a self-balancing binary search tree, and you typically need logarithmic complexity to find the leftmost node, where iteration has to begin.

How would you implement begin() in constant time? Do standard library implementations actually comply with this?

The standard requires begin() to be constant time, and standard libraries do comply with this. The easiest way to do this is to store the leftmost node in a member.

In libstdc++ for example, see this comment:

// (1) the header cell is maintained with links not only to the root
// but also to the leftmost node of the tree, to enable constant
// time begin(), and to the rightmost node of the tree, to enable
// linear time performance when used with the generic set algorithms
// (set_union, etc.)