lru 缓存 c++ 设计实现

LRU 缓存是一种常见的缓存淘汰算法，它的设计思想是将最近最少使用的数据从缓存中淘汰出去，以保证缓存的数据都是热点数据，从而提高缓存的命中率。

下面是一个基于双向链表和哈希表实现的 LRU 缓存的 C++ 设计实现：

#include <unordered_map>

struct Node {
    int key;
    int value;
    Node* prev;
    Node* next;
    Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
public:
    LRUCache(int capacity) : size_(capacity), head_(nullptr), tail_(nullptr) {}

    int get(int key) {
        auto iter = cache_.find(key);
        if (iter == cache_.end()) {
            return -1;
        } else {
            Node* node = iter->second;
            move_to_head(node);
            return node->value;
        }
    }

    void put(int key, int value) {
        auto iter = cache_.find(key);
        if (iter == cache_.end()) {
            Node* node = new Node(key, value);
            add_to_head(node);
            cache_[key] = node;
            if (cache_.size() > size_) {
                Node* tail = remove_tail();
                cache_.erase(tail->key);
                delete tail;
            }
        } else {
            Node* node = iter->second;
            node->value = value;
            move_to_head(node);
        }
    }

private:
    int size_;
    Node* head_;
    Node* tail_;
    std::unordered_map<int, Node*> cache_;

    void add_to_head(Node* node) {
        if (head_ == nullptr) {
            head_ = node;
            tail_ = node;
        } else {
            node->next = head_;
            head_->prev = node;
            head_ = node;
        }
    }

    void move_to_head(Node* node) {
        if (node == head_) {
            return;
        } else if (node == tail_) {
            tail_ = tail_->prev;
            tail_->next = nullptr;
        } else {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        node->next = head_;
        head_->prev = node;
        node->prev = nullptr;
        head_ = node;
    }

    Node* remove_tail() {
        Node* node = tail_;
        if (head_ == tail_) {
            head_ = nullptr;
            tail_ = nullptr;
        } else {
            tail_ = tail_->prev;
            tail_->next = nullptr;
        }
        return node;
    }
};

在这个实现中，我们使用了一个双向链表保存缓存中的数据，并使用一个哈希表来提高查找效率。在 `get` 操作中，如果缓存中不存在目标数据则返回 -1，否则将目标数据移到链表头部并返回其值。在 `put` 操作中，如果缓存中不存在目标数据则创建一个新的节点并将其添加到链表头部，如果缓存已满则删除链表尾部的节点。如果缓存中已存在目标数据则将其值更新并将其移动到链表头部。

需要注意的是，在 `move_to_head` 和 `remove_tail` 操作中，我们需要判断目标节点是否已经在链表的头部或尾部，以避免对空指针进行操作。此外，在每次操作中，我们还需要更新哈希表中对应节点的指针。