带过期时间的LRU实现（更新时不改变expire_time）put 的时候遍历找过期的，也可以从list->head往后找，这里应该优化不成O(1)吧？#include <iostream>#include <unordered_map>#include <time.h>using namespace std;const int ttl=10;class LRUCache{public:    struct DLinkNode    {        int key,value;        time_t expire_time;        DLinkNode *prev,*next;        DLinkNode(int key,int value):key(key),value(value),expire_time(0),prev(nullptr),next(nullptr){}    };    int _cap;    unordered_map<int,DLinkNode*> _cache;    DLinkNode *_head,*_tail;    LRUCache(int capacity):_cap(capacity){        _head=new DLinkNode(0,0);        _tail=new DLinkNode(0,0);        _head->next=_tail;        _tail->prev=_head;    }    void removeNode(DLinkNode* tmp){        tmp->prev->next=tmp->next;        tmp->next->prev=tmp->prev;        return ;    }    void addToLast(DLinkNode* tmp){        DLinkNode * pre=_tail->prev;        pre->next=tmp;        tmp->next=_tail;        _tail->prev=tmp;        tmp->prev=pre;        return ;    }    DLinkNode* removeHead(){        DLinkNode* tmp=_head->next;        _head->next=tmp->next;        tmp->next->prev=_head;        return tmp;    }    int get(int key){        if(_cache.find(key)==_cache.end()) return -1;        else{            DLinkNode* tmp=_cache[key];            time_t cur_time;            cur_time=time(nullptr);            if(difftime(cur_time,tmp->expire_time)<=0){                //过期                removeNode(tmp);//链表删                _cache.erase(key);//hash删                return -1;            }else{                //这里也可以重新计算expire_time = cur_time + ttl                removeNode(tmp);                addToLast(tmp);                return tmp->value;            }        }    }    void put(int key,int value){        if(_cache.find(key)!=_cache.end()){            DLinkNode* tmp=_cache[key];            removeNode(tmp);            addToLast(tmp);            //更新值，这里也可以重新计算expire_time = cur_time + ttl            tmp->value=value;            return ;        }else{            DLinkNode* tmp=new DLinkNode(key,value);            time_t cur_time;            cur_time=time(nullptr);            tmp->expire_time=cur_time+ttl;            addToLast(tmp);            _cache[key]=tmp;            bool is_expire=false;            if(_cache.size()>=_cap){                //找第一个过期的删除，O(N)                unordered_map<int,DLinkNode*>::iterator it;                for(;it!=_cache.end();it++){                    if(difftime(it->second->expire_time,cur_time)>=0){                        is_expire=true;                        break;                    }                }                if(is_expire){                    //找到啦                    DLinkNode* tmp=it->second;                    removeNode(tmp);                    _cache.erase(tmp->key);                }else{                    //都没过期                    DLinkNode* tmp=removeHead();                    _cache.erase(tmp->key);                }            }        }    }};