C++11 O(1) solution with 2 unordered_maps and a linked list


  • 0
    B

    O(1) but slow, however I think it's easy to understand, code and comment should explain themselves

    class LFUCache {
    private:
        using key_type = int;
        using count_type = unsigned int;
        using value_type = int;
        using list_type = std::list< std::pair<key_type, value_type> >;
        std::unordered_map<key_type, std::pair<count_type, list_type::iterator> > m_map; // iterator corresponds to key
        std::unordered_map<count_type, list_type::iterator> m_listmap; // count and head(MRU) of that segment
        list_type m_list;
        size_t m_capacity;
        
    public:
        std::pair<count_type, list_type::iterator> move(int key) {
            const auto count = m_map[key].first;
            auto itrToBeMoved = m_map[key].second;
            const auto newCount = count+1;
            if (m_listmap.find(newCount) != m_listmap.end()) { // newCount already exists, move iterator there
                if (itrToBeMoved == m_listmap[count]) {// head of count is the same as the iterator to be moved
                    m_listmap[count] = std::next(itrToBeMoved); // so advance head of count pointer to next one
                }
    
                m_list.splice(m_listmap[newCount], m_list, itrToBeMoved); // move target iterator to head of newCount
                m_listmap[newCount] = itrToBeMoved;
            }
            else {
                if (itrToBeMoved == m_listmap[count]) {
                    m_listmap[count] = std::next(itrToBeMoved); // advance head of count pointer to next one
                }
                else { // the node to be moved is not the head of this count, so move it to before the head
                    m_list.splice(m_listmap[count], m_list, itrToBeMoved);
                }
                m_listmap[newCount] = itrToBeMoved;
            }
            
            if (m_listmap[count] == m_list.end() || m_map[m_listmap[count]->first].first != count) {
                // if count is no longer pointing to anything useful, delete it
                m_listmap.erase(count);
            }
            
            return std::make_pair(newCount, m_listmap[newCount]);
        }
    
    public:
        explicit LFUCache(int capacity) : m_capacity(capacity) {
            
        }
        
        int get(int key) {
            if (m_capacity == 0) {
                return -1;
            }
            
            if (m_map.find(key) != m_map.end()) { // key exists
                auto newValue = this->move(key);
                m_map[key] = newValue;
    
                return newValue.second->second;
            }
            else {
                return -1;
            }
        }
        
        void put(int key, int value) {
            if (m_capacity == 0) {
                return;
            }
            
            if (m_map.find(key) != m_map.end()) { // key already exists
                auto newValue = this->move(key);
                newValue.second->second = value;
                m_map[key] = newValue;
            }
            else {
                if (m_list.size() == m_capacity) {
                    const auto keyToBeDeleted = m_list.back().first;
                    const auto count = m_map[keyToBeDeleted].first;
        
                    auto itrToBeInvalidated = m_listmap[count];
                    if (*itrToBeInvalidated == m_list.back()) { // head of count is the last element in list, remove it
                        m_listmap.erase(count);
                    }
                    m_map.erase(keyToBeDeleted);
                    m_list.pop_back();
                }
                
                const constexpr auto count = 1;
                auto itr = m_list.end();
                if (m_listmap.find(count) != m_listmap.end()) { // has listmap[1]
                    itr = m_list.emplace(m_listmap[count], key, value);
                }
                else { // first element of listmap with count 1
                    itr = m_list.emplace(m_list.end(), key, value);
                }
                m_listmap[count] = itr;
                m_map.emplace(std::make_pair(key, std::make_pair(count, itr)));
            }
        }
    };
    

Log in to reply
 

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