Why isn't std::list.size() constant-time?
c++, list, performance, size
Solution
There is a conflict between constant time `size()` and constant time `list.splice`. The committee chose to favour `splice`.
When you splice nodes between two lists, you would have to count the nodes moved to update the sizes of the two lists. That takes away a lot of the advantage of splicing nodes by just changing a few internal pointers.
As noted in the comments, C++11 has changed this by giving up O(1) for some rare(?) uses of `splice`:
void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);
Complexity: Constant time if `&x == this`; otherwise, linear time.
Problem
This code ran for 0.012 seconds: ``` std::list<int> list; list.resize(100); int size; for(int i = 0 ; i < 10000; i++) size = list.size(); ``` This one for 9.378 seconds: ``` std::list<int> list; list.resize(100000); int size; for(int i = 0 ; i < 10000; i++) size = list.size(); ``` In my opinion it would be possible to implement std::list in such way, that size would be stored in a private variable but according to this it is computed again each time I call size. Can anyone explain why?