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.
Post a Comment