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

Question

我正在尝试更多地了解C++中的STL迭代器.我理解不同的数据结构有不同的迭代器,但我不明白为什么有些迭代器不是RandomAccess.例如,为什么LinkedList迭代器不是随机访问迭代器？我知道LinkedList不是一个"随机访问结构"的perse,但我们不能实现迭代器来给出随机访问结构的错觉吗？例如,LinkedList有一个双向迭代器,它不定义+或+ =运算符,但它定义了++运算符.我们不能只使用以下内容定义+和+ =运算符:

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

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

Answer 1

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

是的,这正是关键问题.迭代器以指针为模型.有了指针,人们就有了一定的期望.其中一个期望是指针加法和减法是非常快的操作(具体地,O(1)).标准库的设计者决定尊重这些期望.因此,如果标准库迭代器无法在O(1)中执行加法和减法,则它不会实现这些操作,也不会被归类为随机访问迭代器.

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

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

是.但它将成为(至少)O(n ^ 2)算法,而不是标准所承诺的O(n log n).