Friday, November 24, 2006

STL list size() method is slow

In STL list, the size() method is o(n), where n is number of elements in the list. The implementation of size() is by traversing the linked list and counting the nodes one by one. So, it sounds stupid.
I have written a simple program to test the performance of size() method in STL list and STL vector. For a STL list with 10M integers, it takes 0.17 sec. to get the size. However, for a STL vector with 10M integers, it takes 0.4 micro sec to get the size() in same machine.
There are some suggestions:
  1. Use vector instead of list.
  2. If the application need to check whether the list is empty or not, uses "list.emtpy()" instead of "list.size() != 0".
  3. use an extra counter variable to counting the size of a list.
Posted by at
Labels:

1 comment:

Unknown said...

Actually, it depends on which STL you are using. Microsoft Visual Studio V6 implements size() as {return (_Size); } whereas gcc (at least in versions 3.3.2 and 4.1.0) do it as
{ return std::distance(begin(), end()); }
The first has constant speed, the second has o(N) speed

9:52 AM

Post a Comment