Originally Posted by
anon
This test with an enormous amount of integers probably doesn't represent a common use case and is rather unfavorable for vector
Well of course it is. That was just a quick test I wrote to give a demo of what sorts of things we can do. Here's something much better:
http://i169.photobucket.com/albums/u...rDequeSort.png
Code:
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <vector>
#include "stopwatch.hpp"
template <typename Container>
double TimeToSort(int elements, int repetitions, Stopwatch& sw);
int optimisationStopper = 0;
int main(int argc, char** argv)
{
if (argc != 4)
{
std::cerr << "Usage: " << argv[0] << " maxElements increment repetitions" << std::endl;
return 1;
}
int seedOffset = time(NULL);
Stopwatch sw;
int maxElements = atoi(argv[1]);
int increment = atoi(argv[2]);
int repetitions = atoi(argv[3]);
std::cout << "size, vector, deque" << std::endl;
for (int i = increment; i <= maxElements; i += increment)
{
std::cout << i << ", ";
// Give the same numbers to vector and deque by seeding before the tests
srand(i + seedOffset);
std::cout << TimeToSort<std::vector<int> >(i, repetitions, sw) << ", ";
srand(i + seedOffset);
std::cout << TimeToSort<std::deque<int> >(i, repetitions, sw) << std::endl;
}
std::cout << ",,," << optimisationStopper << std::endl;
return 0;
}
void ReserveIfVector(std::vector<int>& v, int n) { v.reserve(n); }
void ReserveIfVector(std::deque<int>& d, int n) { }
template <typename Container>
double TimeToSort(int elements, int repetitions, Stopwatch& sw)
{
typename std::list<Container> cList(repetitions);
for (typename std::list<Container>::iterator i = cList.begin(); i != cList.end(); ++i)
{
ReserveIfVector(*i, elements);
for (int j = 0; j != elements; ++j)
i->push_back(rand());
}
sw.Start();
for (typename std::list<Container>::iterator i = cList.begin(); i != cList.end(); ++i)
{
sort(i->begin(), i->end());
optimisationStopper += i->at(rand() % i->size());
}
sw.Stop();
return sw.GetSeconds() / repetitions;
}
Output:
Code:
vectorVsDeque$ g++ sort.cpp stopwatch.cpp -O3 -march=pentium3 \
> -fomit-frame-pointer -fexpensive-optimizations
vectorVsDeque$ a.out 10000 500 10000
size, vector, deque
500, 2.5e-05, 3.1e-05
1000, 5.5e-05, 6.9e-05
1500, 8.5e-05, 0.000108
2000, 0.000119, 0.00015
2500, 0.000152, 0.000193
3000, 0.000185, 0.000236
3500, 0.000221, 0.000278
4000, 0.000256, 0.000323
4500, 0.00029, 0.000368
5000, 0.000325, 0.000415
5500, 0.000362, 0.00046
6000, 0.000398, 0.000506
6500, 0.000434, 0.000554
7000, 0.000473, 0.000599
7500, 0.000509, 0.000645
8000, 0.000547, 0.000695
8500, 0.000587, 0.000741
9000, 0.000623, 0.000791
9500, 0.000661, 0.000838
10000, 0.000699, 0.000887
,,,-588600934
Looks like this takes 25% longer with deque. That's with my machine and g++ 4.4.5 and -O3. I'd like to see someone else's output.