使用std::map和std::list构造MRU中的循环依赖关系

Question

我有一个映射(std::map<key_t, val_t>)，我想要跟踪使用的键的顺序是最近的和最近的。

这是我尝试过的，但是我被循环依赖的声明卡住了：

typedef ... key_t;

typedef struct {
    ...
    mru_list_t::iterator mru_it;
} val_t;

typedef std::map<key_t, val_t> foo_map_t;

typedef std::list<foo_map_t::iterator> mru_list_t;

更新例程似乎足够直截了当：

foo_map_t foo_map;
mru_list_t mru_list;

void use(const key_t& key) {

    // get the entry corresponding to the key
    std::pair<foo_map_t::iterator, bool> r;
    r = foo_map.insert(std::make_pair(key, val_t()));
    foo_map_t::iterator map_it = r.first;

    // the corresponding value
    val_t *val = &(*map_it).second;

    // did it already exist?
    if (!r.second) {
        // remove from the mru list
        mru_list.erase(val->mru_it);
    }

    // push to the front of the list
    mru_list.push_front(map_it);
    val->mru_it = mru_list.begin();
}

，我该怎么处理呢？(循环依赖项)

我知道我可以转发、声明和使用指针，而不是：

typedef struct _key_t key_t;
typedef struct _val_t val_t;
typedef std::list<std::pair<key_t, val_t> *> mru_list_t;

但这似乎依赖于无文件记录的特征。

编辑：，还是，我需要意识到这是不可能的？(并与无文档的特性一起，滚动我自己的链接列表，或者用其他非stl容器替换部件？)

Answer 1

根据您所使用的键类型，并且由于您使用的是单值映射，您可以尝试将key_t存储在列表中，而不是将迭代器存储到std::map中。因为映射每个键只有一个值，所以您仍然可以唯一地访问元素，并且可以解决这个可怕的循环依赖问题。

代码看起来类似于：

typedef std::list<key_t> mru_list_t;

对于列表的类型，以及在use函数的末尾，您需要更改：

mru_list.push_front(map_it);

至

mru_list.push_front(map_it->first);

Answer 2

我建议您查看一下Boost多重指数，它的构建是为了允许对同一数据块进行多个索引(因此可以匹配多个订单)。

更具体地说，已经有了一个MRU的例子，尽管您现在可能不想看它，自己尝试一下这个库。

Boost多重索引的主要思想是，不是有指向元素和可能不同步的多个相关结构的指针，而是将每个元素插入到一个容器单元格中，以便将其连接到多个索引上。

例如，在MRU示例中，您可以自己实现链接列表，方法是将每个“值”登录到struct V { value_t value; V* next; }中。