每天一道场景题

带过期时间的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);
                }
            }
        }
    }

};