#include <algorithm>
#include <iostream>
#include <map>
#include <cstdlib>
#include <ctime>
#include <vector>
 
static const unsigned seek_count = 10000000;
 
std::map<unsigned, unsigned>::const_iterator mapfind(const std::map<unsigned, unsigned>& a, const std::pair<unsigned, unsigned>& findme) {
    return a.find(findme.first);
        //MSVC9 implimentation, for compaison with vector code
                //const_iterator _Where = lower_bound(_Keyval);
                //return (_Where == end()
                //      || _DEBUG_LT_PRED(this->comp,
                //              _Keyval, _Key(_Where._Mynode()))
                //                      ? end() : _Where);
}
 
std::vector<std::pair<unsigned, unsigned>>::const_iterator vecfind(const std::vector<std::pair<unsigned, unsigned>>& a, const std::pair<unsigned, unsigned>& findme) {
    typedef std::vector<std::pair<unsigned, unsigned>>::const_iterator iterator;
	iterator iter = std::lower_bound(a.begin(), a.end(), findme,[](std::pair<unsigned,unsigned> const &lhs,std::pair<unsigned,unsigned> const &rhs){ return lhs.first<rhs.first;});
    return ( (iter == a.end() || iter->first<findme.first) ? a.end() : iter );
}
 
volatile unsigned nocheat = 0;
int main() {
        clock_t beg,end;
    const unsigned test_size = 100000;
    srand(0); //repeatable tests
        std::vector<std::pair<unsigned, unsigned>> shuffled(test_size);
    for(unsigned i=0; i<test_size; ++i)
        shuffled[i] = std::pair<unsigned, unsigned>(rand(), rand());
 
    nocheat = 0;
        std::map<unsigned, unsigned> a(shuffled.begin(), shuffled.end());
    {
        typedef std::map<unsigned, unsigned>::const_iterator iterator;
            beg = clock();
        for(unsigned i=0; i<seek_count; ++i) {
            const std::pair<unsigned, unsigned>& findme = shuffled[i%shuffled.size()];
            iterator iter = mapfind(a, findme);
            nocheat += iter->second;
        }
        end = clock();
            std::cout << "map: " << (end-beg) << ' ' << nocheat << '\n';
    }
    nocheat = 0;
    {
        typedef std::vector<std::pair<unsigned, unsigned>>::const_iterator iterator;
        std::vector<std::pair<unsigned, unsigned>> v(a.begin(), a.end());
            beg = clock();
        for(unsigned i=0; i<seek_count; ++i) {
            const std::pair<unsigned, unsigned>& findme = shuffled[i%shuffled.size()];
            iterator iter = vecfind(v, findme);
            nocheat += iter->second;
        }
        end = clock();
        std::cout << "vec: " << (end-beg) << ' ' << nocheat << '\n';
    }
 
        return 0;
}