题目：https://leetcode-cn.com/problems/lru-cache-lcci/

我的方法一：stl::list

步骤

get

使用stl::list来实现，按照顺序遍历list（即先push_back的先遍历到），当list没有对应的key时，返回-1
当list有对应的项时，将该项删除掉，然后通过push_front插入到列表的头上，这样优先级最高；

put

先顺序遍历list，当list没有对应的key时，创建一个新的，通过push_front插入到列表的头上，这样优先级最高；
当list有对应的key时，像get的操作一样，将该项删除掉，然后通过push_front插入到列表的头上，这样优先级最高；
因为有最大容量限制，所以当超过最大容量时，需要将列表最后一个项去掉；所以使用reverse_iterator获得最后一个项；然后通过reverse_iterator获得iterator进行删除
reverse_iterator转iterator的详细说明，请看https://www.jianshu.com/p/8a3cc02bab9a

复杂度

空间复杂度：O(n)
时间复杂度：get和put都是O(n)，因为都需要遍历list

leetcode耗时300ms左右

代码

class LRUCache {
public:
    LRUCache(int capacity) {
        capacity_ = capacity;
    }
    
    int get(int key) {
        for(list<Item>::iterator iter = cache_.begin(); 
            iter != cache_.end(); iter++){
            if(iter->key == key){
                int value = iter->value;
                cache_.erase(iter);
                cache_.push_front(Item(key, value));
                return value;
            }
        }
        return -1;
    }
    
    void put(int key, int value) {
        bool exist = false;
        for(list<Item>::iterator iter = cache_.begin(); 
            iter != cache_.end(); iter++){
            if(iter->key == key) {
                cache_.erase(iter);
                cache_.push_front(Item(key, value));
                exist = true;
                break;
            }
        }

        if(!exist){
            cache_.push_front(Item(key, value));
        }

        if(cache_.size() > capacity_){
            list<Item>::reverse_iterator iter = cache_.rbegin();
            cache_.erase((++iter).base());
        }
    }

private:
    struct Item {
        int key;
        int value;

        Item(int k, int v){
            key = k;
            value = v;
        }
    };

    list<Item> cache_;
    int capacity_ = 0;
};

我的方法二： stl::map + 双向链表

复杂度

get是O(1)，因为map通过key可以直接查到一个Node；并通过Node的双向指针可以在O(1)时间内，完成移到列表头；
put通过是O(1)，因为put也是先查询，再移动到列表头

leetcode耗时76ms，确实比方法一有优化；

边界条件

主要考虑要操作的Node是first_或者last_的情况；

代码

class LRUCache {
public:
    LRUCache(int capacity) {
        capacity_ = capacity;
    }
    
    int get(int key) {
        map<int, Node*>::iterator iter = caches_.find(key);
        if(iter == caches_.end()){
            return -1;
        }

        Node* node = iter->second;
        remove(node);
        insert_to_first(node);
        return node->value;
    }
    
    void put(int key, int value) {
        map<int, Node*>::iterator iter = caches_.find(key);
        if(iter == caches_.end()){
            Node* node = new Node();
            node->key = key;
            node->value = value;
            node->next = 0;
            node->pre = 0;
            insert_to_first(node);
            caches_[key] = node;

            if(caches_.size() > capacity_){
                int key = last_->key;
                caches_.erase(key);
                Node* last = last_;
                remove(last_);
                delete last;
            }
            return;
        }

        Node* node = iter->second;
        node->value = value;
        remove(node);
        insert_to_first(node);
    }

private:
    struct Node {
        int key;
        int value;
        Node* pre;
        Node* next;
    };

    void remove(Node* node){
        if(node == first_){
            //size = 1
            if(first_ == last_){
                first_ = 0;
                last_ = 0;
                return;
            }

            first_ = first_->next;
            first_->pre = 0;
        } else if(node == last_){
            //size = 1
            if(first_ == last_){
                first_ = 0;
                last_ = 0;
                return;
            }

            last_ = last_->pre;
            last_->next = 0;
        } else {
            node->pre->next = node->next;
            node->next->pre = node->pre;
        }
    }

    void insert_to_first(Node* node){
        if(!first_){
            first_ = node;
            node->pre = 0;
            first_->next = 0;
            last_ = node;
            return;
        }

        if(first_ == node){
            return;
        }

        node->next = first_;
        first_->pre = node;
        first_ = node;
    }

    Node* first_ = 0;
    Node* last_ = 0;
    map<int, Node*> caches_;
    int capacity_ = 0;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */