基于Boost Multi Index容器重构CacheWeb类的技术咨询

背景 #

原CacheWeb类已通过单元测试验证可用，现计划基于Boost库的Multi Index容器重构该类。尝试修改元素容器类型时写出如下代码：

typedef multi_index_container<items,indexed_by<sequenced<>,hashed_unique<identity<Item> >>> item_list;

触发错误：Invalid use of non-static data member '_items'。以下分析该错误及原代码中的其他问题，并提供重构思路。

核心错误分析（typedef问题） #

你写的typedef存在两个关键问题：

1. items是类的非静态成员变量，不是类型，不能作为multi_index_container的模板参数（模板参数需要类型）。
2. Item未定义，原代码中存储的元素是std::pair<Tkey, Tval>，需用该类型替代Item。

正确的typedef写法（需先包含Boost Multi Index头文件）：

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>

// 定义元素类型
using Item = std::pair<Tkey, Tval>;

// 定义Multi Index容器类型
using item_list = boost::multi_index::multi_index_container<
    Item,
    boost::multi_index::indexed_by<
        // 顺序索引：维护LRU的访问顺序，头部是最近访问的元素
        boost::multi_index::sequenced<>,
        // 哈希唯一索引：通过key快速查找，基于pair的first成员（Tkey）
        boost::multi_index::hashed_unique<
            boost::multi_index::member<Item, Tkey, &Item::first>
        >
    >
>;

注：这里用member提取器替代identity，因为我们需要基于pair的first成员（即key）做哈希索引，而不是整个Item。

原代码中的其他错误 #

1. lookup容器的键类型错误：

   std::unordered_map<key, typename std::list<std::pair<Tkey, Tval>>::iterator> lookup;
   

   这里的key未定义，应改为模板参数Tkey。

2. get方法返回类型未定义：

   const VAL_T& get(const Tkey& key)
   

   VAL_T是未定义的类型，需替换为模板参数Tval。

3. getItems方法语法错误：

   std::list<std::pair<Tkey, Tval>>getItems()
   

   返回类型和函数名之间缺少空格，应改为：

   std::list<std::pair<Tkey, Tval>> getItems()
   

4. 多余的闭合大括号：
   类定义结束后多了一个}，需删除。

5. capacityOut方法的边界逻辑：
   当capacity为0时，原逻辑直接返回0，意味着允许无限存储，若这不是预期行为，需调整逻辑（比如抛出异常或限制存储）。

Boost Multi Index重构后的CacheWeb实现思路 #

使用Multi Index容器后，无需再维护单独的lookup哈希表，容器本身提供两种索引：

• 顺序索引：用于实现LRU的访问顺序调整（将访问过的元素移到头部）。
• 哈希索引：用于快速查找元素。

重构后的核心方法示例：

template<typename Tkey, typename Tval>
class CacheWeb {
private:
    using Item = std::pair<Tkey, Tval>;
    using item_list = boost::multi_index::multi_index_container<
        Item,
        boost::multi_index::indexed_by<
            boost::multi_index::sequenced<>,
            boost::multi_index::hashed_unique<
                boost::multi_index::member<Item, Tkey, &Item::first>
            >
        >
    >;

    unsigned int capacity;
    item_list items;

    // 禁用拷贝构造和赋值
    CacheWeb(const CacheWeb&) = delete;
    CacheWeb& operator=(const CacheWeb&) = delete;

    int capacityOut() {
        if (capacity == 0 || items.size() <= capacity) {
            return 0;
        }
        int cnt = 0;
        while (items.size() > capacity) {
            // 删除顺序索引的最后一个元素（最久未访问）
            items.pop_back();
            ++cnt;
        }
        return cnt;
    }

public:
    CacheWeb(int icapacity) : capacity(icapacity) {}
    virtual ~CacheWeb() = default;

    int size() {
        return items.size();
    }

    bool empty() {
        return items.empty();
    }

    void clear() {
        items.clear();
    }

    bool contains(const Tkey& key) {
        // 使用哈希索引查找
        auto& hash_idx = items.get<1>();
        return hash_idx.find(key) != hash_idx.end();
    }

    void remove(const Tkey& key) {
        auto& hash_idx = items.get<1>();
        hash_idx.erase(key);
    }

    void put(const Tkey& key, const Tval& val) {
        auto& hash_idx = items.get<1>();
        auto it = hash_idx.find(key);
        if (it != hash_idx.end()) {
            // 更新值，并移到顺序索引的头部
            hash_idx.modify(it, [&val](Item& item) { item.second = val; });
            // 将元素从哈希索引转换为顺序索引的迭代器，然后移到头部
            auto seq_it = items.project<0>(it);
            items.relocate(items.begin(), seq_it);
            return;
        }
        // 插入新元素到顺序索引头部
        items.emplace_front(key, val);
        capacityOut();
    }

    std::list<Item> getItems() {
        // 将顺序索引的元素转换为list返回
        return std::list<Item>(items.begin(), items.end());
    }

    const Tval& get(const Tkey& key) {
        auto& hash_idx = items.get<1>();
        auto it = hash_idx.find(key);
        if (it == hash_idx.end()) {
            throw std::invalid_argument("Key does not exist");
        }
        // 移到顺序索引头部
        auto seq_it = items.project<0>(it);
        items.relocate(items.begin(), seq_it);
        return it->second;
    }
};

内容的提问来源于stack exchange，提问作者Keorus