C++标准库中std::set等容器迭代器自增的时间复杂度问询

直接结论 #

C++标准明确要求std::set、std::multiset、std::map、std::multimap的迭代器自增（it++/++it）、自减操作的时间复杂度为O(1)，同时规定这些容器的迭代器属于双向迭代器范畴，但标准没有强制要求底层节点必须是双向链表结构——标准只关心容器对外的接口、行为和复杂度指标，不会限制具体实现细节。

详细解释 #

• 关于复杂度：标准在关联容器的规范章节里（C++11及之后的正式标准）明确标注，这类容器的迭代器自增、自减操作必须是常数时间。这意味着实现不能通过遍历整棵树（比如红黑树）来查找下一个/上一个元素，所以主流实现都会在树节点里额外存储前驱和后继指针——相当于让节点同时具备二叉树节点和双向链表节点的特性，但这只是满足复杂度要求的一种实现方式，不是标准强制的结构。
• 标准的关注点：C++标准只定义容器的"契约"——比如插入、查找、迭代的行为和复杂度，至于底层用红黑树、AVL树还是其他结构，只要符合契约就合法。
• 你参考的n1905是C++0x的早期草案，内容相对陈旧，建议查看更新的正式标准文档，在关联容器的专门章节里能找到明确的复杂度规定。

额外补充 #

虽然标准没硬卡节点结构，但为了达到O(1)的自增/自减效率，目前所有主流STL实现（比如GCC的libstdc++、Clang的libc++、MSVC的STL）都采用了带前驱后继指针的树节点设计，本质上就是把树节点和双向链表节点合并了。

内容的提问来源于stack exchange，提问作者Misha T