关于C++迭代器时间复杂度的疑问

首先引用你提到的C++标准段落：

所有迭代器类别仅要求那些能以摊还常数时间实现的函数。因此，迭代器的要求表和概念定义未指定复杂度。
——[iterator.requirements.general] p13

(1) 关于摊还复杂度的困惑 #

这里的“摊还”指的是针对迭代器的任意合法操作序列，平均每个操作的时间复杂度为常数（O(1)）。单个操作可能在某些场景下耗时超过常数，但将一系列操作的总时间分摊到每个操作上后，每个操作的平均开销是常数。

你举的仅解引用一次的例子，依然可以推断其复杂度为O(1)——因为如果单个解引用操作的最坏情况不是常数时间，那么包含该操作的序列的摊还复杂度必然无法达到常数，这违反了标准的要求。标准用“摊还常数”来表述，是为了覆盖那些单个操作偶尔有额外开销，但整体序列平均下来满足常数的场景（比如某些迭代器的递增操作，可能在内部需要维护缓存或调整结构，但长期来看平均每次递增是O(1)）。

相关标准参考：C++标准中[definitions]章节对“摊还复杂度”的定义明确，摊还分析关注的是一系列操作的累计成本，而非单个操作的最坏情况；同时[iterator.requirements.general] p13的上下文强调，迭代器的核心操作（解引用、递增、比较等）必须能通过摊还常数时间的实现来满足迭代器类别的要求。

(2) 关于迭代器操作的困惑 #

迭代器的操作要求是由迭代器类别（如输入迭代器、双向迭代器、随机访问迭代器等）统一定义的，而每个容器的迭代器所属的类别是C++标准明确规定的。此外，容器的具体迭代器实现细节（如操作对应的底层行为），部分由容器的类别要求约束，部分是实现定义，但必须满足迭代器类别和容器自身的复杂度要求。

以std::map为例：

• 标准规定std::map的迭代器属于双向迭代器类别（[map.overview] p1），双向迭代器要求递增、递减、解引用等操作满足摊还常数时间。
• std::map底层通常实现为红黑树，其迭代器的移动操作本质是遍历树节点，但这是实现细节——标准并未强制要求底层实现，只要求迭代器操作符合双向迭代器的复杂度要求。

相关标准参考：

• [iterator.concepts]章节定义了各个迭代器概念（对应原有的迭代器类别）的操作要求；
• [associative.reqmts]章节规定了关联容器（如std::map）的迭代器必须满足双向迭代器的要求，且其迭代器的递增、递减操作具有摊还常数时间复杂度。

内容的提问来源于stack exchange，提问作者Jan Schultke