实现LRU(用双链表加hash表的方式实现时间复杂度达到O

前言

我们要实现数据库buffer pool中的LRU淘汰算法，当bufferpool满了后，我们要把最前访问的page驱逐(evict)，这个算法也是leecode和CMU 15-441的题目

基本思想

我们如果不强加O(1)可以用vector实现，(删除的时候要移动元素，非常消耗时间)，我们如果要实现O(1)就需要双链表(List默认双链表)和hash表实现，list用来记录每一个bufferpool的page和其对应的pincount，hash表key是page id，value是page的引用或者指针，当我们的某个page的pincount为0说明可以驱逐
我们要 *** 作page对应的pin count的时候，如果只有list只能遍历，但是我们有hash表，可直接定位到对应位置，然后 *** 作当这个pin count等于0的时候就放到list尾部，删除的时候直接删除即可,实现代码如下

#include 
#include 
#include 
//#include 

using namespace std;

int main()
{
    std::list<int> LRUinstance;
    std::map<int, int *> LRUmap;
    
 
    for(int i = 0; i < 10; i++){
        LRUinstance.push_back(i * 3);
        LRUmap[i] = &(LRUinstance.back());
         //cout << "map" << i << " is " << *(LRUmap[i]) << endl;
    }
    
    cout << "link list of 5 node is "<< *(LRUmap[5]) << endl;
    
    //cout<<"Hello World";

    return 0;
}

map的key对应page_id,value对应这个page的pin_count