Why isn't there an operator[] for a std::list?
c++, list, stl
Solution
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];
...
}
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`.
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;
Problem
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?