使用C++简单实现LRU缓存_c++简单的使用lru

首先是malloc:

  可能是C语言写习惯的，导致在C++进行内存分配的时候我也习惯用malloc，C和C++混用很可能就会出bug！
  在给struct LRUCache{};初始化时，由于指针会指向一块内存，指针本身也是要占用内存的，但指针指向的地方还没有分配内存呢，所以就需要又malloc 。我就是少malloc，结果程序老是运行不下去。。。

接着是map:

  我在struct LRUCache{};放了一个map<int, ListNode*> mp; mp用来存索引key和映射ListNode的指针.
  如果是用malloc初始化struct LRUCache{};那么又需要给map初始化，因为malloc只是申请一块内存，不会初始化map对应的内存。使用new 除了malloc内存，还会调用默认的构造初始化函数 ，所以最好还是用new比较省事。

malloc和new的区别:

(1)malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。
(2)new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。
(3)使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计算，而malloc则需要显式地指出所需内存的尺寸。

  下面是代码，用了get(key)获取数据，put(key, value)存放数据。代码还没有完善，只是简单的实现，后面有时间会进行修改。（其实可以把struct LRUCache{};换成一个类，这样比较好。。。）
代码如下：

#include<iostream>
#include<stdlib.h> 
#include<map>
using namespace std;
struct ListNode{
	int key;
	int value;
	ListNode *pre,*next;//指针 
	ListNode (int key1,int value1){
		key=key1;
		value=value1;
		pre=NULL;
		next=NULL;
	}
};
struct LRUCache{
	int Captacity;
	map<int,ListNode*> m;
	ListNode *head,*tail;//指针 
	LRUCache(int captacity){
		Captacity= captacity;
		head=new ListNode(0,0); 
    	tail=new ListNode(0,0); 
	}
}*cache;
LRUCache *Constructor(int capacity){//初始化 
    LRUCache *cache=new LRUCache(capacity); 
	cache->head->next=cache->tail;
	cache->tail->pre=cache->head;
	return cache;
}
void removeNode(ListNode *node){    //移除 
	node->pre->next=node->next;
	node->next->pre=node->pre;
}
void addNode(ListNode *node){//添加元素到表头 
	node->next=cache->head->next;
	node->pre=cache->head;
	cache->head->next->pre=node;
	cache->head->next=node;
} 
void moveToHead(ListNode *node) {//移动到表头 
	removeNode(node); 
	addNode(node);
}
void popTail(){ //删除表尾 
	ListNode *res = cache->tail->pre;
	removeNode(res);
}
int get(int key){
	map<int,ListNode*>::iterator it=cache->m.find(key);
	if(it==cache->m.end()){//如果不存在 
		return -1;
	}
	ListNode *node = it->second;
	moveToHead(node);
	return node->value; 
}
void put(int key,int value){
	map<int,ListNode*>::iterator it=cache->m.find(key);
	if(it==cache->m.end()){//如果不存在 
		ListNode * NewNode = new ListNode(key,value);
		if(cache->m.size()==cache->Captacity){//如果满了 
			cache->m.erase(cache->tail->pre->key);//从map表中删除最后一个 
			cache->m[key]= NewNode;//从map表中加上新的 
			popTail();//删除 cache最后一个 
			addNode(NewNode);//把新的移到最前面 
		}else{
			cache->m[key]= NewNode;
			addNode(NewNode);
		}
	} else{//如果存在 
		it->second->value=value;//更新值 
		moveToHead(it->second);
	}
}
int main(){
	cache=Constructor(3);
	put(1,1);
	put(2,2);
	put(3,3);
	//顺序：3，2，1 
	cout<<get(1)<<endl;//1
	// 顺序：1，3，2 
	put(4,4);
	// 顺序：4，1，3 
	cout<<get(2)<<endl;//-1
	put(5,5);
	// 顺序：5，4，1
	cout<<get(3)<<endl;//-1
	cout<<get(4)<<endl;//4
	cout<<get(5)<<endl;//5
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

  如果哪里写得不够好或者是大家有不同看法的欢迎评论！我会看情况进行更改。