Attempt using C++


  • 1
    J

    Shitty code.

    class LFUCache {
    public:
        LFUCache(int capacity) {
            m_capacity = capacity;
        }
    
        int get(int key) {
            if (!m_capacity) return -1;
            auto it = cache.find(key);
            if (it == cache.end()) return -1;
            touch(it);
            return it->second.first;
        }
    
        void set(int key, int value) {
            if (!m_capacity) return;
            auto it = cache.find(key);
            if (it != cache.end()) {
                touch(it); // exist
                cache[key].first = value;
            } else { // doesn't exist -> insert
                if (cache.size() == m_capacity) {
                    // delete least used element
                    int &freq = std::get<0>(used.front());
                    list<int> &order = std::get<1>(used.front());
                    unordered_map<int, list<int>::iterator> &s = std::get<2>(used.front());
                    cache.erase(order.front());
                    s.erase(s.find(order.front()));
                    order.pop_front();
                    if (order.empty()) used.pop_front();
                }
                auto freq = used.begin();
                if (std::get<0>(*freq) != 1) {
                    freq = used.insert(freq, make_tuple(1, list<int>(), unordered_map<int, list<int>::iterator>()));
                }
                std::get<1>(*freq).push_back(key);
                std::get<2>(*freq).insert({key, --std::get<1>(*freq).end()});
                cache[key] = {value, freq};
            }
        }
    
    private:
        using freqLRU = list<tuple<int, list<int>, unordered_map<int, list<int>::iterator>>>;
        using freqLRUIter = freqLRU::iterator; // least recent to most recent
        unordered_map<int, pair<int, freqLRUIter>> cache;
        freqLRU used;  // least frequent to most frequent
        int m_capacity; // cache size maximum
    
        void touch(unordered_map<int, pair<int, freqLRUIter>>::iterator it) {
            freqLRUIter freq = it->second.second;
            std::get<1>(*freq).erase(std::get<2>(*freq).find(it->first)->second);
            std::get<2>(*freq).erase(std::get<2>(*freq).find(it->first));
    
            auto next_freq = freq;
            next_freq++;
            if (next_freq == used.end() || std::get<0>(*next_freq) != std::get<0>(*freq) + 1) {
                next_freq = used.insert(next_freq, make_tuple(std::get<0>(*freq) + 1, list<int>(),
                                                              unordered_map<int, list<int>::iterator>()));
            }
    
            std::get<1>(*next_freq).push_back(it->first);
            std::get<2>(*next_freq).insert({it->first, --std::get<1>(*next_freq).end()});
    
            if (std::get<2>(*freq).empty()) {
                used.erase(freq);
            }
    
            it->second.second = next_freq;
        }
    };
    
    • list item

Log in to reply
 

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