Talk:cpp/named req/Container

I thought the complexity of 'Container::size_type Container::size() const' is only required to be linear, not constant.

std::list is the canonical example of this, where some implementations have a Linear complexity.

"Effective STL" by Scott Meyers - Item 4. Call empty instead of checking size() against zero.

http://www.sgi.com/tech/stl/Container.html#10. I know, this isn't the Standard.

Referring to ISO/IEC 14882:2003, Section 23.1, I see that its complexity for ::size, as well as ::max_size is "should be constant", implying that it won't always be.

I just added a note saying that std::list is an exception to the constant complexity.

Should the table for ::size and ::max_size be more explicit about this?

69.84.133.248 13:39, 20 June 2012 (PDT) Charles Wilcox

The C++03 standard says "should be constant", I've used n3290 (C++11) to compile this table which only says "constant".

This should be highlighted in the footnote

--Bazzy 13:49, 20 June 2012 (PDT)

It seems that the standard committee decided that std::list should have a separate data member storing the number of elements. C++11 says that size() is constant without any ambiguity. splice() from another list is linear, not constant. This limitation can only be if there's need to count the number of inserted elements in order to update the size data member. -- P12 13:58, 20 June 2012 (PDT)