对于向量O（n）或O（1），std :: next是？

Question

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

对于list，std::next是O（n），因为我需要迭代所有元素。但是如何为vector？我找到了this note on 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

矢量符合这些要求吗？

是的，它确实：

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

引用：“iterator Legacy RandomAccessIterator”

为什么“遗产”？

由于即将推出的名为ranges的C ++库特性，现有的迭代器已被重命名为“遗留”，这是当前方法的替代品。范围将有新的迭代器。现有的仍将存在，因此它们被称为“遗产”。