146.LRUキャッシュメカニズム*【バックル】

意味の理解
最近最も少ないLRUバッファメカニズムのクラスを設計する
もんだいぶんせき
STLの使用
hashテーブルunordered_map、デュアルチェーンリスト.
Listはバッファに使用されます.mapは、要素の場所をクエリーするために使用されます.listにkey、valueペア、mapにkey、listの反復器が格納されます.
ダブルチェーンテーブルはヘッドpush_を挿入できますfront,ヘッダpop_を削除front,挿入尾push_back,削除尾pop_back,
その他
0801:get,putがo(1)であることを保証し、クエリーと任意の要素の削除と変更の効率が高く、前後の順序を維持する必要がある.最も速いクエリーはhashであり、最も速い任意の要素の削除は双方向チェーンテーブルであることを知っています.キーをキーワードとして繰り返し、チェーンテーブルを利用する反復器はチェーンテーブルの具体的な位置にすぎない.
リンク

public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    void print() {
        cout << "======" << endl;
        for (auto pair:buffer) {
            cout << pair.first << ' ' << pair.second;
        }
        cout << endl;
    }
    int get(int key) {
        //cout << "get start" << endl;
        //print();
        int val = -1;
        if (dict.count(key)) {
            auto it = dict[key];
            val = it -> second;
            buffer.erase(it);
            buffer.push_front(make_pair(key, val));
            dict[key] = buffer.begin();
        }
        //cout << "get end" << endl;
        //print();
        return val;
    }
    
    void put(int key, int value) {
        //cout << "put start" << endl;
        //print();
        if (dict.count(key)) {
            auto it = dict[key];
            buffer.erase(it);
            buffer.push_front(make_pair(key,value));
            dict[key] = buffer.begin();
        }
        else if (buffer.size() < cap) {
            buffer.push_front(make_pair(key,value));
            dict[key] = buffer.begin();
        }
        else {
            //      key
            int old_key = buffer.back().first;
            //  dict  key
            dict.erase(old_key);
            //  buffer      
            buffer.pop_back();
            //     
            buffer.push_front(make_pair(key,value));
            //  （key，   ） dict
            dict[key]=buffer.begin();
        }
        //cout << "put end" << endl;
        //print();
    }
private:
    list> buffer;
    unordered_map>::iterator> dict;
    int cap = 0;
};