c++ - std::next 是 vector O(n) 还是 O(1)？

Question

在 C++11 中我使用 std::next 因为如果我想将 vector 更改为 list，我不必更改其余代码。

对于 list，std::next 是 O(n)，因为我需要迭代所有元素。但是对于 vector 来说是怎样的呢？我找到了this note on cppreference :

However, if InputIt or ForwardIt additionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.

vector 是否满足这些要求？为什么是“遗产”？

Answer 1

有在 C++20 中添加概念(编译时类型约束)的计划。新标准应该包含 InputIterator 或 RandomAccessIterator 等概念。为了区分概念和旧的 trait-like 需求，cppreference 使用 LegacyRandomAccessIterator 等表示概念前需求，使用 RandomAccessIterator 等表示概念需求。

所以是的，std::vector::iterator 符合 LegacyRandomAccessIterator 的要求，实际上也将实现 RandomAccessIterator 的概念。这直接得出结论，在 vector::iterator 上调用的 std::next 复杂度为 O(1)。