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: Paolo Carlini <pcarlini at suse dot de>
- To: chris jefferson <caj at cs dot york dot ac dot uk>
- Cc: 聂久焘 <njt at mprc dot pku dot edu dot cn>, libstdc++ at gcc dot gnu dot org
- Date: Wed, 23 Nov 2005 13:11:20 +0100
- Subject: Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
- References: <200511231141.jANBfaLn020308@mprc.mprc.pku.edu.cn> <4384583F.9020005@cs.york.ac.uk>
chris jefferson wrote:
>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.
>
>
100% agreed. I want to add that this issue was recently debated again in
the LWG reflector: thread starting from c++std-lib-15781 (*).
Paolo.
(*) Everyone can fetch archived messaged sending queries to
c++std-ping@accu.org (an empty one to learn about the whole thing).