In fact, the question is even two. To some surprise for myself, I learned that the time complexity of getting a list of items from the std::list::size() is linear.

C ++ 98. Complexity: Up to linear. A source

It is not entirely clear what caused this. Why each time to count their items?

And if this was the need for early standards, then at the expense of what compromises was it possible to achieve a guarantee of constancy in the standard of the new?

C ++ 11. Complexity: Constant.

    1 answer 1

    This is a consequence of the age-old "conflict of interest" between the functions std::list::size() and std::list::splice() .

    If a partial splice() made from one std::list to another with the requirement of a constant execution time of such splice() (i.e., just transferring the extreme elements of the range from one list to another), then it will be impossible to immediately know the new dimensions of the container source and destination container, because it is not known how many elements are strung together Therefore, the requirement of a time- constant splice() leads to the requirement of a time- linear size() - elements in both containers will have to be recalculated.

    If, on the contrary, to require time constancy size() (i.e., to actually require a stored size), then you have to agree to a slower splice() , which in the above situation will calculate the new sizes of containers for the linear time.

    In C ++ 98 this question was left open. Implementations were allowed to choose where, in their opinion, the constant time is more important - in size() or splice() .

    In C ++ 11 they decided to make a volitional decision: we make the stored size, guarantee size() for a constant time and, so be it, agree to linear time in splice() .

    This explains the difference between C ++ 98 and C ++ 11.

    PS The implementation of the standard C ++ library in GCC initially followed the fast splice() and slow size() paths. After C ++ 11 insisted on another version, GCC corrected the implementation of its std::list , but immediately stumbled upon the binary incompatibility of library versions due to the addition of a new field to std::list . The change was immediately rolled back, and to this day the std::list in the GCC does not meet the requirements of C ++ 11. std::list::size() is linear there.

    • Thank you for your reply! - Malov Vladimir