c++ - 使用 std::map 和 std::list 构造 MRU 中的循环依赖

Question

我有一张 map ( std::map<key_t, val_t> )，我想按最近到最近的顺序跟踪使用的 key 。

这是我尝试过的方法，但我被循环依赖的声明困住了:

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;

不过这个好像要依赖an undocumented feature .

编辑:或者，我是否需要意识到这无法完成？(并使用未记录的功能，滚动我自己的链表，或者用其他一些非-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);