Why isn't there an operator[] for a std::list?

Question

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?

Answer 1

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;

Answer 2

It would not be too hard (for the implementer) but it would be too hard at runtime, since the performance will be terrible in most cases. Forcing the user to go through each link will make it more obvious what is going on in there than 'myList[102452]' would.