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

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.

Answer 2

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 3

I think I found the answer in another SO post http://stackoverflow.com/questions/366432/extending-stdlist

"your operator[] is O(N) time" - this is exactly why it is not included in the standard's std::list<>. – Michael Burr Dec 14 at 17:29

Still, is that the only reason?

EDIT : It seems though as people mentioned it is more a matter of consistency regarding performance then strictly performance.