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

[Phil Edwards <phil at codesourcery dot com>]

On Fri, Nov 25, 2005 at 01:17:42PM -0500, Howard Hinnant wrote:
> On Nov 25, 2005, at 9:28 AM, Phil Edwards wrote:
> 
> >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.
> 
> I could not find it here:
> 
> http://gcc.gnu.org/onlinedocs/libstdc++/faq/index.html


http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#6

-- 
You're proposing to build a box with a light on top of it.  The light is
supposed to go off when you carry the box into a room that has a Unicorn
in it.  How do you show that it works?
         - Dr. Gene "spaf" Spafford, at Dr. Wenliang Du's qualifing exam