fork download
  1. #include <algorithm>
  2. #include <iomanip>
  3. #include <iostream>
  4. #include <string>
  5. #include <vector>
  6.  
  7. int count_copy_construction;
  8. int count_move_construction;
  9. int count_copy_assignment;
  10. int count_move_assignment;
  11. int count_swap;
  12. int count_comparison;
  13.  
  14. struct A {
  15. std::string value;
  16. A() : value("") {}
  17. A(const A &a) : value(a.value) {
  18. ++count_copy_construction;
  19. }
  20. A(A &&a) : value(std::move(a.value)) {
  21. ++count_move_construction;
  22. }
  23. A &operator=(const A &a) {
  24. ++count_copy_assignment;
  25. value = a.value;
  26. return *this;
  27. }
  28. A &operator=(A &&a) {
  29. ++count_move_assignment;
  30. value = std::move(a.value);
  31. return *this;
  32. }
  33. bool operator<(const A &a) const {
  34. ++count_comparison;
  35. return value < a.value;
  36. }
  37. };
  38. void swap(A &a, A &b) {
  39. ++count_swap;
  40. std::swap(a.value, b.value);
  41. }
  42.  
  43. template<typename I>
  44. void MergeSort(I first, I last) {
  45. if (last - first > 1) {
  46. I mid = first + (last - first) / 2;
  47. MergeSort(first, mid);
  48. MergeSort(mid, last);
  49. std::inplace_merge(first, mid, last);
  50. }
  51. }
  52.  
  53. int main() {
  54. for (int method = 0; method < 1; ++method) {
  55. std::vector<A> a(1000000);
  56. unsigned first = 0;
  57. unsigned last = a.size();
  58. for (unsigned i = 0; i < 100; ++i) {
  59. const std::string s = std::string()
  60. + (char)('a' + i / 25)
  61. + (char)('a' + i % 25);
  62. for (unsigned j = 0; j < i + 2; ++j) {
  63. a[first++].value = s;
  64. }
  65. a[--last].value = s;
  66. }
  67. for (unsigned pos = first; pos < last; ++pos) {
  68. a[pos].value = std::string() + "z"
  69. + (char)('a' + pos % 11)
  70. + (char)('a' + pos % 13)
  71. + (char)('a' + pos % 17)
  72. + (char)('a' + pos % 19)
  73. + (char)('a' + pos % 23);
  74. }
  75. count_copy_construction = 0;
  76. count_move_construction = 0;
  77. count_copy_assignment = 0;
  78. count_move_assignment = 0;
  79. count_swap = 0;
  80. count_comparison = 0;
  81. switch (method) {
  82. case 0:
  83. std::sort(a.begin(), a.end());
  84. break;
  85. case 1:
  86. std::partial_sort(a.begin(), a.end(), a.end());
  87. break;
  88. case 2:
  89. std::stable_sort(a.begin(), a.end());
  90. break;
  91. case 3:
  92. MergeSort(a.begin(), a.end());
  93. break;
  94. }
  95. std::cerr
  96. << std::setw(8) << count_copy_construction << " "
  97. << std::setw(8) << count_move_construction << " "
  98. << std::setw(8) << count_copy_assignment << " "
  99. << std::setw(8) << count_move_assignment << " "
  100. << std::setw(8) << count_swap << " "
  101. << std::setw(8) << count_comparison << std::endl;
  102. }
  103. return 0;
  104. }
  105.  
Success #stdin #stdout #stderr 4.03s 34464KB
stdin
Standard input is empty
stdout

Standard output is empty

stderr
       0  5496978        0 22421816     1078  59277065