Skip to content

Instantly share code, notes, and snippets.

@AtomKrieg
Last active April 29, 2016 07:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save AtomKrieg/6fb6d3d8ae80842efb1d7d81d275017e to your computer and use it in GitHub Desktop.
Save AtomKrieg/6fb6d3d8ae80842efb1d7d81d275017e to your computer and use it in GitHub Desktop.
Sort obj by M functions with cashes
#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>();
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment