146. LRU 캐 시 메커니즘

제목 설명
당신 이 파악 한 데이터 구 조 를 활용 하여 LRU (최근 최소 사용) 캐 시 체 제 를 설계 하고 실현 합 니 다.데이터 get 을 가 져 오고 데 이 터 를 기록 하 는 put 를 지원 해 야 합 니 다.
데이터 get (key) 가 져 오기 - 키 (key) 가 캐 시 에 존재 하면 키 의 값 (항상 정수) 을 가 져 옵 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.데이터 put (key, value) 를 기록 합 니 다. - 키 가 존재 하지 않 으 면 데이터 값 을 기록 합 니 다.캐 시 용량 이 상한 선 에 이 르 렀 을 때 새 데 이 터 를 쓰기 전에 최근 에 가장 적 게 사용 한 데이터 값 을 삭제 하여 새로운 데이터 값 에 공간 을 남 겨 야 합 니 다.
진급:
당신 은 O (1) 시간 복잡 도 내 에 이 두 가지 조작 을 완성 할 수 있 습 니까?
예시:

LRUCache cache = new LRUCache( 2 /*      */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       //     1
cache.put(3, 3);    //          2   
cache.get(2);       //    -1 (   )
cache.put(4, 4);    //          1   
cache.get(1);       //    -1 (   )
cache.get(3);       //     3
cache.get(4);       //     4

분석 하 다.
접근 할 때마다 키 를 대기 열 끝 에 대기 열 이 가득 찼 을 때 처음부터 list 를 삭제 하고 복잡 도 를 삭 제 했 을 때 O (1). unordered 사용 하기map 는 key 의 위 치 를 기록 하여 key 를 통 해 list 요 소 를 삭제 하 는 복잡 도 를 O (1) 에 달성 하 는 목적 을 달성 합 니 다.
코드

class LRUCache {
public:
    LRUCache(int capacity) {
        m_cap = capacity;
    }
    
    int get(int key) {
        auto it = m_map.find(key);
        if(it == m_map.end()) {
            return -1;
        } 
        int value = it->second->second;
        //    ，     key      
        m_list.erase(it->second);
        m_map.erase(it);
        m_list.push_back(make_pair(key, value));
        m_map[key] =  --m_list.end();
        return value; 
    }
    
    void put(int key, int value) {
        //          
        auto it = m_map.find(key);
        if(it != m_map.end()) {
            m_list.erase(it->second);
            m_map.erase(it);
        }
        if(m_map.size() >= m_cap) {
            auto it= m_map.find(m_list.front().first);
            if(it!= m_map.end()) {
                m_list.erase(it->second);
                m_map.erase(it);
            }
        }
        m_list.push_back(make_pair(key, value));
        m_map[key] =  --m_list.end();
    }
private:
    list> m_list;
    unordered_map>::iterator> m_map;
    int m_cap;
};

제목 링크
https://leetcode-cn.com/problems/lru-cache/description/