lru lfu c++

LRU (Least Recently Used) 和 LFU (Least Frequently Used) 都是常用的缓存淘汰算法。它们都用于在缓存空间不足时决定哪些数据应该被淘汰，以便为新的数据腾出空间。

LRU 算法根据数据的访问时间来进行淘汰，即最近最少使用的数据被淘汰。当一个数据被访问时，它会被移动到缓存的顶部，而最久未访问的数据则会被淘汰。

LFU 算法根据数据的访问频率来进行淘汰，即使用次数最少的数据被淘汰。当一个数据被访问时，其访问频率会被增加。当缓存空间不足时，LFU 算法会淘汰访问频率最低的数据。

以上是关于 LRU 和 LFU 缓存淘汰算法的简要介绍。若有进一步的问题，请随时提问。

相关问题

lru算法c++

以下是C++实现的LRU算法代码：

#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if (cache.count(key) == 0) {
            return -1;
        }
        // 把当前访问的元素移到链表头部，并更新unordered_map中该元素的地址
        cacheList.splice(cacheList.begin(), cacheList, cache[key]);
        cache[key] = cacheList.begin();

        return cache[key]->second;
    }
    
    void put(int key, int value) {
        if (cache.count(key) == 0) {
            if (cacheList.size() == cap) {
                // 删除链表最后一个元素
                auto last = cacheList.end();
                last--;
                cache.erase(last->first);
                cacheList.erase(last);
            }
            // 插入新元素到链表头部，并在unordered_map中记录该元素的地址
            cacheList.push_front(make_pair(key, value));
            cache[key] = cacheList.begin();
        }
        else {
            // 把当前访问的元素移到链表头部，并更新unordered_map中该元素的地址
            cacheList.splice(cacheList.begin(), cacheList, cache[key]);
            cache[key] = cacheList.begin();
            // 更新元素的值
            cache[key]->second = value;
        }
    }

private:
    int cap;
    // cacheList的元素是pair<key, value>，其中key和unordered_map中的key相同，
    // value是实际存储的value值。链表按照访问时间从新到旧排序
    list<pair<int, int>> cacheList;
    // unordered_map的key是LRU缓存的key，value是LRU缓存中key对应节点在cacheList中的地址
    unordered_map<int, list<pair<int, int>>::iterator> cache;
};

int main() {
    LRUCache lruCache(2);

    lruCache.put(1, 1);
    lruCache.put(2, 2);
    cout << lruCache.get(1) << endl; // 1
    lruCache.put(3, 3);
    cout << lruCache.get(2) << endl; // -1
    lruCache.put(4, 4);
    cout << lruCache.get(1) << endl; // -1
    cout << lruCache.get(3) << endl; // 3
    cout << lruCache.get(4) << endl; // 4

    return 0;
}

LRU算法的核心思想是，缓存一定的数据，并在缓存满时，删除最近最少访问的数据，为新的数据留出空间。以上代码实现了一个LRU缓存类，使用了双向链表和哈希表。其中双向链表按照访问时间从新到旧排序，哈希表记录了每个key对应的节点在链表中的地址。在get操作中，如果请求的key不存在于哈希表中，则返回-1；如果存在于哈希表中，则把对应的节点移到链表头部，并返回节点的value值。在put操作中，如果请求的key不存在于哈希表中，则把新元素插入到链表头部，并删除链表最后一个元素；如果存在于哈希表中，则把对应的节点移到链表头部，并更新节点的value值。

LRU算法c++

以下是一个简单的 C++ 实现 LRU 算法的例子：

#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

class LRUCache {
private:
    int capacity;
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;
    list<pair<int, int>> cacheList;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1;
        }
        auto iter = cacheMap[key];
        int value = iter->second;
        cacheList.erase(iter);
        cacheList.push_front(make_pair(key, value));
        cacheMap[key] = cacheList.begin();
        return value;
    }

    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            auto iter = cacheMap[key];
            cacheList.erase(iter);
        }
        cacheList.push_front(make_pair(key, value));
        cacheMap[key] = cacheList.begin();
        if (cacheMap.size() > capacity) {
            auto lastPair = cacheList.back();
            cacheMap.erase(lastPair.first);
            cacheList.pop_back();
        }
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 1
    cache.put(3, 3);
    cout << cache.get(2) << endl; // -1
    cache.put(4, 4);
    cout << cache.get(1) << endl; // -1
    cout << cache.get(3) << endl; // 3
    cout << cache.get(4) << endl; // 4
    return 0;
}

LRU 算法利用哈希表和双向链表实现，其中哈希表用于快速查找，双向链表用于维护访问顺序。在 get 操作中，如果 key 不存在，返回 -1；否则将该 key 对应的节点移动到链表头部，并返回对应的 value 值。在 put 操作中，如果 key 已经存在，将对应的节点移到链表头部；否则将新的 key-value 对添加到链表头部，判断是否超过缓存容量，如果超过则删除链表尾部对应的 key-value 对。