项目特点本次我们所设计的项目有一个很明显的特点数据结构稳定 需求逐步增强这也正是数据结构/算法工程化类的项目的特点我们列举一些常见的项目数据结构 / 算法工程化LRU / LFU / 队列 / 内存池缓存系统线程池任务调度器系统模块设计日志系统配置系统网络请求模块数据库连接池后端 / 中间件RPC框架KV存储消息队列像这种我一般会采取一个分层需求演进 自顶向下设计 自底向上实现的一个设计思路在讲思路之前我也将不适用的一些项目说清楚如下主要影响还是需求一次性强约束问题数学证明竞赛题固定算法题LeetCodeUI / 产品设计类项目用户体验驱动前端页面交互设计APP设计AI实验论文实验模型调参不稳定需求探索类项目系统设计思路分层需求演进开发层级的不断演进也就对应了需求的层级演进确定当前开发层级1. 基本功能2. 性能要求3. 类型扩展4. 内存安全5. 线程安全6. 接口统一从基本功能到接口统一首先我们要明确自己当前的需求层级再进行下一步我们从基本功能与性能要求开始。基本功能与性能要求首先我们最要实现一个LRU Cache。支持 put(key, value)存和 get(key)取。容量固定容量满时淘汰最久未使用的数据。1.核心操作是要put插入或更新数据get查询数据淘汰删除最久未使用的数据访问更新被 get 或 put 的数据变成最近使用2.性能要求是get 要快put 要快最好都是 O(1)3.选择合适的数据结构或技术哈希表双向链表unordered_map 双向链表4.对于数据结构里的数据关系怎么画哈希表key - 双向链表节点地址双向链表dummyHead_ - 最近使用节点 - ... - 最久未使用节点 - dummyTail_5.设计类成员-根据核心需求数据结构写相应的粗int capacity_;容量std::unordered_mapint, Node* cache_;Node* dummyHead_;Node* dummyTail_;节点struct Node{int key;int value;Node* prev;Node* next;};6.public接口-根据核心操作写LRU_Cache(int capacity);int get(int key);void put(int key, int value);7.private辅助函数-根据数据结构与关系写细void addToHead(Node* node);void removeNode(Node* node);void moveToHead(Node* node);Node* removeTail();8.伪代码-这里主要还是public接口需要写比如get如果 key 不存在返回 -1如果 key 存在找到节点移动到最近使用位置返回 value9.具体的C代码完成到这里你就可以进入第二个层级了类型扩展版这一层的需求是我要从 int-int LRU 升级成任意 Key-Value LRU。不能仅仅是int类型的缓存不应该只能存 int - int。应该支持 Key - Value。这一层比较简单有些环节就可以省略了3.技术templatetypename Key, typename Value5.修改类成员节点要改变Key key_;Value value_;std::unordered_mapKey, NodePtr nodeMap_;内存安全这一层我们的需求是节点内存应该自动管理减少手动 new/delete避免忘记 delete。同样3.技术std::shared_ptrstd::weak_ptr5.修改类成员std::weak_ptrLruNodeKey, Value prev_;std::shared_ptrLruNodeKey, Value next_;线程安全这次我们的需求增加为我要支持多个线程同时访问缓存多个线程同时 get / put / remove 时缓存结构不能乱。3.技术std::mutexstd::lock_guard5.设计类成员std::mutex mutex_;注意这里类成员变成设计了需要写相应的代码了10.翻译成代码在put/get/remove里加std::lock_guardstd::mutex lock(mutex_);接口统一最后需求是以后可能有 LRU、LFU、FIFO不想每种缓存对外接口都乱写不同缓存策略应该有统一接口。3.技术抽象基类 纯虚函数5.类成员6.public接口virtual void put(Key key, Value value) 0;virtual bool get(Key key, Value value) 0;virtual Value get(Key key) 0;10.代码class KLruCache : public KICachePolicyKey, Value//继承总结确定当前开发层级1. 基本功能2. 性能要求3. 类型扩展4. 内存安全5. 线程安全6. 接口统一不同的开发层级都需要思考以下步骤第 1 步写当前层级的需求第 2 步确定核心操作第 3 步确定性能要求第 4 步选择数据结构或语言机制第 5 步画数据关系第 6 步设计类成员第 7 步设计 public 接口第 8 步设计 private 辅助函数第 9 步写伪代码第 10 步翻译成 C 代码Thank you!