This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
[C++] Should the complexity of std::list::size() be O(n) or O(1)?
- From: 聂久焘 <njt at mprc dot pku dot edu dot cn>
- To: <gcc at gcc dot gnu dot org>
- Date: Wed, 23 Nov 2005 19:42:35 +0800
- Subject: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
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?