C++ with list, map, and unordered_map


  • 0
    M
    1. FLIST = list<pair<int, int>> is the list save data entry with the same frequency count, with list you can easier splice item to next frequency list.
    2. map<int, pair<int, int>> saves all the data in a map of frequency to list.
    3. unordered_map<int, pair<int, FLIST::iterator>> index key to pair of frequency and list iterator.

    class LFUCache {
    public:
    LFUCache(int capacity) : capacity_(capacity) {
    }

    int get(int key) {
        if (capacity_ < 1 || idx.count(key) == 0) return -1; 
        int f = idx[key].first++;
        dat[f+1].splice(dat[f+1].end(), dat[f], idx[key].second);
        if (dat[f].empty()) dat.erase(f);
        return idx[key].second->second;
    }
    
    void put(int key, int value) {
        if (capacity_ < 1) return;
        if (idx.count(key)) {
            int f = idx[key].first++;
            dat[f+1].splice(dat[f+1].end(), dat[f], idx[key].second);
            if (dat[f].empty()) dat.erase(f);
            idx[key].second->second = value;
        } else {
            if (capacity_ == (int)idx.size()) {
                int k = dat.begin()->second.begin()->first;
                idx.erase(k);
                dat.begin()->second.pop_front();
                if (dat.begin()->second.empty()) dat.erase(dat.begin());
            }
            dat[1].push_back({key, value});
            idx[key] = make_pair(1, prev(dat[1].end()));
        }
    }
    

    private:
    int capacity_;
    using FLIST=list<pair<int, int>>;
    map<int, FLIST> dat;
    unordered_map<int, pair<int, FLIST::iterator>> idx;
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.