Complexity of std::list::size() is... O(N)

I want to share my recent "discovery" that was very shocking to me. Reading comments to a slashdot story about the C++0x standard I read something very interesting: std::list::size() has O(N) complexity in the gcc compiler.

For many years I thought it's obvious that std::list::size() has constant complexity and I've used it relaying on that "fact". I was more convinced by some nice sites with C++ documentation I use like cppreference.com. I was really surprised by the slashdot comment and posts it refers to, so I've made a simple benchmark:

#include <iostream>
#include <list>
 
using namespace std;
 
int main ()
{
	list< int > l;
 
	for (int i = 0; i < 1000000; i++)
		l.push_back (i);
 
	for (int i = 0; i < 1000000; i++)
		cout << l.size () << endl;
 
	return 0;
}

I've compiled it with gcc 4.4.5 (standard GCC in the current Ubuntu), run this program and waited forever to finish... So it's true! Using gdb or doing a little research one can find that calling std:list::size() actually does this:

typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last)
{
        ++__first;
        ++__n;
}
return __n;