警示后人
查看原帖
警示后人
513329
徐晨轩✅楼主2023/6/24 16:04

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;
    }
};
2023/6/24 16:04
加载中...