向量O（n）或O（1）是std :: next吗？

Question

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

对于list，std::next为O（n），因为我需要遍历所有元素。但是，这如何vector呢？我在cppreference上发现了这个注释：

但是，如果满足InputIt或ForwardIt额外满足LegacyRandomAccessIterator的要求，则复杂度是恒定的。

是否vector符合这些要求？以及为什么“传统”？

Answer 1

有计划在C ++ 20中添加概念（编译时间类型约束）。新标准应该包含类似InputIterator或的概念RandomAccessIterator。为了区分概念和旧特征样需求，cppreference使用了诸如LegacyRandomAccessIterator概念前需求和RandomAccessIterator概念需求之类的东西。

因此，是的，std::vector::iterator满足的要求，LegacyRandomAccessIterator实际上也将实现RandomAccessIterator概念。这直接得出结论，std::next调用vector::iterator具有复杂度O（1）。

Answer 2

vector是否满足这些要求？

是的，它确实：

https://en.cppreference.com/w/cpp/container/vector

Quote：“迭代器LegacyRandomAccessIterator”

以及为什么“传统”？

由于即将到来的C ++库功能称为range，因此将现有的迭代器重命名为“ legacy” ，它可以替代当前方法。范围将具有新的迭代器。现有的将仍然存在，因此被称为“旧版”。