使用c++编写LRU函数demo

好的，我可以回答这个问题。LRU（Least Recently Used）是一种缓存淘汰算法，它会淘汰最近最少使用的缓存块。以下是一个使用C语言编写的LRU函数demo：

#include <stdio.h>
#include <stdlib.h>

#define CACHE_SIZE 5

typedef struct Node {
    int key;
    int value;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct LRUCache {
    int size;
    int capacity;
    Node* head;
    Node* tail;
    Node** cache;
} LRUCache;

Node* createNode(int key, int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

void deleteNode(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
}

void insertNode(Node* node, Node* head) {
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}

LRUCache* createCache(int capacity) {
    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->size = 0;
    cache->capacity = capacity;
    cache->head = createNode(0, 0);
    cache->tail = createNode(0, 0);
    cache->head->next = cache->tail;
    cache->tail->prev = cache->head;
    cache->cache = (Node**)malloc(sizeof(Node*) * capacity);
    for (int i = 0; i < capacity; i++) {
        cache->cache[i] = NULL;
    }
    return cache;
}

void deleteCache(LRUCache* cache) {
    for (int i = 0; i < cache->capacity; i++) {
        if (cache->cache[i] != NULL) {
            free(cache->cache[i]);
        }
    }
    free(cache->cache);
    free(cache->head);
    free(cache->tail);
    free(cache);
}

void moveToHead(Node* node, LRUCache* cache) {
    deleteNode(node);
    insertNode(node, cache->head);
}

void removeFromTail(LRUCache* cache) {
    Node* node = cache->tail->prev;
    deleteNode(node);
    cache->cache[node->key] = NULL;
    cache->size--;
}

int get(LRUCache* cache, int key) {
    if (cache->cache[key] == NULL) {
        return -1;
    }
    Node* node = cache->cache[key];
    moveToHead(node, cache);
    return node->value;
}

void put(LRUCache* cache, int key, int value) {
    if (cache->cache[key] != NULL) {
        Node* node = cache->cache[key];
        node->value = value;
        moveToHead(node, cache);
    } else {
        Node* node = createNode(key, value);
        insertNode(node, cache->head);
        cache->cache[key] = node;
        cache->size++;
        if (cache->size > cache->capacity) {
            removeFromTail(cache);
        }
    }
}

int main() {
    LRUCache* cache = createCache(CACHE_SIZE);
    put(cache, 1, 1);
    put(cache, 2, 2);
    put(cache, 3, 3);
    put(cache, 4, 4);
    put(cache, 5, 5);
    printf("%d\n", get(cache, 1)); // 1
    printf("%d\n", get(cache, 2)); // 2
    put(cache, 6, 6);
    printf("%d\n", get(cache, 3)); // -1
    deleteCache(cache);
    return 0;
}

这个demo实现了LRU缓存淘汰算法，使用双向链表和哈希表来实现。在main函数中，我们创建了一个容量为5的缓存，然后插入了5个键值对。接着，我们查询了键为1和2的值，然后插入了一个新的键值对，最后查询了键为3的值。