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

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;

Leave a Comment