#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;
}