fork(4) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <map>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <vector>
  7.  
  8. static const unsigned seek_count = 10000000;
  9.  
  10. std::map<unsigned, unsigned>::const_iterator mapfind(const std::map<unsigned, unsigned>& a, const std::pair<unsigned, unsigned>& findme) {
  11.     return a.find(findme.first);
  12.         //MSVC9 implimentation, for compaison with vector code
  13.                 //const_iterator _Where = lower_bound(_Keyval);
  14.                 //return (_Where == end()
  15.                 //      || _DEBUG_LT_PRED(this->comp,
  16.                 //              _Keyval, _Key(_Where._Mynode()))
  17.                 //                      ? end() : _Where);
  18. }
  19.  
  20. std::vector<std::pair<unsigned, unsigned>>::const_iterator vecfind(const std::vector<std::pair<unsigned, unsigned>>& a, const std::pair<unsigned, unsigned>& findme) {
  21.     typedef std::vector<std::pair<unsigned, unsigned>>::const_iterator iterator;
  22. 	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;});
  23.     return ( (iter == a.end() || iter->first<findme.first) ? a.end() : iter );
  24. }
  25.  
  26. volatile unsigned nocheat = 0;
  27. int main() {
  28.         clock_t beg,end;
  29.     const unsigned test_size = 100000;
  30.     srand(0); //repeatable tests
  31.         std::vector<std::pair<unsigned, unsigned>> shuffled(test_size);
  32.     for(unsigned i=0; i<test_size; ++i)
  33.         shuffled[i] = std::pair<unsigned, unsigned>(rand(), rand());
  34.  
  35.     nocheat = 0;
  36.         std::map<unsigned, unsigned> a(shuffled.begin(), shuffled.end());
  37.     {
  38.         typedef std::map<unsigned, unsigned>::const_iterator iterator;
  39.             beg = clock();
  40.         for(unsigned i=0; i<seek_count; ++i) {
  41.             const std::pair<unsigned, unsigned>& findme = shuffled[i%shuffled.size()];
  42.             iterator iter = mapfind(a, findme);
  43.             nocheat += iter->second;
  44.         }
  45.         end = clock();
  46.             std::cout << "map: " << (end-beg) << ' ' << nocheat << '\n';
  47.     }
  48.     nocheat = 0;
  49.     {
  50.         typedef std::vector<std::pair<unsigned, unsigned>>::const_iterator iterator;
  51.         std::vector<std::pair<unsigned, unsigned>> v(a.begin(), a.end());
  52.             beg = clock();
  53.         for(unsigned i=0; i<seek_count; ++i) {
  54.             const std::pair<unsigned, unsigned>& findme = shuffled[i%shuffled.size()];
  55.             iterator iter = vecfind(v, findme);
  56.             nocheat += iter->second;
  57.         }
  58.         end = clock();
  59.         std::cout << "vec: " << (end-beg) << ' ' << nocheat << '\n';
  60.     }
  61.  
  62.         return 0;
  63. }
Success #stdin #stdout 4.91s 6000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
map: 2940000 28231668
vec: 1890000 28231668
https://ideone.com/b3OnH
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!