I did a test program timing some operations on std::list and std::vector. std::vector is way faster than std::list, not to mention I had to turn off optimization since std::vector got so optimized giving close to 0 ms in each of its tests (I fear the loops got totally optimized away). std::list may sound fast in theory (had me fooled) but std::vector does take home the gold medal.
...unless I made some serious mistake, I posted the source for the interested.
The result (no optimization):
List.push_back(), iterating 100000 times!
Time: 179 ms
List::iterator, iterating 1000 times!
Time: 7669 ms
List.pop_back(), iterating 100000 times!
Time: 1375 ms
Vector.push_back(), iterating 100000 times!
Time: 10 ms
Vector::iterator, iterating 1000 times!
Time: 4886 ms
Vector.pop_back(), iterating 100000 times!
Time: 5 ms
The result (optimization enabled):
List.push_back(), iterating 100000 times!
Time: 169 ms
List::iterator, iterating 1000 times!
Time: 2158 ms
List.pop_back(), iterating 100000 times!
Time: 1373 ms
Vector.push_back(), iterating 100000 times!
Time: 5 ms
Vector::iterator, iterating 1000 times!
Time: 0 ms
Vector.pop_back(), iterating 100000 times!
Time: 0 ms
The source code:
Code:
#include <windows.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
typedef void (*TaskPointer)(int);
std::list<int> List;
std::vector<int> Vector;
std::ofstream File;
void TaskListPushBack(int Times)
{
while(Times > 0)
{
List.push_back(Times);
Times--;
}
}
void TaskListIterate(int Times)
{
int Sum = 0;
std::list<int>::iterator i;
while(Times > 0)
{
i = List.begin();
while(i != List.end())
{
Sum += (*i);
i++;
}
Times--;
}
}
void TaskListPopBack(int Times)
{
while(Times > 0)
{
List.pop_back();
Times--;
}
}
void TaskVectorPushBack(int Times)
{
while(Times > 0)
{
Vector.push_back(Times);
Times--;
}
}
void TaskVectorIterate(int Times)
{
int Sum = 0;
std::vector<int>::iterator i;
while(Times > 0)
{
i = Vector.begin();
while(i != Vector.end())
{
Sum += (*i);
i++;
}
Times--;
}
}
void TaskVectorPopBack(int Times)
{
while(Times > 0)
{
Vector.pop_back();
Times--;
}
}
void TimeTask(const std::string& Title, TaskPointer Task, int Times)
{
DWORD StartTime;
DWORD EndTime;
std::cout << "Attempting " << Title << "..." << std::endl;
File << Title << ", iterating " << Times << " times!" << std::endl;
StartTime = timeGetTime();
Task(Times);
EndTime = timeGetTime();
File << "Time: " << (EndTime - StartTime) << " ms" << std::endl << std::endl;
std::cout << Title << " done!" << std::endl << std::endl;
}
int main()
{
int PushTimes = 100000;
int IterateTimes = 1000;
std::cout << "Warming up..." << std::endl << std::endl;
Sleep(2000);
timeBeginPeriod(1);
File.open("Result.txt");
TimeTask("List.push_back()", TaskListPushBack, PushTimes);
TimeTask("List::iterator", TaskListIterate, IterateTimes);
TimeTask("List.pop_back()", TaskListPopBack, PushTimes);
TimeTask("Vector.push_back()", TaskVectorPushBack, PushTimes);
TimeTask("Vector::iterator", TaskVectorIterate, IterateTimes);
TimeTask("Vector.pop_back()", TaskVectorPopBack, PushTimes);
File.close();
timeEndPeriod(1);
std::cout << "Done!" << std::endl;
return 0;
}