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

This is the mail archive of the gcc@gcc.gnu.orgmailing list for the GCC project.

• From: Phil Edwards
• To: ??????
• 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

• Follow-Ups:
  • Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
    * From: Howard Hinnant
• References:
  • [C++] Should the complexity of std::list::size() be O(n) or O(1)?
    * From: 聂久焘