LRU和LFU（Go和CPP版本）

LRU

• LRU本来用deque写的，但是deque在有删除操作的时候还是莫名其妙指向end()前一位（实际上已经是第二位了），没办法，所以只好用list

插入：检查是否是末尾，是的话直接改值返回，不是的话看是否溢出，溢出的话删头节点对应的map然后pop，如果没溢出，如果本来就有这个key，删掉list对应元素留着map等后面再映射，然后添加到list末尾然后增加map映射。

读取：如果有这个值那就插入这个值更新然后return该值，如果没，那就返回-1

list+pair版本：（C++）

#include<iostream>
#include<list>
#include<deque>
#include<unordered_map>
using namespace std;
class LRUCache {
public:
    int maxsize;
    list<pair<int,int>>d;
    unordered_map<int,list<pair<int,int>>::iterator>m;
    LRUCache(int capacity) {
        maxsize=capacity;
    }
    
    int get(int key) {
        // get到的时候修改排列顺序
        if(m.count(key)){
            put(key,m[key]->second);     
            return m[key]->second;
        }else{
            return -1;
        }
    }
    
    void put(int key, int value) {
        // 如果本来就是末尾那就直接改value
        if(d.back().first==key){
            d.back().second=value;
            return;
        }
        if(m.count(key)){
            d.erase(m[key]);
        }
        else if(maxsize==d.size()){
            m.erase(d.front().first);
            d.pop_front();
        }
        d.push_back({key,value});
        m[key]=--d.end();
    }
};

int main() {
    // LRUCache* lRUCache = new LRUCache(2);
    // lRUCache->put(1, 1); // 缓存是 {1=1}
    // lRUCache->put(2, 2); // 缓存是 {1=1, 2=2}
    // std::cout<<lRUCache->get(1)<<endl;    // 返回 1
    // lRUCache->put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    // std::cout<<lRUCache->get(2)<<endl;    // 返回 -1 (未找到)
    // lRUCache->put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    // std::cout<<lRUCache->get(1)<<endl;    // 返回 -1 (未找到)
    // std::cout<<lRUCache->get(3)<<endl;    // 返回 3
    // std::cout<<lRUCache->get(4)<<endl;    // 返回 4
    LRUCache* lRUCache = new LRUCache(3);
    lRUCache->put(1,1);
    lRUCache->put(2,2);
    lRUCache->put(3,3);
    lRUCache->put(4,4);
    cout<<(lRUCache->get(4))<<endl;
    cout<<(lRUCache->get(3))<<endl;
    cout<<(lRUCache->get(2))<<endl;
    cout<<(lRUCache->get(1))<<endl;
    lRUCache->put(5,5);
    cout<<(lRUCache->get(1))<<endl;
    cout<<(lRUCache->get(2))<<endl;
    cout<<(lRUCache->get(3))<<endl;
    cout<<(lRUCache->get(4))<<endl;
    cout<<(lRUCache->get(5))<<endl;
}

List+map版本：（Go）

package main

import (
    "container/list"
    "fmt"
)

type Node struct {
    key   int
    value int
}
type LRUCache struct {
    m    map[int]*list.Element
    l    *list.List
    size int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        m:    make(map[int]*list.Element),
        l:    list.New(),
        size: capacity,
    }
}

func (this *LRUCache) Get(key int) int {
    if _, ok := this.m[key]; !ok {
        fmt.Println(-1)
        return -1
    }
    n := Node{key, this.m[key].Value.(Node).value}
    this.l.Remove(this.m[key])
    delete(this.m, this.m[key].Value.(Node).key)
    this.l.PushBack(n)
    this.m[key] = this.l.Back()
    fmt.Println(this.m[key].Value.(Node).value)
    return this.m[key].Value.(Node).value
}

func (this *LRUCache) Put(key int, value int) {
    if _, ok := this.m[key]; ok {
        if this.m[key].Value.(Node).value != value {
            n := Node{key, value}
            this.l.Remove(this.m[key])
            this.l.PushBack(n)
            this.m[key] = this.l.Back()
        } else {
            this.Get(key)
        }
    } else {
        if this.size == len(this.m) {
            k := this.l.Front().Value.(Node).key
            this.l.Remove(this.l.Front())
            delete(this.m, k)
        }
        n := Node{key, value}
        this.l.PushBack(n)
        this.m[key] = this.l.Back()
    }
    //fmt.Println("put",this.size,key,this.m)
}

func main() {
    lRUCache := Constructor(2)
    //lRUCache.Put(1, 1) // 缓存是 {1=1}
    //lRUCache.Put(2, 2) // 缓存是 {1=1, 2=2}
    //lRUCache.Get(1)    // 返回 1
    //lRUCache.Put(3, 3) // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    //lRUCache.Get(2)    // 返回 -1 (未找到)
    //lRUCache.Put(4, 4) // 该操作会G使得关键字 1 作废，缓存是 {4=4, 3=3}
    //lRUCache.Get(1)    // 返回 -1 (未找到)
    //lRUCache.Get(3)    // 返回 3
    //lRUCache.Get(4)    // 返回 4

    lRUCache.Get(2)
    lRUCache.Put(2, 6)
    lRUCache.Get(1)
    lRUCache.Put(1, 5)
    lRUCache.Put(1, 2)
    lRUCache.Get(1)
    lRUCache.Get(2)
}

• https://blog.csdn.net/u014779917/article/details/107857521

LFU

go语言版本

package main

import (
    "container/list"
    "fmt"
)

type Node struct {
    key    int // 因为list里面不知道是哪个key的node，删除的时候很麻烦，所以添加key标记
    value  int
    counts int
}
type LFUCache struct {
    min_freq int
    size     int
    // key -> value+counts
    KeyToNode map[int]Node
    // key's frequency -> list of key Node
    FreqToKeyList map[int]*list.List
}

func Constructor(capacity int) *LFUCache {
    return &LFUCache{
        min_freq:      1, // 最低的频率优先淘汰
        size:          capacity,
        KeyToNode:     make(map[int]Node),
        FreqToKeyList: make(map[int]*list.List), // list int
    }
}
func (this *LFUCache) Get(key int) int {
    if v, ok := this.KeyToNode[key]; ok {
        var next *list.Element
        // 利用key删除旧freq List中的老freq
        for e := this.FreqToKeyList[v.counts].Front(); e != nil; e = next {
            next = e.Next()
            if e.Value.(Node).key == key {
                this.FreqToKeyList[v.counts].Remove(e)
            }
        }
        // 被删除的可能是min_freq，这时候需要修改min_freq
        if this.FreqToKeyList[v.counts].Len() == 0 {
            if v.counts == this.min_freq {
                this.min_freq = v.counts + 1
            }
            // delete(this.FreqToKeyList,v.counts) 想想还是算了，留着复用影像也不大
        }
        // 添加Node到新的freq+1
        node := this.KeyToNode[key]
        node.counts += 1
        this.KeyToNode[key] = node

        // v.counts变成旧freq了
        freq := this.KeyToNode[key].counts
        if _, ok := this.FreqToKeyList[freq]; ok {
            this.FreqToKeyList[freq].PushBack(this.KeyToNode[key])
        } else {
            n := Node{key, this.KeyToNode[key].value, 1}
            l := list.New()
            l.PushBack(n)
            this.FreqToKeyList[freq] = l
        }
        fmt.Println(key, v.value)
        return v.value
    } else {
        fmt.Println(-1)
        return -1
    }
}

// 按key来算访问，key同value不同算访问同一个
// put到队尾，size溢出删除队头
func (this *LFUCache) Put(key int, value int) {
    if this.size <= 0 {
        return
    }
    if _, ok := this.KeyToNode[key]; ok {
        // 有对应项 , 借用Get更新freq++ , 然后修改value
        this.Get(key)
        a := this.KeyToNode[key]
        a.value = value
        this.KeyToNode[key] = a
        for e := this.FreqToKeyList[this.KeyToNode[key].counts].Front(); e != nil; e = e.Next() {
            if e.Value.(Node).key == key {
                e.Value = Node{key, value, 1}
                // e.Value.(Node).value = value  无法直接修改map对象的属性，只能覆盖
            }
        }
    } else {
        // 没有对应的项 , 如果硬塞会溢出那就删掉min_freq尾巴上的node , 然后塞进 freq=1 的list
        if len(this.KeyToNode) == this.size {
            // 需要删除min_freq List的队头node
            delete(this.KeyToNode, this.FreqToKeyList[this.min_freq].Front().Value.(Node).key)
            this.FreqToKeyList[this.min_freq].Remove(this.FreqToKeyList[this.min_freq].Front())
        }
        if _, ok := this.FreqToKeyList[1]; ok {

        } else {
            // 没list就加
            this.FreqToKeyList[1] = list.New()
        }
        // min_freq肯定为1了，前面删除需要旧值所以就放后面修改
        this.min_freq = 1

        // 因为KeyToNode为空就添加新node
        n := Node{key, value, 1}
        this.KeyToNode[key] = n
        this.FreqToKeyList[1].PushBack(n)
    }
}
func main() {
    Cache := Constructor(2)
    Cache.Put(1, 1)
    Cache.Put(2, 2)
    Cache.Get(1)    // 返回 1
    Cache.Put(3, 3) // 去除键 2
    Cache.Get(2)    // 返回 -1（未找到）
    Cache.Get(3)    // 返回 3
    Cache.Put(4, 4) // 去除键 1
    Cache.Get(1)    // 返回 -1（未找到）
    Cache.Get(3)    // 返回 3
    Cache.Get(4)    // 返回 4
}