432. All O`one Data Structure

list是bidirectional iterator支持++和–

class AllOne {
public:
    /** Initialize your data structure here. */
    AllOne() {

    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if (key2bucket.count(key) == 0) {
            key2bucket[key] = buckets.insert(buckets.end(), {0, {key}}); // 找不到『旧bucket』就先插一个
        }
        auto curr = key2bucket[key], prev = std::prev(curr);
        if (curr == buckets.begin() || prev->value > curr->value + 1) {
            prev = buckets.insert(curr, {curr->value + 1, {}}); // 如果没有『新bucket』就插一个
        }
        prev->keys.insert(key); // 从旧bucket挪到新bucket
        curr->keys.erase(key);
        if (curr->keys.empty()) {
            buckets.erase(curr);
        }
        key2bucket[key] = prev;
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if (key2bucket.count(key) == 0) return;
        auto curr = key2bucket[key], next = std::next(curr);
        key2bucket.erase(key); // 先删key反正后边要不删了就删了要不写新key
        if (curr->value != 1) {
            if (next == buckets.end() || curr->value - 1 > next->value) {
                next = buckets.insert(next, {curr->value - 1, {}}); // 如果没有『新bucket』加一个
            }
            next->keys.insert(key); // 从旧bucket挪到新bucket
            key2bucket[key] = next;
        }
        curr->keys.erase(key);
        if (curr->keys.empty()) {
            buckets.erase(curr);
        }
    }

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        return buckets.empty() ? "" : *begin(buckets.front().keys);
    }

    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        return buckets.empty() ? "" : *begin(buckets.back().keys);
    }

    struct Bucket {
        int value = 0;
        unordered_set<string> keys;
    };
    unordered_map<string, list<Bucket>::iterator> key2bucket;
    list<Bucket> buckets;
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * string param_3 = obj.getMaxKey();
 * string param_4 = obj.getMinKey();
 */

class AllOne {
public:
    /** Initialize your data structure here. */
    AllOne() {

    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        auto it = key2it.find(key);
        if (it == key2it.end()) {
            if (freq2lst.count(1) == 0) {
                freq2lst[1] = lst.insert(lst.end(), list<KF>());
            }
            freq2lst[1]->emplace_front(key, 1);
            key2it[key] = freq2lst[1]->begin();
        } else {
            KF kf = *it->second;
            int freq = kf.freq;
            if (freq2lst.count(freq + 1) == 0) {
                freq2lst[freq + 1] = lst.insert(freq2lst[freq], list<KF>());
            }
            freq2lst[freq]->erase(it->second);
            freq2lst[++kf.freq]->push_front(kf);
            key2it[kf.key] = freq2lst[kf.freq]->begin();
            if (freq2lst[freq]->empty()) {
                lst.erase(freq2lst[freq]);
                freq2lst.erase(freq);
            }
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        auto it = key2it.find(key);
        if (it == key2it.end()) return;
        KF kf = *it->second;
        int freq = kf.freq;
        freq2lst[freq]->erase(it->second);
        if (freq == 1) {
            key2it.erase(kf.key);
        } else {
            if (freq2lst.count(freq - 1) == 0) {
                auto iter = freq2lst[freq];
                freq2lst[freq - 1] = lst.insert(++iter, list<KF>());
            }
            freq2lst[--kf.freq]->push_front(kf);
            key2it[kf.key] = freq2lst[kf.freq]->begin();
        }
        if (freq2lst[freq]->empty()) {
            lst.erase(freq2lst[freq]);
            freq2lst.erase(freq);
        }
    }

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        return lst.empty() ? "" : lst.front().front().key;
    }

    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        return lst.empty() ? "" : lst.back().front().key;
    }

    struct KF {
        KF(const string &key, int freq) : key(key), freq(freq) {}
        string key;
        int freq = 0;
    };
    unordered_map<string, list<KF>::iterator> key2it;
    unordered_map<int, list<list<KF>>::iterator> freq2lst;
    list<list<KF>> lst;
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * string param_3 = obj.getMaxKey();
 * string param_4 = obj.getMinKey();
 */