用一个结构表示Key 和 Value:
class LRUCacheNode
{
friend LRUCache;
int mKey, mVal;
LRUCacheNode* next;
LRUCacheNode* pre;
LRUCacheNode(int iK, int iV):mKey(iK), mVal(iV), next(NULL), pre(NULL){};
};
用map 或 hash表示<key, LRUCacheNode*>, 用于快速查找key对应的value。
用一个LRUCacheNode 组成的双向链表来维护key和value的访问先后顺序.
实现set和get的时间复杂度都是O(1).
代码如下:
class LRUCache{ class LRUCacheNode { friend LRUCache; int mKey, mVal; LRUCacheNode* next; LRUCacheNode* pre; LRUCacheNode(int iK, int iV):mKey(iK), mVal(iV), next(NULL), pre(NULL){}; }; //use map or unorder_map provde the quick check the value of the key. map<int/*key*/, LRUCacheNode*> mKeyMap; //use the dinay list to matain the squence of the visit time. LRUCacheNode head; LRUCacheNode tail; int mC; int mNum; public: LRUCache(int capacity):head(LRUCacheNode(-1, -1)),tail(LRUCacheNode(-2, -2)) { mC = capacity; mNum = 0; mKeyMap.clear(); head.next = &tail; tail.pre = &head; } int get(int key) { if(mKeyMap.find(key) == mKeyMap.end()) { return -1; } else { LRUCacheNode* lNode = mKeyMap[key]; hDeleteNodeFromDequeue(lNode); hMoveNodeToHead(lNode); return lNode->mVal; } } void set(int key, int value) { if(mKeyMap.find(key) == mKeyMap.end()) { if(mNum == mC) { LRUCacheNode* ldeteNode = hRemoveNodeFromTail(); mKeyMap.erase(ldeteNode->mKey); delete ldeteNode; mNum --; } LRUCacheNode* lNode = new LRUCacheNode(key, value); hMoveNodeToHead(lNode); mKeyMap[key] = lNode; mNum++; } else { LRUCacheNode* lNode = mKeyMap[key]; hDeleteNodeFromDequeue(lNode); hMoveNodeToHead(lNode); lNode->mVal = value; } } private: void hDeleteNodeFromDequeue(LRUCacheNode* iNode) { if(iNode == NULL) return; iNode->next->pre = iNode->pre; iNode->pre->next = iNode->next; } void hMoveNodeToHead(LRUCacheNode* iNode) { if(iNode == NULL) return; iNode->next = head.next; iNode->pre = &head; head.next = iNode; iNode->next->pre = iNode; } LRUCacheNode* hRemoveNodeFromTail() { LRUCacheNode* lDeNode = tail.pre; tail.pre = lDeNode->pre; lDeNode->pre->next = &tail; return lDeNode; } };