I have a sequence of double (with no duplicates) and I need to sort them. Is filling a vector
and then sort
ing it faster than insert
ing the values in a set
?
Is this question answerable without a knowledge of the implementation of the standard library (and without a knowledge of the hardware on which the program will run) but just with the information provided by the C++ standard?
#include <vector>
#include <set>
#include <algorithm>
#include <random>
#include <iostream>
std::uniform_real_distribution<double> unif(0,10000);
std::default_random_engine re;
int main()
{
std::vector< double > v;
std::set< double > s;
std::vector< double > r;
size_t sz = 10;
for(size_t i = 0; i < sz; i++) {
r.push_back( unif(re) );
}
for(size_t i = 0; i < sz; i++) {
v.push_back(r[i]);
}
std::sort(v.begin(),v.end());
for(size_t i = 0; i < sz; i++) {
s.insert(r[i]);
}
return 0;
}
set
(and co) is the stability of their elements' addresses during insertion/removal. If not for that, we would use B+ Trees. – Matthieu M. Feb 22 '12 at 20:00