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

我正在尝试了解有关 C++ 中的 STL 迭代器的更多信息。我理解不同的数据结构如何具有不同的迭代器，但我不明白为什么有些迭代器不是随机访问。例如，为什么 LinkedList 迭代器不是随机访问迭代器？我知道 LinkedList 本身并不是“随机访问结构”，但是我们不能实现迭代器来给出随机访问结构的错觉吗？例如，LinkedList 有一个双向迭代器，它没有定义 + 或 += 运算符，但定义了 ++ 运算符。我们不能只使用以下内容来定义 + 和 += 运算符：

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

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

我猜测这是因为某些操作基本上具有 O(N) 时间复杂度，但我不确定这是否是关键问题。

是的，这正是关键问题。迭代器是根据指针建模的。而有了指针，人们就有了一定的期望。这些期望之一是指针加法和减法是非常快的操作（具体来说，O(1)）。标准库的设计者决定满足这些期望。因此，如果标准库迭代器无法在 O(1) 内执行加法和减法，则它不会实现这些操作，并且不被归类为随机访问迭代器。

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

如果我们使用这种方法实现 RandomAccessIterators，这会对使用带有 STL 算法的 LinkedList 产生什么后果？我们会突然能够使用 std::sort 函数对 LinkedList 进行排序吗？

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