Is list::size() really O(n)?

by

In C++11 it is required that for any standard container the .size() operation must be complete in “constant” complexity (O(1)). (Table 96 — Container requirements). Previously in C++03 .size() should have constant complexity, but is not required (see Is std::string size() a O(1) operation?).

The change in standard is introduced by n2923: Specifying the complexity of size() (Revision 1).

However, the implementation of .size() in libstdc++ still uses an O(N) algorithm in gcc up to 4.8:

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

See also Why is std::list bigger on c++11? for detail why it is kept this way.

Update: std::list::size() is properly O(1) when using gcc 5.0 in C++11 mode (or above).

By the way, the .size() in libc++ is correctly O(1):

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

More Related Contents:

  1. c++ push reference node to stl list
  2. What are the complexity guarantees of the standard containers?
  3. vector vs. list in STL
  4. Sort list using STL sort function
  5. Does std::list::remove method call destructor of each removed element?
  6. multiset, map and hash map complexity
  7. array vs vector vs list
  8. Cleaning up an STL list/vector of pointers
  9. How can std::make_heap be implemented while making at most 3N comparisons?
  10. What’s the time complexity of iterating through a std::set/std::map?
  11. list of polymorphic objects
  12. Why isn’t there an operator[] for a std::list?
  13. How to recognize the meaning of a linked list function in c++ [closed]
  14. Thou shalt not inherit from std::vector
  15. What’s the most efficient way to erase duplicates and sort a vector?
  16. UTF8 to/from wide char conversion in STL
  17. What happens if you call erase() on a map element while iterating from begin to end?
  18. Floating point keys in std:map
  19. Difference between erase and remove
  20. Why is the C++ initializer_list behavior for std::vector and std::array different?
  21. Heterogeneous containers in C++
  22. Why use functors over functions?
  23. How to filter items from a std::map? [duplicate]
  24. Is the use of std::vector objects in C++ acceptable, or should I use an alternative?
  25. How do I store arrays in an STL list?
  26. Is there a standard date/time class in C++?
  27. Which type of sorting is used in the std::sort()?
  28. what is the difference between const_iterator and iterator? [duplicate]
  29. Why vector access operators are not specified as noexcept?
  30. Inspecting STL containers in Visual Studio debugging

Leave a Comment