C++ LFU嵌LRU递进缓存

2025-12-19

本文作者原创，首发在本博客；CSDN 上的同名文章已标注为转载并回链到本页：https://blog.csdn.net/qq_30220519/article/details/156096248

背景

怎么样选出最受欢迎的水果中最近购买的品种的价格？

LRU类

#include <list>
#include <map>
#include <unordered_map>

template<typename K, typename V>
class LRUMap {
public:
    using ListType = std::list<std::pair<K, V>>;
    using CacheMap = std::map<K, typename ListType::iterator>;
    using CacheMapIter = typename CacheMap::iterator;

    LRUMap(int cap = 100)
        : m_capacity(cap)
    {
    }

    virtual ~LRUMap()
    {
    }

    CacheMapIter find(const K& key)
    {
        return m_cache.find(key);
    }

    bool isValid(const CacheMapIter& iter) const
    {
        return iter != m_cache.end();
    }

    V get(const K& key)
    {
        return get(find(key));
    }

    /**
     * @brief 缓存查询
     * @param it
     */
    V get(const CacheMapIter& it)
    {
        if (it == m_cache.end())
            return {};
        m_list.splice(m_list.begin(), m_list, it->second);
        return it->second->second;
    }

    /**
     * @brief 缓存新增
     * @param key
     * @param value
     */
    void put(const K& key, V value)
    {
        if (m_list.size() == m_capacity) {
            // 先删除最后一个
            auto last = m_list.end();
            --last;
            m_cache.erase(last->first);
            m_list.pop_back();
        }
        m_list.emplace_front(key, value);
        m_cache.try_emplace(key, m_list.begin());
    }

    /**
     * @brief 热度更新。数据变更
     * @param it
     */
    void update(const CacheMapIter& it)
    {
        if (it == m_cache.end())
            return;
        if (m_list.size() < 2)
            return;
        m_list.splice(m_list.begin(), m_list, it->second);
        it->second = m_list.begin();
    }

    /**
     * @brief 热度更新。数据不变
     * @param it
     * @param value
     */
    void update(const CacheMapIter& it, V value)
    {
        if (it == m_cache.end())
            return;
        if (m_list.empty())
            return;
        if (m_list.size() < 2) {
            m_list.begin()->second = value;
            return;
        }
        m_list.splice(m_list.begin(), m_list, it->second);
        it->second = m_list.begin();
        it->second->second = value;
    }

private:
    int m_capacity;
    ListType m_list;
    std::map<K, typename ListType::iterator> m_cache;
};

LRU键类

class Key {
public:
	Key(std::string type, std::string color):m_type(type), m_color(color){}
	
	std::string type() const { return m_type; }
	std::string color() const { return m_color; }
		
private:
	bool operator<(const Key& other) const { return  if(m_type == other.type()) return m_color < other.color(); return m_type < other.type();}
    bool operator==(const Key& other) const { return m_type == other.type() && m_color == other.color(); }
private:
	std::string m_type;
	std::string m_color;
};

LRU扩展类

class LRUCache
    : public LRUMap<Key, float> {
public:
	LFUCache(int cap)
		: LRUMap<Key, float>(cap)
		  , m_freq(0)
	{
	}

    int freq() const { return m_freq; }
    void setFreq(int freq) { m_freq = freq; }
	
private:
    int m_freq;
};

LFU类


// LRU最近使用缓存，例如青苹果和红苹果都是苹果，最近出现的颜色被缓存。
// LFU出现最多缓存，例如香蕉和苹果都是水果，应该被分类，出现次数多的水果被缓存。
// LFU嵌LRU类
class LFUCache {
public:
    using Iter = std::unordered_map<std::string, LRUCache>::iterator;
	LFUCache(int cap) : m_capacity(cap)
	{
	}

	LRUCache& insert(const std::string& content)
	{
		auto findIter = m_fruitLRUMap.find(content);
		if (findIter == m_fruitLRUMap.end()) {
			if (m_fruitLRUMap.size() >= m_capacity)
				shrink_to_fit_one();
			findIter = m_fruitLRUMap.try_emplace(content, 12).first;
		}
		updateFreq(findIter);
		return findIter->second;
	}
	
private:
	/* *
	 *  删除一个低频次的LRU缓存
	 */
	void shrink_to_fit_one()
	{
		if (m_fruitFreqMap.empty())
			return;
		auto lowFreqIter = m_fruitFreqMap.begin();
		if (lowFreqIter->second.empty())
			return;
		auto removeIter = lowFreqIter->second.begin();
		m_fruitLRUMap.erase(*removeIter); // 更新LRU缓存
		if (lowFreqIter->second.size() < 2) {
			m_fruitFreqMap.erase(lowFreqIter);
			return;
		}
		lowFreqIter->second.erase(removeIter); // 删除低频次的一个
	}	
	
	void updateFreq(Iter iter)
	{
		// 从旧的频次中删除
		auto oldFreq = iter->second.freq();
		auto oldFreqFindIter = m_fruitFreqMap.find(oldFreq);
		if (oldFreqFindIter != m_fruitFreqMap.end()) {
			if (oldFreqFindIter->second.size() < 2)
				m_fruitFreqMap.erase(oldFreq); // 只剩一个，整体删除
			else
				oldFreqFindIter->second.erase(iter->first); // 局部删除
		}

		// 新的频次添加
		auto newFreq = oldFreq + 1;
		auto newFreqFindIter = m_fruitFreqMap.find(newFreq);
		if (newFreqFindIter == m_fruitFreqMap.end())
			m_fruitFreqMap.try_emplace(newFreq, std::unordered_set<std::string>{ iter->first });
		else
			newFreqFindIter->second.insert(iter->first);
		iter->second.setFreq(newFreq);
	}
	
private:
    std::unordered_map<std::string, LRUCache> m_fruitLRUMap;  // 每种水果最近出现的品种
    std::map<int, std::unordered_set<std::string>> m_fruitFreqMap; // 经常出现的水果
    int m_capacity;
};

使用示例一

// 水果最近有被购买
bool testPriceChange(const Key& key, float price) {
	LRUMap<std::string, Key> lastFruitMap;
	auto findCacheIter = lastFruitMap.find(key.type());
	if (!lastFruitMap.isValid(findCacheIter))
		return true;
	if (findCacheIter->second->second != price)
		return true;
	return false;
}
Key key("苹果"，"红色");
float price = 10.f;
auto isChange = testPriceChange(key, price);
std::cout << "Price is change " << isChange << std::endl;

使用示例二

// 统计经常被购买水果价格
float testPrice(const Key& key) {
	LFUCache fruitCache;
	auto& lruCache = fruitCache.insert(key.type());
	auto cacheIter = lruCache.find(key);
	bool hasCache = lruCache.isValid(cacheIter);

	float price;
	if (hasCache) {	// 最近有被购买
		price = cacheIter->second->second;
		lruCache.update(cacheIter);
	} else {
		price = 10;  // 请输入价格
		lruCache.put(key, price);
	}
	return price;
}

Key key("苹果"，"红色");
auto price = testPrice(key);
std::cout << "Price is " << price << std::endl;