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)?
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
or here:
http://gcc.gnu.org/faq.html
or here:
http://www.jamesd.demon.co.uk/csc/faq.html
-Howard