在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:

分析

这道题目,没做对很大程度上是因为没有理解题意。题目要求要求每次删除最久没有操作过的删去。于是这就是一个队列,每次操作了哪个元素,就将那个元素提到队列最前,每次删除时删除队尾就可以了。至于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():反转容器中元素顺序

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注