Циклическая зависимость в конструкции 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. ?)


c++ circular-dependency
person antak    schedule 17.11.2012    source источник
comment
Вместо списка (который вы должны сортировать самостоятельно) почему бы не использовать std::priority_queue? Вы можете использовать только ключ в этом, тогда вам не нужно беспокоиться о циклических зависимостях.   -  person Some programmer dude    schedule 17.11.2012
comment
@Joachim Pileborg: std::priority_queue не подлежит обновлению/перестановке. Как только элемент вставлен в очередь, он не может быть удален, его приоритет не может быть изменен, а его положение в очереди не может быть соответствующим образом обновлено. Между тем, похоже, что ОП должен иметь возможность обновлять приоритеты. Это можно сделать и с std::priority_queue путем мягкого удаления устаревшего элемента (пометив его как удаленный) и вставив новый с новым приоритетом. Но это далеко не идеально.   -  person AnT    schedule 17.11.2012

Ответы (2)


arrow_upward
0
arrow_downward

В зависимости от того, какие вещи вы используете в качестве ключей, и из-за того, что вы используете карту с одним значением, вы можете попробовать просто сохранить key_t в своем списке вместо сохранения итератора в std::map. Поскольку карта имеет только одно значение для каждого ключа, у вас по-прежнему есть уникальный доступ к элементу, и вы избавляетесь от этой ужасной проблемы циклической зависимости.

Код будет выглядеть примерно так:

typedef std::list<key_t> mru_list_t;

для типа списка и в конце вашей функции use вам нужно будет изменить:

mru_list.push_front(map_it);

to

mru_list.push_front(map_it->first);
person Xymostech    schedule 17.11.2012
comment
Это надежно избавляет от проблемы круговой зависимости. Тем не менее, я все еще надеюсь, что язык не требует от меня жертвовать производительностью для достижения семантического соответствия (т. е. дополнительного поиска карты, если я хочу получить значение). - person antak; 17.11.2012

arrow_upward
0
arrow_downward

Я предлагаю вам взглянуть на Boost Multi Index, который позволяет использовать несколько индексов для одного и того же фрагмента данных (и, следовательно, может соответствовать нескольким порядкам).

В частности, есть пример MRU уже, хотя вы можете не захотеть смотреть на это прямо сейчас и поэкспериментировать с библиотекой самостоятельно.

Основная идея Boost Multi-Index заключается в том, что вместо указателей на элементы и нескольких взаимосвязанных структур, которые могут не синхронизироваться, вы вместо этого вписываете каждый элемент в ячейку-контейнер, предназначенную для привязки к нескольким индексам.

В примере MRU вы можете, например, самостоятельно реализовать связанный список, вписав каждое «значение» в struct V { value_t value; V* next; }, например.

person Matthieu M.    schedule 17.11.2012