LRU 实现

LRU:

Least recently used, 最近最少(least)使用: 对于当前所有缓存, 后续使用时, 缓存满的时候,
最近使用的缓存被移除的概率最小(最后被移除)! .. 即缓存满的时候最先移除最近最少使用的!

(Discards the least recently used items first, i.e. once a cache used, then it least likely to be removed when caches full!!)

参考: https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU

---

C++ 实现: 使用双链表存储缓存以及使用 hash map 查找缓存!

See also:

• doublylinkedlist.hpp
• lrucache.hpp
• test/base/lrucache.cpp

template<typename K, typename V>
class LruCache {
public:
    /// Internal cache type.
    using Cache = std::tuple<K, V>;
    /// Cache datas type.
    using Caches = DoublyLinkedList<Cache>;
    /// Key to cache iterator type.
    using KeyCaches = std::unordered_map<K, typename Caches::Iterator>;
    /// Default ctor.
    LruCache() noexcept;
    /// Dtor
    ~LruCache() noexcept;
    /// @return caches capacity.
    inline int32_t getCapacity() const noexcept;
    /// @return current caches size.
    inline int32_t getSize() const noexcept;
    /// Check whether this caches empty.
    inline bool isEmpty() const noexcept;
    /**
     * Set cache capacity.
     * @param capacity the capacity to set, NOTE: should >= current caches
     * and > 0.
     * @return true when set success, otherwise false.
     */
    inline bool setCapacity(const int32_t capacity) noexcept;
    /**
     * Set or update cache of key.
     * @param key the key to set.
     * @param value the value to set.
     */
    void set(K&& key, V&& value) noexcept;
    void set(const K& key, V&& value) noexcept;
    void set(K&& key, const V& value) noexcept;
    void set(const K& key, const V& value) noexcept;
    /// Check whether has cache of key.
    inline bool has(const K& key) const noexcept;
    /**
     * Get cache of key.
     * @param key the key to get cache.
     * @return the cache of key.
     * @return true when success otherwise false.
     */
    bool get(const K& key, V& value) const noexcept;
    /**
     * Get cache of key, if not exists, value is default.
     * @param key the key to get cache.
     * @return the cache of key.
     * @sa
     * - has
     * - get
     * - set
     */
    V& operator[](const K& key) noexcept;
    /// @throw std::logic_error when no such key.
    const V& operator[](const K& key) const;
    /// @return caches.
    inline const Caches& getCaches() const noexcept;
    /// Clear all caches.
    inline void clear() noexcept;
private:
    mutable Caches caches;///< The cache datas.
    KeyCaches keyCaches;///< { key, cacheIterator }.
    int32_t capacity{ 16 };///< The capacity of cache(max caches), default 16.
};

template<typename K, typename V>
LruCache<K, V>::LruCache() noexcept {}
template<typename K, typename V>
LruCache<K, V>::~LruCache() noexcept {}
template<typename K, typename V>
inline int32_t LruCache<K, V>::getCapacity() const noexcept
{
    return this->capacity;
}
template<typename K, typename V>
inline int32_t LruCache<K, V>::getSize() const noexcept
{
    return this->caches.size();
}
template<typename K, typename V>
inline bool LruCache<K, V>::isEmpty() const noexcept
{
    return this->caches.empty();
}
template<typename K, typename V>
bool LruCache<K, V>::setCapacity(const int32_t capacity) noexcept
{
    if (capacity < 1) {
        return false;
    }
    if (uint32_t(capacity) < this->caches.size()) {
        return false;
    }
    this->capacity = capacity;
    return true;
}
template<typename K, typename V>
void LruCache<K, V>::set(K&& key, V&& value) noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt != this->keyCaches.end()) {
        auto& cacheIt = kCIt->second;
        std::get<1>(*cacheIt) = std::move(value);
        this->caches.rewire_to_front(cacheIt);
    } else {
        if (int32_t(this->keyCaches.size()) >= this->capacity) {
            auto const& back = this->caches.back();
            this->keyCaches.erase(std::get<0>(back));
            this->caches.pop_back();
        }
        this->caches.push_front(Cache{ key, std::move(value) });
        this->keyCaches[std::move(key)] = this->caches.begin();
    }
}
template<typename K, typename V>
void LruCache<K, V>::set(const K& key, V&& value) noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt != this->keyCaches.end()) {
        auto& cacheIt = kCIt->second;
        std::get<1>(*cacheIt) = std::move(value);
        this->caches.rewire_to_front(cacheIt);
    } else {
        if (int32_t(this->keyCaches.size()) >= this->capacity) {
            auto const& back = this->caches.back();
            this->keyCaches.erase(std::get<0>(back));
            this->caches.pop_back();
        }
        this->caches.push_front(Cache{ key, std::move(value) });
        this->keyCaches[key] = this->caches.begin();
    }
}
template<typename K, typename V>
void LruCache<K, V>::set(K&& key, const V& value) noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt != this->keyCaches.end()) {
        auto& cacheIt = kCIt->second;
        std::get<1>(*cacheIt) = value;
        this->caches.rewire_to_front(cacheIt);
    } else {
        if (int32_t(this->keyCaches.size()) >= this->capacity) {
            auto const& back = this->caches.back();
            this->keyCaches.erase(std::get<0>(back));
            this->caches.pop_back();
        }
        this->caches.push_front(Cache{ key, value });
        this->keyCaches[std::move(key)] = this->caches.begin();
    }
}
template<typename K, typename V>
void LruCache<K, V>::set(const K& key, const V& value) noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt != this->keyCaches.end()) {
        auto& cacheIt = kCIt->second;
        std::get<1>(*cacheIt) = value;
        this->caches.rewire_to_front(cacheIt);
    } else {
        if (int32_t(this->keyCaches.size()) >= this->capacity) {
            auto const& back = this->caches.back();
            this->keyCaches.erase(std::get<0>(back));
            this->caches.pop_back();
        }
        this->caches.push_front(Cache{ key, value });
        this->keyCaches[key] = this->caches.begin();
    }
}
template<typename K, typename V>
inline bool LruCache<K, V>::has(const K& key) const noexcept
{
    return this->keyCaches.find(key) != keyCaches.end();
}
template<typename K, typename V>
bool LruCache<K, V>::get(const K& key, V& value) const noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt == this->keyCaches.end()) {
        return false;
    }
    const auto& cacheIt = kCIt->second;
    this->caches.rewire_to_front(cacheIt);
    value = std::get<1>(*cacheIt);
    return true;
}
template<typename K, typename V>
V& LruCache<K, V>::operator[](const K& key) noexcept
{
    auto kCIt = this->keyCaches.find(key);
    if (kCIt == this->keyCaches.end()) {
        this->set(key, V{});
        kCIt = this->keyCaches.find(key);
    }
    auto& cacheIt = kCIt->second;
    this->caches.rewire_to_front(cacheIt);
    return std::get<1>(*cacheIt);
}
template<typename K, typename V>
const V& LruCache<K, V>::operator[](const K& key) const
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt == this->keyCaches.end()) {
        throw std::logic_error("no such key");
    }
    const auto& cacheIt = kCIt->second;
    this->caches.rewire_to_front(cacheIt);
    return std::get<1>(*cacheIt);
}
template<typename K, typename V>
inline const typename LruCache<K, V>::Caches&
LruCache<K, V>::getCaches() const noexcept
{
    return this->caches;
}
template<typename K, typename V>
inline void LruCache<K, V>::clear() noexcept
{
    this->caches.clear();
    this->keyCaches.clear();
}
template<typename K, typename V>
std::ostream& operator<<(
    std::ostream& os, const LruCache<K, V>& lruCache) noexcept
{
    const auto& caches = lruCache.getCaches();
    os << "capacity " << lruCache.getCapacity();
    const int32_t size = lruCache.getSize();
    os << ", size " << size;
    if (size > 0) {
        os << ": ";
    }
    for (const auto& cache : caches) {
        os << '(' << std::get<0>(cache) << ',' << std::get<1>(cache) << ") ";
    }
    return os;
}