0

I just wonder how expensive is it to call a std::list size(). Some people say it's an O(1) call because the size is updated upon insert() or remove()/erase(). Some people say it will iterate from begin to end and count how many elements are there.

Does c++ standard say anything about how the complexity of this function call should be? Thanks!

Immanuel Kant
  • 517
  • 3
  • 8
  • 10
    [`std::list::size`](https://en.cppreference.com/w/cpp/container/list/size) – Quimby Jan 12 '23 at 13:57
  • Glad to see this got updated in C++11. Allowing `size()` to be linear was just to accommodate one particular implementation. Somewhere on the internet is a piece by the author of that implementation where he gives five spurious reasons why he's right and all the other implementations are wrong. – john Jan 12 '23 at 14:01
  • some people are right and some people have been right until c++11. Btw the draft versions of the standard are available online. You can read it. – 463035818_is_not_an_ai Jan 12 '23 at 14:01
  • For context, the only advantage to having linear `size` is that not storing the length makes splicing faster – Jeffrey Jan 12 '23 at 14:10
  • @Jeffrey -- not storing the size makes the `list` object smaller, and in some realms that's important. – Pete Becker Jan 12 '23 at 14:43

1 Answers1

1

According to cppreference, a requirement for a class to be considered a Container is that the size() member function has constant complexity, i.e. O(1), from c++11 and onward.

One can also see that fact specifically for std::list as @Quimby pointed out.

Mestkon
  • 3,532
  • 7
  • 18