LeetCode LRUCache

51 阅读 0 评论 34 点赞

我是靠谱客的博主务实小伙，最近开发中收集的这篇文章主要介绍LeetCode LRUCache，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/*
LeetCode LRUCache（least recently used）简单实现

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the
following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise
return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its
capacity, it should invalidate the least recently used item before inserting a new item.

list + unorder_map
使用unorder_map 双向链表查找难的问题
使用list 前面为最近访问的元素
可以尝试将value换成 template<T>更加的通用
主要练习 list 和 unorder_map的使用
*/

#include "type.h"

class LRUCache{
private:
    struct CacheNode{
        int key;
        int value;
        CacheNode(int key,int value):key(key),value(value){}
    };
public:
    typedef list<CacheNode> CacheType;
    LRUCache(int capacity):capacity(capacity){}
    void set(int key, int value);
    int get(int key);
private:
    int size;   //当前数据
    int capacity;//空间
    CacheType cacheList;
    unordered_map<int ,CacheType::iterator> cacheMap;
};

void LRUCache::set(int key, int value){
    //判断是否存在
    if (cacheMap.find(key) == cacheMap.end())//不存在
    {
        if (capacity == cacheList.size())//删除最后一个元素
        {
            cacheMap.erase(cacheList.back().key);
            cacheList.pop_back();
        }
        cacheList.push_front(CacheNode(key,value));
        cacheMap[key] = cacheList.begin();
    } 
    else//更新 value  将元素一道list头
    {
        cacheMap[key]->value = value;
        cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);//splice 将cacheMap[key] 插入到cacheList.begin位置

        cacheMap[key] = cacheList.begin();
    }

}

int LRUCache::get(int key){

    if (cacheMap.find(key) != cacheMap.end())
    {
            //把刚才访问的节点移动到链表头部 更新map中的地址
            cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);
            cacheMap[key] = cacheList.begin();
             cacheMap[key]->value;
    }
    return -1;
}