#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <vector>
#include <ctime>
static const unsigned seek_count = 1000000;
volatile int nocheat;
#ifndef _MSC_VER
template<typename C>
auto begin(C &&c) -> decltype(std::forward<C>(c).begin()) { return std::forward<C>(c).begin(); }
template<typename C>
auto end(C &&c) -> decltype(std::forward<C>(c).end()) { return std::forward<C>(c).end(); }
#endif
clock_t search_set(int N) {
nocheat = 0;
auto r = std::bind(std::uniform_int_distribution<int>(0,N-1),std::default_random_engine());
std::set<int> s;
for(int i=0;i<N;++i) {
s.insert(i);
}
clock_t start = clock();
for(int i=0;i<seek_count;++i) {
int findme = r();
auto iter = s.find(findme);
nocheat += *iter;
}
clock_t end = clock();
return end-start;
}
clock_t search_vector(int N) {
nocheat = 0;
auto r = std::bind(std::uniform_int_distribution<int>(0,N-1),std::default_random_engine());
std::vector<int> s;
for(int i=0;i<N;++i) {
s.push_back(i);
}
clock_t start = clock();
for(int i=0;i<seek_count;++i) {
int findme = r();
auto iter = std::lower_bound(begin(s),end(s),findme);
if (iter == s.end() || *iter<findme)
iter = s.end();
nocheat += *iter;
}
clock_t end = clock();
return end-start;
}
int main()
{
const int N = 100000;
int time;
#if defined(WIN32)
std::cout.imbue(std::locale("English_United States.1251"));
#endif
std::cout << "Time for N searches where N = " << N << "\n";
time = search_set(N);
std::cout << "set returned " << nocheat<< " in " << time << " ticks\n";
time = search_vector(N);
std::cout << "vector returned " << nocheat<< " in " << time << " ticks\n";
return 0;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y3RpbWU+CiAKc3RhdGljIGNvbnN0IHVuc2lnbmVkIHNlZWtfY291bnQgPSAxMDAwMDAwOwp2b2xhdGlsZSBpbnQgbm9jaGVhdDsKIAojaWZuZGVmIF9NU0NfVkVSCiAgICAgICAgdGVtcGxhdGU8dHlwZW5hbWUgQz4KICAgICAgICBhdXRvIGJlZ2luKEMgJiZjKSAtPiBkZWNsdHlwZShzdGQ6OmZvcndhcmQ8Qz4oYykuYmVnaW4oKSkgeyByZXR1cm4gc3RkOjpmb3J3YXJkPEM+KGMpLmJlZ2luKCk7IH0KICAgICAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBDPgogICAgICAgIGF1dG8gZW5kKEMgJiZjKSAtPiBkZWNsdHlwZShzdGQ6OmZvcndhcmQ8Qz4oYykuZW5kKCkpIHsgcmV0dXJuIHN0ZDo6Zm9yd2FyZDxDPihjKS5lbmQoKTsgfQojZW5kaWYKIApjbG9ja190IHNlYXJjaF9zZXQoaW50IE4pIHsKICAgICAgICBub2NoZWF0ID0gMDsKICAgICAgICBhdXRvIHIgPSBzdGQ6OmJpbmQoc3RkOjp1bmlmb3JtX2ludF9kaXN0cmlidXRpb248aW50PigwLE4tMSksc3RkOjpkZWZhdWx0X3JhbmRvbV9lbmdpbmUoKSk7CiAgICAgICAgc3RkOjpzZXQ8aW50PiBzOwogICAgICAgIGZvcihpbnQgaT0wO2k8TjsrK2kpIHsKICAgICAgICAgICAgICAgIHMuaW5zZXJ0KGkpOwogICAgICAgIH0KICAgICAgICBjbG9ja190IHN0YXJ0ID0gY2xvY2soKTsKICAgICAgICBmb3IoaW50IGk9MDtpPHNlZWtfY291bnQ7KytpKSB7CiAgICAgICAgICAgIGludCBmaW5kbWUgPSByKCk7CiAgICAgICAgICAgIGF1dG8gaXRlciA9IHMuZmluZChmaW5kbWUpOwogICAgICAgICAgICBub2NoZWF0ICs9ICppdGVyOwogICAgICAgIH0KICAgICAgICBjbG9ja190IGVuZCA9IGNsb2NrKCk7CiAgICAgICAgcmV0dXJuIGVuZC1zdGFydDsKfQogCmNsb2NrX3Qgc2VhcmNoX3ZlY3RvcihpbnQgTikgewoJICAgIG5vY2hlYXQgPSAwOwogICAgICAgIGF1dG8gciA9IHN0ZDo6YmluZChzdGQ6OnVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxpbnQ+KDAsTi0xKSxzdGQ6OmRlZmF1bHRfcmFuZG9tX2VuZ2luZSgpKTsKICAgICAgICBzdGQ6OnZlY3RvcjxpbnQ+IHM7CiAgICAgICAgZm9yKGludCBpPTA7aTxOOysraSkgewogICAgICAgICAgICAgICAgcy5wdXNoX2JhY2soaSk7CiAgICAgICAgfQogICAgICAgIGNsb2NrX3Qgc3RhcnQgPSBjbG9jaygpOwoJCWZvcihpbnQgaT0wO2k8c2Vla19jb3VudDsrK2kpIHsKCQkJaW50IGZpbmRtZSA9IHIoKTsKCQkJYXV0byBpdGVyID0gc3RkOjpsb3dlcl9ib3VuZChiZWdpbihzKSxlbmQocyksZmluZG1lKTsKCQkJaWYgKGl0ZXIgPT0gcy5lbmQoKSB8fCAqaXRlcjxmaW5kbWUpCgkJCQlpdGVyID0gcy5lbmQoKTsKCQkJbm9jaGVhdCArPSAqaXRlcjsKCQl9CiAgICAgICAgY2xvY2tfdCBlbmQgPSBjbG9jaygpOwogICAgICAgIHJldHVybiBlbmQtc3RhcnQ7Cn0KIAppbnQgbWFpbigpCnsKICAgIGNvbnN0IGludCBOID0gMTAwMDAwOwogICAgICAgIGludCB0aW1lOwogCiNpZiBkZWZpbmVkKFdJTjMyKQogICAgICAgIHN0ZDo6Y291dC5pbWJ1ZShzdGQ6OmxvY2FsZSgiRW5nbGlzaF9Vbml0ZWQgU3RhdGVzLjEyNTEiKSk7CiNlbmRpZgogCiAgICBzdGQ6OmNvdXQgPDwgIlRpbWUgZm9yIE4gc2VhcmNoZXMgd2hlcmUgTiA9ICIgPDwgTiA8PCAiXG4iOwogICAgICAgIHRpbWUgPSBzZWFyY2hfc2V0KE4pOwogICAgc3RkOjpjb3V0IDw8ICJzZXQgcmV0dXJuZWQgIiA8PCBub2NoZWF0PDwgIiBpbiAiIDw8IHRpbWUgPDwgIiB0aWNrc1xuIjsKICAgICAgICB0aW1lID0gc2VhcmNoX3ZlY3RvcihOKTsKICAgIHN0ZDo6Y291dCA8PCAidmVjdG9yIHJldHVybmVkICIgPDwgbm9jaGVhdDw8ICIgaW4gIiA8PCB0aW1lIDw8ICIgdGlja3NcbiI7CiAKICAgIHJldHVybiAwOwp9CiA=