40

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?

Gab Royer
  • 9,587
  • 8
  • 40
  • 58

4 Answers4

81

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;
Pavel Minaev
  • 99,783
  • 25
  • 219
  • 289
  • So basically, it's just a matter of preventing people of making mistakes? – Gab Royer Jul 11 '09 at 02:03
  • 21
    yep. Or of not making promises you can't keep. In the STL, the operator[] promises *efficient* access to arbitrary elements. – jalf Jul 11 '09 at 02:06
  • 11
    Note that std::list::size() may also be O(n) (see http://stackoverflow.com/questions/228908/is-listsize-really-on/228914), so that first loop could be O(n^2) even without the call to operator[]. – bk1e Jul 11 '09 at 17:45
  • `std::next` is more appropriate function (`std::list< int > list; ...; *std::next(std::begin(list), index) = 1;`), due to [it leaves its argument unmodified](http://stackoverflow.com/questions/15017065/whats-the-difference-between-stdadvance-and-stdnext). – Tomilov Anatoliy Jul 10 '15 at 09:11
3

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.

florin
  • 13,986
  • 6
  • 46
  • 47
  • 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. – dmckee --- ex-moderator kitten Jul 11 '09 at 02:03
  • 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 ;) – Pavel Minaev Jul 11 '09 at 02:08
  • I know the difference, rest assured! But it remains operator[] ;). – Gab Royer Jul 11 '09 at 02:11
1

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.

Community
  • 1
  • 1
Gab Royer
  • 9,587
  • 8
  • 40
  • 58
  • You mean that isn't reason enough? :-) – C. K. Young Jul 11 '09 at 02:04
  • 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). – Pavel Minaev Jul 11 '09 at 02:05
0

Actually, there is absolutely no reason to not provide operator[] or at least method at(int), because of the two reasons:

  • It is double linked list, so you need to move at most size()/2 places your iterator to get your index, and costs to internally keep few more fixed iterators are very low. And at the end, the Qt library provides the operator[] and the at, and I do not see performance cost using it.
  • forcing people something not to use is a very bad programming habit, because a list will much usable container, if you have a "random access" near the linked access, there is a variety examples when you need both access, depending at which runtime point.
Mikhail Kalashnikov
  • 1,146
  • 1
  • 11
  • 31
Dusan
  • 1
  • 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::operator[]` is efficient? (BTW, according to Stroustrup the standard container you should use is `std::vector`). – Zeta Feb 25 '13 at 17:24