Advertisement
Guest User

Untitled

a guest
Apr 29th, 2016
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.35 KB | None | 0 0
  1. #include <iostream>
  2. #include <utility>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <unordered_map>
  6.  
  7. using key_type = unsigned;
  8.  
  9. struct SomeClass
  10. {
  11. SomeClass(key_type _x1, key_type _x2, key_type _x3)
  12. :x1(_x1), x2(_x2), x3(_x3)
  13. {}
  14.  
  15. key_type x1, x2, x3;
  16.  
  17. void print() const
  18. {
  19. std::cout << x1 << x2 << x3 << "\n";
  20. }
  21. };
  22.  
  23. template <size_t M>
  24. key_type key(const SomeClass& val) {}
  25. template<>
  26. key_type key<1>(const SomeClass& val) {return val.x1;}
  27. template<>
  28. key_type key<2>(const SomeClass& val) {return val.x2;}
  29. template<>
  30. key_type key<3>(const SomeClass& val) {return val.x3;}
  31.  
  32. using SSPair = std::pair<size_t, size_t>;
  33.  
  34. struct PairHasher
  35. {
  36. size_t operator()(const SSPair& p) const
  37. {
  38. return (p.first * 0x1f1f1f1f) ^ p.second;
  39. }
  40. };
  41.  
  42. struct KeyCasher
  43. {
  44. size_t idx;
  45.  
  46. using PVector = std::vector<SomeClass> *;
  47. static PVector data;
  48.  
  49. using HashMap = std::unordered_map<SSPair, key_type, PairHasher>;
  50. static HashMap value;
  51.  
  52. template<size_t M>
  53. key_type cashed_key() const
  54. {
  55. std::pair<size_t, size_t> p {idx, M};
  56. if (value.find(p) == value.end())
  57. {
  58. key_type val = key<M>((*data)[idx]);
  59. value[p] = val;
  60. return val;
  61. }
  62.  
  63. return value[p];
  64. }
  65.  
  66. void print() const
  67. {
  68. (*data)[idx].print();
  69. }
  70. };
  71.  
  72. KeyCasher::PVector KeyCasher::data = nullptr;
  73. KeyCasher::HashMap KeyCasher::value;
  74.  
  75. bool cmp(const KeyCasher& lft, const KeyCasher& rgt)
  76. {
  77. key_type lkey, rkey;
  78. lkey = lft.cashed_key<1>();
  79. rkey = rgt.cashed_key<1>();
  80. if (lkey != rkey)
  81. return lkey < rkey;
  82.  
  83. lkey = lft.cashed_key<2>();
  84. rkey = rgt.cashed_key<2>();
  85. if (lkey != rkey)
  86. return lkey < rkey;
  87.  
  88. lkey = lft.cashed_key<3>();
  89. rkey = rgt.cashed_key<3>();
  90. if (lkey != rkey)
  91. return lkey < rkey;
  92. }
  93.  
  94.  
  95. std::vector<SomeClass> input {
  96. {1,1,1}, {1,1,2}, {1,1,3},
  97. {1,2,1}, {1,2,2}, {1,2,3},
  98. {1,3,1}, {1,3,2}, {1,3,3},
  99.  
  100. {2,1,1}, {2,1,2}, {2,1,3},
  101. {2,2,1}, {2,2,2}, {2,2,3},
  102. {2,3,1}, {2,3,2}, {2,3,3},
  103.  
  104. {3,1,1}, {3,1,2}, {3,1,3},
  105. {3,2,1}, {3,2,2}, {3,2,3},
  106. {3,3,1}, {3,3,2}, {3,3,3}
  107. };
  108.  
  109. int main()
  110. {
  111. using namespace std;
  112.  
  113. random_shuffle(input.begin(), input.end());
  114. cout << "shuffled\n";
  115. for(const auto& val: input)
  116. val.print();
  117.  
  118. vector<KeyCasher> output(input.size());
  119. KeyCasher::data = &input;
  120. for(int i=0; i < output.size(); ++i)
  121. output[i].idx = i;
  122.  
  123. sort(output.begin(), output.end(), cmp);
  124.  
  125. cout << "\nsorted\n";
  126. for(const auto& val: output)
  127. val.print();
  128.  
  129. system("pause");
  130. return 0;
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement