本期我们进入实际操作环节我采用Windows系统用VScode ssh远程连接Linux服务器进行操作。因为本人一直跑的是python的项目配置的anaconda环境这里conda deactivate退出。新建cache文件夹 并cd cache 下一步搭建基本的代码框架。基本的项目框架首先我们需要三个文件夹include放头文件src放源代码文件build放编译生成的中间文件以及可执行程序命令mkdir include src build结构cache├── include类的声明函数声明结构体定义├── src真正执行的 C 代码函数实现main 函数└── build编译垃圾桶/编译产物目录不把它和源代码混在一起接下来需要创建一个空文件CMakeLists.txtC 项目的“编译说明书”这个文件是给 CMake 用的。CMake 是 C 项目常用的构建工具它负责告诉编译器:项目叫什么用哪个 C 标准头文件在哪里源代码在哪里?最后生成什么可执行文件?命令touch CMakeLists.txt最后就是项目核心的LRUCache.h以及main.cpp先从最基础的LRU淘汰策略做起命令touch include/LRUCache.h touch src/main.cpp总结一下CMakeLists.txt 编译说明书include/LRUCache.h LRU缓存类的头文件src/main.cpp 程序入口和测试代码build 编译生成文件存放处框架搭好之后开始编辑内容先写C项目的编译配置文件因为我们后面不会直接手动写很长的g编译命令而是用 CMake 来管理项目。没有CMakeLists.txtCMake 就不知道怎么编译你的项目。cat CMakeLists.txt EOFcmake_minimum_required(VERSION 3.10)##版本号project(kama_cache)##项目名称set(CMAKE_CXX_STANDARD 17)##C17标准set(CMAKE_CXX_STANDARD_REQUIRED ON)include_directories(include)##头文件放进includeadd_executable(kama_cachesrc/main.cpp)##把src/main.cpp编译成一个可执行程序程序名字叫kama_cacheEOF接下来在main里编译一个简单的测试程序#include iostreamint main(){std::cout Kama Cache project is running! std::endl;return 0;}##std::cout输出工具将右边的内容放到左边输出流里 std::endl换行下一步执行程序cd buildcmake ..让 CMake 去上一级目录..找CMakeLists.txt然后根据它生成 Makefile其中CMakeLists.txt 是我们写的“项目编译说明书”cmake .. 根据说明书生成 Makefilemake 根据 Makefile 真正编译代码这里已经生成了可执行文件下一步直接在目录下./kama_cache。[ 50%] Building CXX object CMakeFiles/kama_cache.dir/src/main.cpp.o先把 C 代码翻译成机器更接近能执行的中间文件[100%] Linking CXX executable kama_cache把编译好的中间文件和需要的库组合起来变成真正能运行的程序[100%] Built target kama_cache这里涉及编译器原理放在下一节成功再复习一下流程。写源代码↓告诉 CMake 项目怎么编译↓在 build 文件夹里生成编译文件↓真正编译生成可执行程序↓运行程序最简单的缓存项目LRUcache基础架构int key int value 哈希表 双向链表#ifndef LRU_CACHE_H #define LRU_CACHE_H #include unordered_map //包含哈希表 class LRU_Cache//定义LRU_Cache类 { private: struct Node//定义双向链表节点类 { int key; int value; Node *prev; Node *next; Node (int k, int v) :key(k), value(v), prev(nullptr), next(nullptr) {} }; //; private : int capacity_; std::unordered_mapint, Node * cache_;//哈希表根据key快速找到节点 Node *dummyHead_;//虚拟节点指向头尾节点 Node *dummyTail_; public: LRU_Cache(int capacity)//建立一个空的双向链表函数 : capacity_(capacity) { dummyHead_ new Node(0, 0); dummyTail_ new Node(0, 0); dummyHead_-next dummyTail_; dummyTail_-prev dummyHead_; } ~LRU_Cache()//释放内存 { Node *current dummyHead_; while (current ! nullptr) { Node *nextNode current-next; delete current; current nextNode; } } }; #endifLRUCache 是一个缓存类。它里面有1. Node 节点每个节点保存 key、value、prev、next。2. capacity_缓存最大容量。3. cache_哈希表用 key 快速找到 Node 节点。4. dummyHead_ 和 dummyTail_双向链表的虚拟头节点和虚拟尾节点。写代码需注意class / struct 的大括号后面要加分号。函数的大括号后面一般不加分号。Node(int k, int v) 是构造函数用来初始化节点。std::unordered_mapint, Node* cache_ 是哈希表int key - Node* 节点地址。LRUCache(int capacity) : capacity_(capacity)表示创建缓存时把容量保存到成员变量 capacity_。读取与写入函数在public里加入get(int key)和put(int key , int value)int get(int key) //缓存的查询函数{if(cache_.find(key)cache_.end()){return -1;}Node* node cache_[key];moveToHead(node);return node-value;}void put(int key, int value) //缓存的插入函数{if(cache_.find(key)!cache_.end())//key已经存在{Node *node cache_[key];//cache_[]是哈希表的访问方式返回的是Node*类型node-value value;moveToHead(node);}if(cache_.size()capacity_)//key不存在容量已满{Node *tailNode removeTail();cache_.erase(tailNode-key);//从哈希表中删除delete tailNode;}Node *newNode new Node(key, value);cache_[key] newNode;//插入哈希表addToHead(newNode);//插入双向链表头部}简单的测试在main.cpp中写一段测试代码测试这几个功能put 插入数据get 查询数据访问后移动到最近使用容量满后淘汰最久未使用数据另外重点解释一下哈希表里的链表与我们自己写的LRU双向链表要区分开哈希表正常存放数据他解决哈希冲突与我们无关是标准库的事但是内部每个节点能够快速指向我们写的LRU双向链表上的节点地址所以我写了put(1, 100); put(2, 200);不管哈希表怎么存我们LRU双向链表上都是前后两个点。#include iostream #include LRUCache.h int main() { LRU_Cache cache(2); // 创建一个容量为2的LRU缓存 cache.put(1, 100); // 缓存中添加键值对 (1, 100) cache.put(2, 200); // 缓存中添加键值对 (2, 200) std::cout get(1): cache.get(1) std::endl; // 输出: 100键1存在于缓存中 cache.put(3, 300); // 缓存容量已满移除最久未使用的键2 std::cout get(2): cache.get(2) std::endl; std::cout get(3): cache.get(3) std::endl; return 0; }std::cout get(1): cache.get(1) std::endl;//std::cout是标准输出对象C里允许连续输出这句话拆成三段std::cout get(1): ;std::cout cache.get(1);std::cout std::endl; //换行依旧是cd build make(CMakeLists.txt 是编译说明; cmake .. 生成 Makefile; make 根据 Makefile 真正编译代码) ./kama_cache(运行当前目录下的可执行文件)成功编译器既然这里提到编译器就顺便解释编译器。等待补充中。。。