为什么std :: list没有operator []？

Question

谁能解释为什么不为std :: list实现operator []？我搜索了一下但没有找到答案.实施起来不是太难,或者我错过了什么？

Answer 1

通过索引检索元素是链表的O(n)操作,这是什么std::list.所以决定提供operator[]会有欺骗性,因为人们会想要积极地使用它,然后你会看到如下代码:

 std::list<int> xs;
 for (int i = 0; i < xs.size(); ++i) {
     int x = xs[i];
     ...
 }

这是O(n ^ 2) - 非常讨厌.所以ISO C++标准特别提到,支持所有STL序列operator[]应该这样做在分期常量时间(23.1.1 [lib.sequence.reqmts]/12),这是可以实现的用于vector和deque,但不是list.

对于您实际需要此类事物的情况,您可以使用std::advance算法:

int iter = xs.begin();
std::advance(iter, i);
int x = *iter;