【数据结构】LRU Cache

LRUCache

1.
LRUCache是一种缓存的替换技术，在CPU和main memory之间根据计算机的局部性原理，往往会采用SRAM技术来构建CPU和主存之间的高速缓存，DRAM(dynamic random access memory)用于构建主存，LRUCache这种缓存替换技术常被应用于高速缓存中缓存行的替换，我们接下来就要模拟实现LRUCache这种数据结构。

LRU 缓存

2.
LRUCache主要实现两个接口，一个是get，一个是put，实现get和put有人可能会想到用一个哈希表，因为哈希表查找和插入数据的时间复杂度刚好是O(1)，这当然没问题，但是你如何实现LRU呢？
我们如何每次在数据满了之后，删除的数据是最近没有访问的数据呢？这该怎么保证？实际上要保证LRU方式数据的删除和更新，使用一个链表是最合适不过的了，如果我们访问了某一个数据，那就把这个数据从链表中的某一位置移动到链表头去，这样的话，每次最近访问的数据都会在链表的头部，而长时间不访问的数据就会在链表尾部放着，那么当数据结构中数据满了的时候，我们只要将链表尾部的数据删除即可，然后将新到来的数据重新插入到数据结构中，这样就可以实现LRU了。
但是现在还有一个问题，我们是将数据存储到链表当中了，但是当涉及到更新操作时，如何快速找到特定的pair结点，将他的value值更改呢？如果遍历链表来更新的话，那么这个操作就不是O(1)了而是O(N)，所以如何找到特定结点成为了破局的关键！我们让哈希表存储的pair对中的value值为链表的迭代器，这样一来就完美设计出一个高效的LRUCache结构了。
在查找某一结点时，我们直接用哈希表就可以实现O(1)的快速查找，只要能够查找到结点，那么get操作，put时可能的更新操作，这些就都是O(1)时间复杂度了。
在实现代码时，如果我们访问了某个结点，那么就要把这个结点转移到链表头部，转移的操作可以使用erase+push_front，但这样会涉及到迭代器失效的问题，因为哈希表中存储的迭代器指向原来的结点，结点被你erase了，那么迭代器就会失效，我们还需要自己重新更改哈希表中存储的迭代器，这样有点麻烦，同时删除结点其实会遍历链表，这样的操作也不是很高效，那么这时候STL还给我们提供了一个接口splice，意为拼接，可以将某一位置的迭代器指向的结点，拼接到链表中的任意位置，拼接的原理其实就是通过更改指针的指向来完成结点的转移，这样就可以不用释放结点和重新申请结点的操作了，效率就会高一些。