On 7/12/06, bringiton bringiton
I'm just wondering what your thoughts are on my findings.
I need a container that meets the following: - forward iteration only - insert to end only - no random access - delete from any position - average size of list will be 64 items
I would first say use list over vector. because no random access and delete from any position. I ran some performance tests, which proved otherwise.
The test builds a list by inserting to end. And then removes all items from the front until size == 0. (note: removing from index [0] should provide worst case linear complexity for vector)
Here are my finding for containers of size 64, 256 and 1024. first result uses vector, 2nd uses list. i ran the test in release mode in ms vc++ 6.
Test build/remove 64 0.062 0.234 Test build/remove 256 0.422 0.938 Test build/remove 1024 5.844 3.75
- it seems vector is best for smaller lists. even at 256 items, the vector is twice as fast at building at contant time and deleting and worst case linear time. - is this strange behaviour? is my test correct or do i have a bug? - i am also curious to how this runs on other compilers (esp later version of ms vc++)
For those curious, here is my code. feel free to pick at it ;)
void TestVectBuildDelete(int redoCount, int listSize) { boost::timer t; for (int i = 0; i < redoCount; i++) { // build the list std::vector<int> vect; for (int j = 0; j < listSize; j++) { vect.push_back(j); //vect.insert(vect.begin(), j); //.push_front(j); } // remove all elements in list while (!vect.empty()) { vect.erase(vect.begin()); } } std::cout << t.elapsed() << std::endl; }
void TestListBuildDelete(int redoCount, int listSize) { boost::timer t; for (int i = 0; i < redoCount; i++) { // build the list std::list<int> vect; for (int j = 0; j < listSize; j++) { vect.push_back(j); } // remove all elements in list while (!vect.empty()) { vect.pop_front(); } } std::cout << t.elapsed() << std::endl; }
void Test() { std::cout << "Test build/remove 64" << std::endl; TestVectBuildDelete(10000, 64); TestListBuildDelete(10000, 64);
std::cout << "Test build/remove 256" << std::endl; TestVectBuildDelete(10000, 256); TestListBuildDelete(10000, 256);
std::cout << "Test build/remove 1024" << std::endl; TestVectBuildDelete(10000, 1024); TestListBuildDelete(10000, 1024); }
I've done some more tests. It seems building a list is significantly slower that building a vector. (This is were the discrepancy is coming from). can anyone suggest why this is so? is the list<T>::push_back bottleneck due to memory allocation for each node? *NB sorry this is boost related. but i found it interesting ;)