我有一张 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 容器?)
最佳答案
根据您使用的是什么类型的键,并且由于您使用的是单值映射,您可以尝试只在列表中存储一个 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);
关于c++ - 使用 std::map 和 std::list 构造 MRU 中的循环依赖,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13431767/