LeetCode_146: LRUCache 使用STL-list

在LeetCode的题目中，考察list操作的比较少，所以这道题也算是经典了，只有17%的通过率也足以说明问题。STL的list模板是一个环形双链表，其支持链表的基本操作，并且封装了reverse、sort、merge、splice等算法，为链表的操作提供许多遍历，这篇博客会根据在STL源码分析中的内容进行简单介绍。

题目

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get andput.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

分析

这道题目，没做对很大程度上是因为没有理解题意。题目要求要求每次删除最久没有操作过的删去。于是这就是一个队列，每次操作了哪个元素，就将那个元素提到队列最前，每次删除时删除队尾就可以了。至于O(1)操作时间，则完全可以借助Hash表来实现。

链表

STL的LIST是一个环状的双向链表。关于LIST的实现，最好参考STL源码分析来理解。这里介绍list中封装的几个方法：splice、sort。还有一个merge算法，merge的输入要求连个链表都是排序好的。

void sort():容器内所有元素排序，默认是升序

template<class Pred>void sort(Pred pr):容器内所有元素根据预断定函数pr排序

void swap(list& str):两list容器交换功能

void unique():容器内相邻元素若有重复的，则仅保留一个

void splice(iterator it,list& li):队列合并函数，队列li所有函数插入迭代指针it前，x变成空队列

void splice(iterator it,list& li,iterator first):队列li中移走[first,end)间元素插入迭代指针it前

void splice(iterator it,list& li，iterator first,iterator last):x中移走[first,last)间元素插入迭代器指针it前

void reverse():反转容器中元素顺序

代码

class LRUCache {
	using ListIt = list<pair<int, int>>::iterator;
public:
	LRUCache(int capacity) {
		size = capacity;
	}

	int get(int key) {
		auto it = hash.find(key);
		if (it == hash.end()){
			return -1;
		}
		cache.splice(cache.begin(), cache, it->second); // 将一个元素提前
		return it->second->second;
	}

	void put(int key, int value) {
		auto it = hash.find(key);
		if (it != hash.end()){
			it->second->second = value;
			return cache.splice(cache.begin(), cache, it->second);
		}
		cache.insert(cache.begin(), {key, value});
		hash[key] = cache.begin();
		if (cache.size() > size){
			hash.erase(cache.back().first);
			cache.pop_back();
		}
	}
private:
	unordered_map<int, ListIt> hash;
	list<pair<int, int>> cache;
	int size;
};