数据结构LRUCache(Least Recently Used – 最近最少使用缓存)
题目要求:
设计一个数据结构,实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作: get 和 put。
int get(int key) – 如果key已存在,则返回key对应的值value(始终大于0);如果key不存在,则返回-1。
void put(int key, int value) – 如果key不存在,将value插入;如果key已存在,则使用value替换原先已经存在的值。如果容量达到了限制,LRU Cache需要在插入新元素之前,将最近最少使用的元素删除。
请特别注意“使用”的定义:新插入或获取key视为被使用一次;而将已经存在的值替换更新,不算被使用。
限制:请在O(1)的时间复杂度内完成上述2个操作。
输入描述
第一行读入一个整数n,表示LRU Cache的容量限制。 从第二行开始一直到文件末尾,每1行代表1个操作。
如果每行的第1个字符是p,则该字符后面会跟随2个整数,表示put操作的key和value。
如果每行的第1个字符是g,则该字符后面会跟随1个整数,表示get操作的key。
输出描述
按照输入中get操作出现的顺序,按行输出get操作的返回结果。
示例:
输入:
2
p 1 1
p 2 2
g 1
p 2 102
p 3 3
g 1
g 2
g 3
输出:
1
1
-1
3
解题思路:
put(key,value)在O(1)的时间内完成,可以使STD中的一个容器:双端链表list,由于list没有实现[]操作符重载,为了实现O(1)内查找,可以使用另一个容器:ordered_map。每次“使用”元素的时候,就将该元素调整到链表的首部,这样当超出容量的时候,直接删除链表末尾的元素及其在map中对应的值。
list介绍:
list是一种序列式容器。
list容器完成的功能实际上和双向链表极其相似,list中的数据元素是通过链表指针串连成逻辑意义上的线性表,也就是list也具有链表的主要优点,即:在链表的任一位置进行元素的插入、删除操作都是快速的。
由于list元素节点并不要求在一段连续的内存中,显然在list中是不支持快速随机存取的,因此对于迭代器,只能通过“++”或“–”操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的操作,这点,是与vector等不同的地方。
begin() #返回一个指向容器起始位置的iterator
rbegin() #返回list中末尾的迭代器
end() #返回list末端下一位置的iterator
push_back() #插入元素到list的末尾
push_front() #从list的头部插入元素
empty() #判断list是否为空
resize() #调用resize(n)将list的长度改为只容纳n个元素,超出的元素将被删除,如果需要扩展那么调用默认构造函数T()将元素加到list末端。如果调用resize(n,val),则扩展元素要调用构造函数T(val)函数进行元素构造,其余部分相同
clear() #清空list中的所有元素
front() #返回list容器中的头部元素引用
back() #返回list容器的最后一个元素的引用
pop_back() #删除链表的末尾元素
pop_front() #删除链表的首部元素
swap() #交换两个链表,list1,swap(list2)和swap(list1,list2)都可以实现list1和list2的交换
splice() #实现链表拼接
/**
将源list的内容部分或全部元素删除,拼插入到目的list,有三种函数声明
dest_list.splice(iterator position,list<T,Allocator>& source_list) #将source_list的所有元素剪接到dest_list的position的后面
dest_list.splice(iterator position,list<T,Allocator>& source_list, iterator it)#将source_list的it位置处的元素剪接到dest_list的position的后面
dest_list.splice(iterator position,list<T,Allocator>& source_list, iterator first,iterator last)#将source_list的first到last的元素剪接到dest_list的position后面
##测试
#include<list>
#include <iostream>
using namespace std;
int main()
{
list<int>list1,list2;
for(int i=1;i<=4;i++) {
list1.push_back(i);
list2.push_back(i+10);
}
// list1 1 2 3 4
// list2 11 12 13 14
list<int>::iterator it=list1.begin();
it++;
list1.splice(it,list2);//1 11 12 13 14 2 3 4
if(list2.empty()) cout<<"list2 is empty"<<endl;
list2.splice(list2.begin(),list1,it);
cout<<*it<<" "<<endl;
/*
list1 1 11 12 13 14 3 4
list2 2
这里的it的值还是2,但是指向的已经是list2中的了
*/
it=list1.begin();
advance(it,3);//advance 的意思是增加的意思,就是相当于 it=it+3;这里指向13
list1.splice(list1.begin(),list1,it,list1.end()); //13 14 3 4 1 11 12 可以发现it到list1.end()被剪贴到list1.begin()前面了
for(list<int>::iterator it=list1.begin();it!=list1.end();++it) cout<<*it<<" ";
cout<<endl;
for(list<int>::iterator it=list2.begin();it!=list2.end();++it) cout<<*it<<" ";
cout<<endl;
list<pair<int,int> > list3;
for(i=1;i<=3;i++)
list3.push_back(make_pair(i,i+3));
list<pair<int,int> >::iterator iter=list3.begin();
cout<<iter->first<<" "<<iter->second<<endl;
return 0;
}
##结果
list2 is empty
2
13 14 3 4 1 11 12
2
1 4
**/
unordered_map介绍
1、与map的区别
map的内部实现是红黑树(红黑树是一种严格的平衡二叉搜索树),因此该容器具有自动排序的功能,map内部的所有元素都是有序的。对map的所有操作都是基于红黑树,因此很多操作都可以在O(logn)的时间内完成,map适用于对元素顺序有要求的场合。
缺点:由于红黑树的节点需要保存节点指针和数据域,所以红黑树的空间开销比较大。
unorder_map的内部实现是哈希表,并且使用开放链表寻址法解决冲突问题,因此元素的查找速度可以达到O(1),适用于对于查找操作有较高才做的场合。
缺点:哈希表的时间复杂度比较高。
2、使用
find(key) #返回key所对应的迭代器,如果该迭代器与end()相等,说明map中不存在key。
count(key) #返回key在map中出现的次数,如果为0说明key不在map中
iterator erase(const_iterator pos ) #移除map中pos处键值对
iterator erase(const_iterator first, const_iterator last );#移除map中first到last的键值对
size_type erase(const key_type& key )#移除特定key的键值对。
begin() #返回指向容器起始位置的迭代器
end() #返回指向容器末尾位置的迭代器
cbegin() #返回指向容器起始位置的常迭代器(const_iterator)
cend() #返回指向容器末尾位置的常迭代器
insert() #插入元素
/**
unordered_map的迭代器是一个指针,指向这个元素,通过迭代器来取得它的值。
unordered_map<Key,T>::iterator it;
(*it).first; // the key value (of type Key)
(*it).second; // the mapped value (of type T)
(*it); // the "element value" (of type pair<const Key,T>)
it->first; // 同 (*it).first (the key value)
it->second; // 同(*it).second (the mapped value)
**/
实现代码:
#include <iostream>
#include <unordered_map>
#include <list>
#include <string>
#include <sstream>
using namespace std;
class LRUCache{
private:
int cap;
list<pair<int,int>> L;
unordered_map<int,list<pair<int,int>>::iterator> m;
public:
LRUCache(int capacity){
cap=capacity;
}
int get(int key){
auto it=m.find(key);
if(it == m.end()) return -1;
L.splice(L.begin(),L,it->second);
return it->second->second;
}
void put(int key,int value){
auto it=m.find(key);
if(it != m.end()) {
it->second->second=value;
}else{
L.push_front(make_pair(key,value));
m[key]=L.begin();
}
if(m.size() > cap){
int k=L.rbegin()->first;
L.pop_back();
m.erase(k);
}
}
};
int main(){
int n;
cin>>n;
LRUCache L(n);
string cmd;
char commond;
while(getline(cin,cmd)){
istringstream iss(cmd);
iss>>commond;
if(commond=='p'){
int key,val;
iss>>key>>val;
L.put(key,val);
}else if(commond=='g'){
int key;
iss>>key;
int val=L.get(key);
cout<<val<<endl;
}
}
return 0;
}
注意
按行读取输入,每一行的输入通过getline(cin,cmd)读入到cmd中,然后通过istringstream iss(cmd)构造一个字符串输入流,然后从中解析出字符、整数。