C++实现LRU队列

Jan 15, 2017

LRU队列即最少使用算法,核心思想是:数据最近被访问过,那么它被访问的几率更高。扩展起来解释即如果某组数据被频繁访问，那么这组数据应该放在最显眼的地方（以最快速度取到），至于访问几率比较低的数据可以放在某个角落。

以程序角度实现方式：以list作为数据缓存队列，访问几率高的数据放在list的头，访问几率低的数据放在list尾部，如此，访问几率越高的数据存取速度越快。

对于LRU实现方式，可以采用链表。但在现代编译器的优化下，采用std::list未必不是一种好的方式，能够让代码更精简（越复杂的代码出错的可能性越高）。明确算法核心内容之后，确定对外接口：

  1. Put，放入数据，内部需要进行访问几率判断。
  2. Get，获取数据。
  3. Del，删除。

代码实现在这里：https://github.com/shaoyuan1943/LRU

#pragma once
#ifndef _LRU_H_
#define _LRU_H_

#include <string>
#include <functional>
#include <map>
#include <list>

namespace lru
{
    template<typename T>
    class Entry final
    {
    public:
        std::wstring key;
        T value;
    };

    template<typename T>
    using Iter = typename std::list<Entry<T>>::iterator;
    
    template<typename T>
    using EvictCallback = typename std::function<void(const Entry<T>& t)>;

    template<typename T>
    class List final
    {
    public:
        List()
        {
        }
        
        ~List()
        {
            lst_.clear();
        }
    
        unsigned int Capacity() const
        {
            return capacity_;
        }
        
        Iter<T> PushFront(const Entry<T>& entry)
        {
            ++capacity_;
            return lst_.insert(lst_.begin(), entry);
        }
        
        Iter<T> MoveToFront(const Iter<T>& it)
        {
            auto v = (*it);
            lst_.erase(it);
            return lst_.insert(lst_.begin(), v);
        }
    
        bool Remove(const Iter<T>& it)
        {
            if (lst_.size() > 0 && capacity_ > 0)
            {
                --capacity_;
                lst_.erase(it);
                return true;
            }
            
            return false;
        }
    	
        Iter<T> Back()
        {
            if (lst_.size() > 0 && capacity_ > 0)
            {
                return (--lst_.end());
            }
            
            return lst_.end();
        }
        bool IsEnd(Iter<T> it) const
        {
            return it != lst_.end();
        }
    private:
        unsigned int capacity_{ 0 };
        std::list<Entry<T>> lst_;
    };
    
    template<typename T>
    class LRU final
    {
    public:
        LRU(const unsigned int& fixed, const EvictCallback<T>& callback = nullptr)
        {
            if (fixedCapacity_ != fixed)
                fixedCapacity_ = fixed;
        
            if (callback != nullptr)
                evictCallback_ = callback;
        }
        
        ~LRU()
        {}
        
        bool Put(const std::wstring& key, const T& value)
        {
            if (key.empty())
                return false;
            
            auto it = lruMap_.find(key);
            if (it != lruMap_.end())
            {
                auto newIt = lruList_.MoveToFront(it->second);
                lruMap_[key] = newIt;
                return false;
            }
            
            if (fixedCapacity_ <= lruList_.Capacity())
            {
                auto delIt = lruList_.Back();
                if (lruList_.IsEnd(delIt))
                {
                    _Delete(delIt);
                }
                else
                    return false;
            }
            
            Entry<T> entry;
            entry.key = key;
            entry.value = value;
            auto iter = lruList_.PushFront(entry);
            lruMap_[key] = iter;
            return true;
        }
        
        T* Get(const std::wstring& key)
        {
            if (key.empty())
                return nullptr;
            
            auto it = lruMap_.find(key);
            if (it == lruMap_.end())
                return nullptr;
            
            auto newIt = lruList_.MoveToFront(it->second);
            lruMap_[key] = newIt;
            return &newIt->value;
        }
        
        bool Del(const std::wstring& key)
        {
            if (key.empty())
                return false;
            
            if (lruList_.Capacity() <= 0)
                return false;
            
            auto it = lruMap_.find(key);
            auto entry = (*it);
            if (it == lruMap_.end())
                return false;
            
            _Delete(it->second);
            return true;
        }
    
    private:
        void _Delete(const Iter<T>& it)
        {
            if (!lruList_.IsEnd(it))
                return;
            
            auto entry = *(it);
            if (lruList_.Remove(it))
            {
                if (evictCallback_ != nullptr)
                    evictCallback_(entry);
                
                lruMap_.erase(entry.key);
            }
        }
    
    private:
        unsigned int fixedCapacity_{ 100 };
        std::map<const std::wstring, Iter<T>> lruMap_;
        List<T> lruList_;
        EvictCallback<T> evictCallback_{ nullptr };
    };
}
#endif