language: C++11 (gcc-4.7.2)
date: 456 days 16 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#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);
    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;
    {
        typedef std::map<unsigned, unsigned>::const_iterator iterator;
        std::map<unsigned, unsigned> a(shuffled.begin(), shuffled.end());
            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>> a(shuffled.begin(), shuffled.end());
        std::sort(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(a, findme);
            nocheat += iter->second;
        }
        end = clock();
        std::cout << "vec: " << (end-beg) << ' ' << nocheat << '\n';
    }
 
        return 0;
}