这题应该见的不少了，写写记录一下。
实现该功能分析:
(1) O(1) 时间完成查找，那除了 hash 别无选择。
(2) LRU 最近最少使用算法，为了方便数据的淘汰。需要对最近访问的数据放未访问数据之前。
用双向链表实现即可。(通常情况下，双向链表读取、插入的时间复杂度都是O(n), 但是如果知道插入位置，则可以实现O(1)实现。)
实现: hash存key对应的数据在双向链表中的位置，就可以完成该功能。
具体代码:
1 #include <iostream> 2 #include <list> //std::list双向链表实现 3 #include <map> 4 5 const int MAX_VALUE_LEN = 32; 6 const int MAX_ELEMENT_NUM = 3; 7 8 struct CacheNode{ 9 int key; 10 int len; 11 char data[MAX_VALUE_LEN]; 12 }; 13 14 class LRU{ 15 public: 16 //默认10个原始 17 LRU(int max_num = MAX_ELEMENT_NUM); 18 ~LRU(); 19 20 //数据获取 21 bool get(const int key, char *data, int &len); 22 23 //新增数据 24 bool set(const int key, const char* data, const int len); 25 26 //打印数据 27 void print_list(); 28 private: 29 30 //更新节点的链接 31 //访问元素后, 需要将元素放置在list 头部 32 int update_node_link(const int key); 33 34 int _max_num; 35 std::list<CacheNode*> _list; 36 std::map<int, std::list<CacheNode*>::iterator> _map; 37 };
