This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
- From: Phil Edwards <phil at codesourcery dot com>
- To: ?????? <njt at mprc dot pku dot edu dot cn>
- Cc: gcc at gcc dot gnu dot org
- Date: Fri, 25 Nov 2005 09:28:33 -0500
- Subject: Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
- References: <200511231141.jANBfaLn020308@mprc.mprc.pku.edu.cn>
On Wed, Nov 23, 2005 at 07:42:35PM +0800, ?????? 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 is a FAQ.
--
Behind everything some further thing is found, forever; thus the tree behind
the bird, stone beneath soil, the sun behind Urth. Behind our efforts, let
there be found our efforts.
- Ascian saying, as related by Loyal to the Group of Seventeen