fork(1) download
  1. #include <ctime>
  2. #include <algorithm>
  3. #include <limits>
  4. #include <map>
  5. #include <iostream>
  6. #include <string>
  7.  
  8. using namespace std;
  9.  
  10. inline int rand_int(int max) { return rand() % max; }
  11.  
  12. inline int rand_int(int min, int max) { return rand_int(max - min) + min; }
  13.  
  14. string rand_string()
  15. {
  16. const int iterations = rand_int(100);
  17. string result;
  18. result.reserve(iterations);
  19. for(size_t i = 0; i < result.size(); ++i)
  20. {
  21. result[i] = char(rand_int(int(numeric_limits<char>::min()),
  22. int(numeric_limits<char>::max())));
  23. }
  24. return result;
  25. }
  26.  
  27. int main()
  28. {
  29. clock_t start_m1 = clock();
  30. map<int, string> m1;
  31. for(int i = 0; i < 500000; ++i)
  32. {
  33. m1.insert(m1.end(), pair<int, string>(i, rand_string()));
  34. // map orders its elements according to the Key
  35. // The Key here is int
  36. // The for-loop generates sorted ints
  37. // hence the Keys are already sorted
  38. }
  39. clock_t stop_m1 = clock();
  40. cout << "The time it took to build map<int, string> is "
  41. << double(stop_m1 - start_m1) / CLOCKS_PER_SEC << " seconds" << '\n';
  42.  
  43. clock_t start_m2 = clock();
  44. map<string, int> m2;
  45. for(int i = 0; i < 500000; ++i)
  46. {
  47. m2[rand_string()] = i;
  48. // The Key here is string
  49. // Randoms strings are generated that are not sorted
  50. // So to build the map in a sorted order,
  51. // bool operator<(const string& _Left, const string& _Right)
  52. // has to be called a lot of times
  53. // to insert the elements in a sorted order
  54. // So many calls to that function means that
  55. // building m2 should take a longer time than m1
  56. // also considering that the Keys of m1 are already sorted
  57. }
  58. clock_t stop_m2 = clock();
  59. cout << "The time it took to build map<string, int> is "
  60. << double(stop_m2 - start_m2) / CLOCKS_PER_SEC << " seconds" << '\n';
  61.  
  62. cout << "Please enter a character to exit:" << "\n";
  63. char ch = 0;
  64. cin >> ch;
  65.  
  66. return 0;
  67. }
Success #stdin #stdout 0.32s 53112KB
stdin
Standard input is empty
stdout
The time it took to build map<int, string> is 0.18 seconds
The time it took to build map<string, int> is 0.08 seconds
Please enter a character to exit: