FJUTOJ-3682 LRU算法的实现2 (链表+哈希)

传送门

此题让我们实现一个LRU的模板类。本题较简便且高效的写法是维护一个std::list和一个std::unordered_map。

std::list 与 std::unordered_map 中存放的内容

std::list中存放各key，类型为K。链表中各键码存放的顺序是按照访问顺序存放的。

std::unordered_map中以key为第一维，第二维为一个pair，其first和second分别为：

first: 该key对应的value。

second:该key在std::list中的迭代器方便访问。

为方便，下面用“链表”来指代std::list，用“哈希表”来指代std::unordered_map。

各操作实现

insert操作：用哈希表判断该键是否已经存在。若存在，先在链表中删除该key，然后再新加一个该key到链表尾部，并更新在哈希表中的value和链表的迭代器。若不存在，则直接加至链表尾部，并在哈希表中插入该key，伴随着对应的value和链表迭代器。

get操作：直接从哈希表中获得其value即可。代码实现未检测该key是否存在，严谨来说应该加上异常处理。

contains操作：直接在哈希表中查询是否存在该key即可。

vis操作：用哈希表判断该键是否存在。若不存在，则本操作无效。否则，将该键从链表中删除，然后再将其加至链表尾部，并更新哈希表中对应链表迭代器。

pop操作：判断是否整个容器已经为空。若为空，则本操作无效。否则，将链表头部元素从链表中删除，并在哈希表中删除对应键值信息。

remove操作：用哈希表判断该键是否存在。若不存在，则本操作无效。否则，将该键从链表中删除，并在哈希表中删除对应键值信息。

empty操作：哈希表或链表判空即可。

size操作：取哈希表或链表大小即可。

clear操作：清空哈希表和链表即可。

时间复杂度

各操作基于对链表和哈希表的修改。期望复杂度均为\(O(1)\)。

参考代码实现

#include <list>

#include <unordered_map>

template <typename K, typename V>

class LRU {

private:

    typedef typename std::list<K>::iterator listIter;

    typedef typename std::unordered_map<K, std::pair<V, listIter>>::iterator unorderedMapIter;

    std::list<K> lst;

    std::unordered_map<K, std::pair<V, listIter>> mp;

public:

    void insert(const K &key, const V &value) {

        unorderedMapIter it = mp.find(key);

        if (it == mp.end()) {

            lst.emplace_back(key);

            mp.insert(std::make_pair(key, std::make_pair(value, --lst.end())));

        } else {

            lst.erase(it->second.second);

            lst.emplace_back(key);

            it->second = std::make_pair(value, --lst.end());

        }

    }

    // If Key doesn't exist, this will create one <Key, zero>

    V get(const K &key) {

        return mp[key].first;

    }

    bool contains(const K &key) {

        return mp.count(key) == 1;

    }

    void vis(const K &key) {

        unorderedMapIter it = mp.find(key);

        if (it != mp.end()) {

            lst.erase(it->second.second);

            lst.emplace_back(key);

            it->second.second = --lst.end();

        }

    }

    void pop() {

        if (!lst.empty()) {

            mp.erase(lst.front());

            lst.pop_front();

        }

    }

    void remove(const K &key) {

        unorderedMapIter it = mp.find(key);

        if (it != mp.end()) {

            lst.erase(it->second.second);

            mp.erase(it);

        }

    }

    bool emtpy() { // 注意本题要求函数名为emtpy

        return lst.empty();

    }

    unsigned long long size() {

        return lst.size();

    }

    void clear() {

        lst.clear();

        mp.clear();

    }

};

巴特西

FJUTOJ-3682 LRU算法的实现2 (链表+哈希)

std::list 与 std::unordered_map 中存放的内容

各操作实现

时间复杂度

参考代码实现

最新文章

热门文章