1

我有一个 map( 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 容器替换部分？）

4

2 回答 2

0

我建议您看一下Boost Multi Index，该索引旨在允许对同一数据块进行多个索引（因此可以匹配多个订单）。

更具体地说，已经有一个MRU示例，尽管您可能不想现在查看它，并自己尝试使用该库。

Boost Multi-Index 的主要思想是，与其拥有指向可能不同步的元素和多个相互关联的结构的指针，不如将每个元素铭刻在一个容器单元中，该容器单元旨在与多个索引挂钩。

例如，在 MRU 的示例中，您可以通过将每个“值”写入 a 来自己实现链表struct V { value_t value; V* next; }。

于 2012-11-17T16:32:21.253 回答
0

根据您用作键的类型，并且由于您使用的是单值映射，您可以尝试仅将 a 存储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);
于 2012-11-17T15:23:56.467 回答