Circular dependency in MRU construct using std::map and std::list

Question

I have a map (std::map<key_t, val_t>) and I want to keep track of the keys that are used in the order of most recent to least recent.

This is what I tried, but I get stuck on the declaration with a circular-dependency:

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;

The update routine seems straight-forward enough:

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();
}

How should I deal with this? (The circular dependency)

I know that I could forward declare and use a pointer instead:

typedef struct _key_t key_t;
typedef struct _val_t val_t;
typedef std::list<std::pair<key_t, val_t> *> mru_list_t;

But this seems to rely on an undocumented feature.

EDIT: Or, do I need to realize that this can't be done? (And go with the undocumented feature, roll my own linked-list, or otherwise replace parts with some other non-stl container?)

Instead of having a list (that you must keep sorted yourself) why not use [`std::priority_queue`](http://en.cppreference.com/w/cpp/container/priority_queue)? You can use only the key in this, then there's no need to worry about "circular dependencies". — Some programmer dude, Nov 17 '12 at 15:07
@Joachim Pileborg: `std::priority_queue` is not updatable/rearrangeable. Once an element is inserted into the queue, element cannot be deleted, its priority cannot be changed and its position in the queue cannot be updated accordingly. Meanwhile, it looks like the OP needs to be able to update the priorities. It is doable with `std::priority_queue` as well by soft-deletion of the outdated element (marking it as "deleted") and inserting a new one with new priority. But it is far from perfect. — AnT stands with Russia, Nov 17 '12 at 15:45

score 0 · Answer 1 · answered Nov 17 '12 at 15:23

Depending on what kind of things you are using as keys, and because of the fact that you are using a single-value map, you could try just storing a key_t in your list, instead of storing an iterator into the std::map. Because the map only has a single value per key, you still have unique access to the element, and you get rid of this horrible circular dependency problem.

The code would look something like:

typedef std::list<key_t> mru_list_t;

for the type of the list, and at the end of your use function, you would need to change:

mru_list.push_front(map_it);

to

mru_list.push_front(map_it->first);

That soundly gets rid of the circular-dependency problem. However, I'm still hoping the language isn't requiring me to trade off performance to achieve semantic compliance (i.e. the extra map lookup if I want the value). — antak, Nov 17 '12 at 16:32

score 0 · Answer 2 · answered Nov 17 '12 at 16:32

I suggest that you take a look at Boost Multi Index which is built to allow several indexes on the same piece of data (and can therefore match several orders).

More specifically, there is an example of MRU already, although you may not want to look at it right now, and experiment with the library by yourself.

The main idea of Boost Multi-Index is that instead of having pointers to elements and multiple inter-related structures that may fall out of sync, you instead inscribe each element in a container cell designed to be hooked on the multiple indexes.

In the example of a MRU, you could for example implement the linked-list yourself by inscribing each "value" into a struct V { value_t value; V* next; }, for example.

Circular dependency in MRU construct using std::map and std::list

2 Answers2