Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?

[chris jefferson]

聂久焘 wrote:
> The C++ standard said Container::size() should have constant complexity
> (ISO/IEC 14882:1998, pp. 461, Table 65), while the std::list::size() in
> current STL of GCC is defined as { std::distance(begin(), end()); }, whose
> complexiy is O(n).
>  
> Is it a bug?
>
>   
This question would be better asked on [EMAIL PROTECTED], the
mailing list of gcc's implementation of the C++ standard library.

This question comes up every so often, in "offical standard speak", the
word "should" has a specific meaning, which is that an implementation is
supposed to do something unless there is a good reason not to.

The reason that size() is O(n) is to allow some of the splice functions
to be more efficient. Basically it's a tradeoff between fast splicing or
fast size.

Note that empty() is O(1), as required by the standard, so if thats what
you want, you should use that.