LRU Cache???C++???
?????ygrx ???????[ 2016/9/19 11:48:52 ] ????????.NET ???????????
???????? LRU
????LRU Cache?????Cache???????????????“???????”????????“???????”????????Cache????????????????Cache?е??????????????????????????????????п??????????????????????
????LRU????????????????????????????????????????и???????????£?Cache????????CPU????????????Cache???????Cache??????????棬??????洢?????????б??????????????Cache???????????????????????????????????????????????Cache??????С?
????LRU ??????????
???????
??????????????????????????????????????int???棬??????汾???????????????????á?
???????
?????????????????????????getValue(key)?????д??????putValue(key??value)
????????????????д????????????????????????????????λ??
??????????????????????????????????????????????
????????
??????????????漸????????????????????????????????????η??????????????????????д????????????????????????????????????????????????????????????????
?????????????????????β??????????????????????????????????????????
????Head <===> Node1 <===> Node2 <===> Node3 <===> Near
????OK?????Щ???????????????????????c++??????LRUCache???????????????????????????£??????????????Cache????????
??????????????????????????
????typedef struct _Node_{
????int key; //??
????int value; //????
????struct _Node_ *next; //????????
????struct _Node_ *pre; //????????
????}CacheNode;
???????壺
class LRUCache{
public:
LRUCache(int cache_size=10); //?????????????cache??С?10
~LRUCache();<span style="white-space:pre"> </span> //????????
int getValue(int key); //????
bool putValue(int key??int value); //д???????
void displayNodes(); //????????????????н??
private:
int cache_size_; //cache????
int cache_real_size_; //?????????
CacheNode *p_cache_list_head; //???????
CacheNode *p_cache_list_near; //β??????
void detachNode(CacheNode *node); //??????
void addToFront(CacheNode *node); //?????????????
};
??????????
LRUCache::LRUCache(int cache_size)
{
cache_size_=cache_size;
cache_real_size_=0;
p_cache_list_head=new CacheNode();
p_cache_list_near=new CacheNode();
p_cache_list_head->next=p_cache_list_near;
p_cache_list_head->pre=NULL;
p_cache_list_near->pre=p_cache_list_head;
p_cache_list_near->next=NULL;
}
LRUCache::~LRUCache()
{
CacheNode *p;
p=p_cache_list_head->next;
while(p!=NULL)
{
delete p->pre;
p=p->next;
}
delete p_cache_list_near;
}
void LRUCache::detachNode(CacheNode *node)
{
node->pre->next=node->next;
node->next->pre=node->pre;
}
void LRUCache::addToFront(CacheNode *node)
{
node->next=p_cache_list_head->next;
p_cache_list_head->next->pre=node;
p_cache_list_head->next=node;
node->pre=p_cache_list_head;
}
int LRUCache::getValue(int key)
{
CacheNode *p=p_cache_list_head->next;
while(p->next!=NULL)
{
if(p->key == key) //catch node
{
detachNode(p);
addToFront(p);
return p->value;
}
p=p->next;
}
return -1;
}
bool LRUCache::putValue(int key??int value)
{
CacheNode *p=p_cache_list_head->next;
while(p->next!=NULL)
{
if(p->key == key) //catch node
{
p->value=value;
getValue(key);
return true;
}
p=p->next;
}
if(cache_real_size_ >= cache_size_)
{
cout << "free" <<endl;
p=p_cache_list_near->pre->pre;
delete p->next;
p->next=p_cache_list_near;
p_cache_list_near->pre=p;
}
p=new CacheNode();//(CacheNode *)malloc(sizeof(CacheNode));
if(p==NULL)
return false;
addToFront(p);
p->key=key;
p->value=value;
cache_real_size_++;
return true;
}
void LRUCache::displayNodes()
{
CacheNode *p=p_cache_list_head->next;
while(p->next!=NULL)
{
cout << " Key : " << p->key << " Value : " << p->value << endl;
p=p->next;
}
cout << endl;
}
????????????
?????????????????????????????????int??????????????????????????????????????????O(n)?????????hash?????????????????????????????????????????????????
??????
???·???
??????????????????
2023/3/23 14:23:39???д?ò??????????
2023/3/22 16:17:39????????????????????Щ??
2022/6/14 16:14:27??????????????????????????
2021/10/18 15:37:44???????????????
2021/9/17 15:19:29???·???????·
2021/9/14 15:42:25?????????????
2021/5/28 17:25:47??????APP??????????
2021/5/8 17:01:11