Benchmarks
While I tried different vector and map-implementations for c++ I've written some benchmarking modules and found that most of the time I was NOT benchmarking the class itself but mostly the allocator. Most benchmarks I've found made this mistake! Btw, for the vector the most important factor was the growth factor of the vector (for example twice as big as the old size, or 1.5 times etc).
startTime();
std::vector test;
for(int i=0; i<100000; ++i)
test.push_back(i);
measureTime();
A better way is to preallocate the memory and measure only the insertion of the element:
std::vector test;
test.resize(100000);
startTime();
for(int i=0; i<100000; ++i)
test.push_back(i);
measureTime();
Ofcourse it's a big win if you can specify how the vector should grow, because (like most of the time)
you can trade memory for speed...
And ofcourse prewarm your cache (or trash it) to create the same start conditions for every routine you
want to test!