0

I was going through a tutorial on Containers from the C++ standard library and was taken aback when the instructor told that the size of the std::list isn't stored as part of the list, instead it is found by traversing through the list end to end and returning the count unlike with std::vector.

Is this true?! If yes, why don't they just store the size as part of the class and update the size every time a node is added or removed from the list? What am I missing here?

ZoomIn
  • 1,237
  • 1
  • 17
  • 35
  • 2
    TL;DR of the dupe: From C++11 onward `size()` is required to be an `O(1)` operation, so it must be a cached value. – NathanOliver Aug 09 '22 at 15:35
  • 5
    *the instructor told that the size of the std::list isn't stored as part of the list, instead it is found by traversing through the list end to end and returning the count* -- The instructor is wrong. – PaulMcKenzie Aug 09 '22 at 15:37
  • 1
    @PaulMcKenzie Ah dang! I knew something was amiss. – ZoomIn Aug 09 '22 at 15:38
  • @PaulMcKenzie it depends on how old the info of the instructors' is. GCC before version 5 had an `O(N)` `std::list::size()` – NathanOliver Aug 09 '22 at 15:39
  • @NathanOliver By cached value, do you mean it is stored as the data member of the std::list class? – ZoomIn Aug 09 '22 at 15:43
  • @ZoomIn Yes. It is now required to keep a size variable in the class with the current size. – NathanOliver Aug 09 '22 at 15:45
  • That's why a C++11 `std::list` is bigger than a C++98 `std::list`. – Eljay Aug 09 '22 at 15:45
  • And it should always have been done that way! (just my $0.02). – Paul Sanders Aug 09 '22 at 15:46
  • @NathanOliver Thank you, is there a standard library implementation I can look at and study from? – ZoomIn Aug 09 '22 at 15:47
  • Technically it's required to determine size() in constant time. How it does that is unspecified. There is however no known way of doing that without storing it! I suggest there has never been a serious implementation that worked like that even before complexity was specified as constant in C++11. It's all well and good to allow for different implementations. But if different platforms have significantly different computational complexity then code is for practical purposes non-portable at scale. – Persixty Aug 09 '22 at 15:50
  • 1
    @Zoomin [here is the implementation of `std::list::size()`](https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_list.h#L479) in libstdc++. It's implemented as the internal function `_M_get_size()`. You can see that it is simply returning a member variable and not performing any logic. – Drew Dormann Aug 09 '22 at 15:51
  • 1
    @ZoomIn Both [libc++](https://github.com/llvm-mirror/libcxx/tree/master/include) and [stdlibc++](https://github.com/gcc-mirror/gcc/tree/master/libstdc%2B%2B-v3) are open source versions of the standard library that you can look at – NathanOliver Aug 09 '22 at 15:57

0 Answers0