Круговая зависимость в конструкции MRU с использованием std :: map и std :: list
У меня есть карта (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 контейнер?)
Решение
В зависимости от того, какие вещи вы используете в качестве ключей, и из-за того, что вы используете карту с одним значением, вы можете попытаться просто сохранить 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);
Другие решения
Я предлагаю вам взглянуть на Увеличить мульти индекс которая построена так, чтобы разрешить несколько индексов для одного и того же фрагмента данных (и, следовательно, может соответствовать нескольким порядкам).
Более конкретно, есть пример MRU уже, хотя вы можете не захотеть смотреть на это прямо сейчас и поэкспериментировать с библиотекой самостоятельно.
Основная идея Boost Multi-Index заключается в том, что вместо наличия указателей на элементы и нескольких взаимосвязанных структур, которые могут не синхронизироваться, вместо этого нужно вписать каждый элемент в ячейку контейнера, предназначенную для подключения к нескольким индексам.
В примере MRU вы можете, например, реализовать связанный список самостоятельно, вписав каждое «значение» в struct V { value_t value; V* next; }, например.