fork(3) download
  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
stdin
Standard input is empty
stdout
map: 2940000 28231668
vec: 1890000 28231668