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?

Solution 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;

Solution 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.

Solution 3

I think I found the answer in another SO post Extending std::list

"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.

Comments

[dmckee --- ex-moderator kitten]

To elaborate a bit operator[] is a constant time operation in all the other places it is used. Giving the same name to a O(n) operation would be inconsistent and confusing.

[Gab Royer]

So basically, it's just a matter of preventing people of making mistakes?

[C. K. Young]

You mean that isn't reason enough? :-)

[Pavel Minaev]

It is. Looking elsewhere, .NET LinkedList doesn't provide an indexer for largely the same reasons - it's just too deceptive. Traditionally, when something has a positional indexer, it is assumed that the operation is O(1).

[josesuero]

yep. Or of not making promises you can't keep. In the STL, the operator[] promises efficient access to arbitrary elements.

[Pavel Minaev]

In a map it's decidedly not a positional index, which is quite obvious - except perhaps when map key is an integer, but if you're confusing positional access with key lookup, you have much bigger problems already ;)

[Gab Royer]

I know the difference, rest assured! But it remains operator[] ;).

[bk1e]

Note that std::list::size() may also be O(n) (see stackoverflow.com/questions/228908/is-listsize-really-on/228‌​914), so that first loop could be O(n^2) even without the call to operator[].

[Zeta]

Is this purely base on your opinion or have you created a nice test scenario, where you show that your custom implementation of std::list<T>::operator[] is efficient? (BTW, according to Stroustrup the standard container you should use is std::vector).

[Tomilov Anatoliy]

std::next is more appropriate function (std::list< int > list; ...; *std::next(std::begin(list), index) = 1;), due to it leaves its argument unmodified.