This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
- From: chris jefferson <caj at cs dot york dot ac dot uk>
- To: 聂久焘 <njt at mprc dot pku dot edu dot cn>
- Cc: gcc at gcc dot gnu dot org, libstdc++ at gcc dot gnu dot org
- Date: Wed, 23 Nov 2005 11:53:35 +0000
- Subject: Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
- References: <200511231141.jANBfaLn020308@mprc.mprc.pku.edu.cn>
聂久焘 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 libstdc++@gcc.gnu.org, 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.