begin() 的恒定复杂度要求对于 std::map 来说是否过于严格？

Question

std::map

满足容器的要求（[map.overview] p2）。

容器需要以下内容：

b.begin()

结果：

iterator

；

const_iterator

表示常数

b

。

Returns：引用容器中第一个元素的迭代器。

复杂性：恒定。

- [容器.要求]

begin()

这对我来说似乎不切实际。

std::map

通常被实现为自平衡二叉搜索树，通常需要对数复杂度来找到迭代必须开始的最左边节点。

您将如何在恒定时间内实现

begin()

？标准库实现实际上符合这一点吗？

Answer 1

标准要求

begin()

为常数时间，标准库确实遵守这一点。

以 libstdc++ 为例，请参阅此评论：

// (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.)