C++LRUアルゴリズムの実装

LRUアルゴリズム
LRUはLeast Recently Usedの略で、最近最も少なく使用されており、ページ置換アルゴリズムでよく使われ、仮想ページストレージ管理サービスである.LRUアルゴリズムの提案は,長い間使用されていないページが今後長い間使用されない可能性が高いという事実に基づいている.したがって、スワップするたびに、最近最も長く使用されていないページを見つけてメモリを呼び出すだけです.これがLRUアルゴリズムのすべてです.
インプリメンテーション
双方向チェーンテーブルとハッシュテーブルを使用してLRUアルゴリズムを実現

双方向チェーンテーブルはkey-valueを保存するために使用され、キューヘッダの要素は最近アクセスされた要素を表し、キューテールの要素は最近最も長く使用されていない要素

を表す.

ハッシュテーブルは、双方向チェーンテーブルにおけるkeyからkeyに対応するノードの位置へのマッピング

を提供する.
get操作とput操作を実現

get:keyを入力valueを取得し、対応するノードを双方向チェーンテーブルヘッダ(このノードは最近アクセスされたノードであるため)

に移動する.

put:key-valueペアが転送され、3つの状況に分けて処理されます.

keyが既に存在する場合は、まず対応するノードを削除し、key-valueを双方向チェーンテーブルヘッダ(このノードは最近アクセスされたノードであるため)

に挿入する.

双方向チェーンテーブルの長さが最大要素の個数以上である場合、双方向チェーンテーブルキューの末尾要素(最近最も長く使用されていない要素)を削除し、key-valueを双方向チェーンテーブルヘッダ

に挿入する.

上記の2つの条件が満たされない場合は、key-valueを双方向チェーンテーブルヘッダ

に挿入するだけでよい.

あるブログの実装方法とは異なり、私は変数sizeを使っています.std::listのsizeメソッドはO(n)時間の複雑さであるため、双方向チェーンテーブルの長さを保存します(具体的には私の別の転載ブログを参照してください).この改良を行った後,getとputの時間複雑度はいずれもO(1)であった.
コード実装

class LRUCache {
public:
    LRUCache(int capacity) : cap_(capacity), size_(0) {}

    int get(int key)
    {
        if(key2pos_.find(key) != key2pos_.end()) {
            put(key, key2pos_[key]->second);
            return key2pos_[key]->second;
        }
        return -1;
    }

    void put(int key, int value)
    {
        if(key2pos_.find(key) != key2pos_.end()) {
            data_.erase(key2pos_[key]);
            --size_;
        } else if(size_ >= cap_) {
            key2pos_.erase(data_.back().first);
            data_.pop_back();
            --size_;
        }
        data_.push_front({key, value});
        key2pos_[key] = data_.begin();
        ++size_;
    }

    void print()
    {
        for(auto& v : data_)
            cout << v.first << ": " << v.second << ";";
        cout << endl;
    }

private:
    int cap_;
    int size_;
    list<pair<int, int>> data_;
    unordered_map<int, list<pair<int, int>>::iterator> key2pos_;
};