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

by

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;

More Related Contents:

  1. c++ push reference node to stl list
  2. vector vs. list in STL
  3. Is list::size() really O(n)?
  4. Sort list using STL sort function
  5. Does std::list::remove method call destructor of each removed element?
  6. array vs vector vs list
  7. Cleaning up an STL list/vector of pointers
  8. list of polymorphic objects
  9. stl::map assert [closed]
  10. How can I use std::maps with user-defined types as key?
  11. Can you remove elements from a std::list while iterating through it?
  12. std::vector::resize() vs. std::vector::reserve()
  13. Is std::vector so much slower than plain arrays?
  14. How do I erase an element from std::vector by index?
  15. How to find if a given key exists in a C++ std::map
  16. How to get std::vector pointer to the raw data?
  17. Can standard container templates be instantiated with incomplete types?
  18. What does the standard library guarantee about self move assignment?
  19. Why use functors over functions?
  20. How to declare a vector of atomic in C++
  21. std::optional specialization for reference types
  22. How to iterate over a priority_queue?
  23. How does std::copy work with stream iterators
  24. STL containers element destruction order
  25. Advice on a better way to extend C++ STL container with user-defined methods
  26. STL vectors with uninitialized storage?
  27. “Right” way to deallocate an std::vector object
  28. Order Statistic Tree in C++
  29. C++11 std::to_string(double) – No trailing zeros
  30. C++ inserting unique_ptr in map

Leave a Comment