c++ - 为什么没有更多的迭代器随机访问？

Question

我正在努力了解更多有关 C++ 中的 STL 迭代器的信息。我了解不同的数据结构如何具有不同的迭代器，但我不明白为什么有些迭代器不是 RandomAccess。例如，为什么 LinkedList 迭代器不是随机访问迭代器？我知道 LinkedList 本身不是“随机访问结构”，但我们不能实现迭代器来产生随机访问结构的错觉吗？例如，LinkedList 有一个双向迭代器，它没有定义 + 或 += 运算符，但定义了++ 运算符。难道我们不能只定义 + 和 += 运算符，使用类似的东西:

iterator operator+= (int steps) {
     for (int i = 0; i < steps; ++i) {
          this->operator++();
     }
}

在查看了 RandomAccessIterator 要求之后，我认为我们可能可以为 LinkedList 实现大部分(如果不是全部)这些功能，那么我们为什么不呢？我猜是因为某些操作本质上具有 O(N) 时间复杂度，但我不确定这是否是关键问题。如果我们要使用这种方法实现 RandomAccessIterators，这对将 LinkedList 与 STL 算法一起使用会有什么影响？我们会突然能够使用 std::sort 函数对 LinkedList 进行排序吗？

Answer 1

I'm guessing its because some operations would have essentially O(N) time complexity, but I'm not sure if that is the key concern.

是的，这正是关键问题。迭代器是在指针之后建模的。而有了指针，人们就有了一定的期待。这些期望之一是指针加法和减法是非常快的操作(具体来说，O(1))。标准库的设计者决定兑现这些期望。因此，如果标准库迭代器不能在 O(1) 中执行加法和减法，那么它就不会实现这些操作，并且不属于随机访问迭代器。

请注意，使用递增和递减运算符(++ 和 --)，性能要求稍微宽松一些，并且有一些迭代器实现了 O (log n) 而不是 O(1)。这种妥协是必要的，因为如果您不能递增或递减迭代器，它就没有多大用处。

If we were to implement RandomAccessIterators using this approach, what consequences would this have on using the LinkedList with STL algorithms? Would we suddenly be able to sort a LinkedList using the std::sort function?

是的。但它会(至少)变成一个 O(n^2) 算法，而不是标准所 promise 的 O(n log n)。