为什么 std::list 没有运算符 []?

2022-01-07 00:00:00 list c++ stl

谁能解释为什么没有为 std::list 实现 operator[] ?我已经搜索了一点，但没有找到答案.实施起来不会太难，还是我遗漏了什么?

Can anyone explain why isn't the operator[] implemented for a std::list? I've searched around a bit but haven't found an answer. It wouldn't be too hard to implement or am I missing something?

推荐答案

通过索引检索元素是链表的 O(n) 操作，这就是 std::list 的含义.因此决定提供 operator[] 将具有欺骗性，因为人们会很想积极地使用它，然后你会看到如下代码:

Retrieving an element by index is an O(n) operation for linked list, which is what std::list is. So it was decided that providing operator[] would be deceptive, since people would be tempted to actively use it, and then you'd see code like:

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

这是 O(n^2) - 非常讨厌.所以ISO C++标准特别提到所有支持operator[]的STL序列都应该在分摊常数时间(23.1.1[lib.sequence.reqmts]/12)内完成，这对于vector 和 deque，但不是 list.

which is O(n^2) - very nasty. So ISO C++ standard specifically mentions that all STL sequences that support operator[] should do it in amortized constant time (23.1.1[lib.sequence.reqmts]/12), which is achievable for vector and deque, but not list.

如果你真的需要那种东西，你可以使用 std::advance 算法:

For cases where you actually need that sort of thing, you can use std::advance algorithm:

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

相关文章