Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <utility>
- #include <vector>
- #include <algorithm>
- #include <unordered_map>
- using key_type = unsigned;
- struct SomeClass
- {
- SomeClass(key_type _x1, key_type _x2, key_type _x3)
- :x1(_x1), x2(_x2), x3(_x3)
- {}
- key_type x1, x2, x3;
- void print() const
- {
- std::cout << x1 << x2 << x3 << "\n";
- }
- };
- template <size_t M>
- key_type key(const SomeClass& val) {}
- template<>
- key_type key<1>(const SomeClass& val) {return val.x1;}
- template<>
- key_type key<2>(const SomeClass& val) {return val.x2;}
- template<>
- key_type key<3>(const SomeClass& val) {return val.x3;}
- using SSPair = std::pair<size_t, size_t>;
- struct PairHasher
- {
- size_t operator()(const SSPair& p) const
- {
- return (p.first * 0x1f1f1f1f) ^ p.second;
- }
- };
- struct KeyCasher
- {
- size_t idx;
- using PVector = std::vector<SomeClass> *;
- static PVector data;
- using HashMap = std::unordered_map<SSPair, key_type, PairHasher>;
- static HashMap value;
- template<size_t M>
- key_type cashed_key() const
- {
- std::pair<size_t, size_t> p {idx, M};
- if (value.find(p) == value.end())
- {
- key_type val = key<M>((*data)[idx]);
- value[p] = val;
- return val;
- }
- return value[p];
- }
- void print() const
- {
- (*data)[idx].print();
- }
- };
- KeyCasher::PVector KeyCasher::data = nullptr;
- KeyCasher::HashMap KeyCasher::value;
- bool cmp(const KeyCasher& lft, const KeyCasher& rgt)
- {
- key_type lkey, rkey;
- lkey = lft.cashed_key<1>();
- rkey = rgt.cashed_key<1>();
- if (lkey != rkey)
- return lkey < rkey;
- lkey = lft.cashed_key<2>();
- rkey = rgt.cashed_key<2>();
- if (lkey != rkey)
- return lkey < rkey;
- lkey = lft.cashed_key<3>();
- rkey = rgt.cashed_key<3>();
- if (lkey != rkey)
- return lkey < rkey;
- }
- std::vector<SomeClass> input {
- {1,1,1}, {1,1,2}, {1,1,3},
- {1,2,1}, {1,2,2}, {1,2,3},
- {1,3,1}, {1,3,2}, {1,3,3},
- {2,1,1}, {2,1,2}, {2,1,3},
- {2,2,1}, {2,2,2}, {2,2,3},
- {2,3,1}, {2,3,2}, {2,3,3},
- {3,1,1}, {3,1,2}, {3,1,3},
- {3,2,1}, {3,2,2}, {3,2,3},
- {3,3,1}, {3,3,2}, {3,3,3}
- };
- int main()
- {
- using namespace std;
- random_shuffle(input.begin(), input.end());
- cout << "shuffled\n";
- for(const auto& val: input)
- val.print();
- vector<KeyCasher> output(input.size());
- KeyCasher::data = &input;
- for(int i=0; i < output.size(); ++i)
- output[i].idx = i;
- sort(output.begin(), output.end(), cmp);
- cout << "\nsorted\n";
- for(const auto& val: output)
- val.print();
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement