unordered_map 对于自定义类(如 node)没有自动的 hash 算法,故需要自己定义。
方法如下:
struct node {
int ac_count, time;
node() { }
node(int x, int y) {
ac_count = x, time = y;
}
bool operator < (node x) const {
if (ac_count != x.ac_count) return ac_count > x.ac_count;
else return time < x.time;
}
bool operator == (node x) const {
return ac_count == x.ac_count && time == x.time;
}
};
// ****** 重点 ******
struct hash_function {
size_t operator()(node a) const {
return hash<int>()(a.ac_count) ^ hash<int>()(a.time);
}
};
template<class T, class Compare = less<pair<T, int>>, class HashFunction = hash<T>>
class multi_rbtree {
private:
tree<pair<T, int>, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update> t;
// 使用
std::unordered_map<T, int, HashFunction> cnt;
public:
multi_rbtree() {
t = tree<pair<T, int>, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>();
cnt.clear();
}
void insert(T x) {
t.insert({x, ++cnt[x]});
}
void erase(T x) {
t.erase({x, cnt[x]--});
}
size_t order_of_key(T x) {
return t.order_of_key({x, 1});
}
T find_by_order(size_t x) {
return t.find_by_order(x)->first;
}
T prev(T x) {
return t.find_by_order(t.order_of_key({x, 1}) - 1)->first;
}
T next(T x) {
return t.find_by_order(t.order_of_key({x, cnt[x]}) + (t.find({x, 1}) != t.end()))->first;
}
};