Typedef mutually referenced stl container

Question

I have a std::map and a std::list. I want the elements in the containers to have the type of the iterator of opposite container.

How can I typedef them?

Example:

 typedef std::map<MyKeyClass, typename MyList::iterator> MyMap;
 //                                    ^ MyList not defined.
 typedef std::list<typename MyMap::iterator> MyList;

Of course inverting the two lines doesn't work.

I also tried

 typedef std::map<MyKeyClass,
                  typename std::list<typename MyMap::iterator>::iterator> MyMap;
 typedef std::list<typename MyMap::iterator> MyList;

but that did not work either.

UPDATE: The reason I need this is to keep track key/value pairs by 2 aspect of orders. Let's say that I have a map<KEY,VALUE>. It is sorted by KEY and find a value by a key is fast. But I also want to keep track the values by the time when the value is added. I want to know which value is least recently added. To do this I use list. The reason I need an iterator back to the list from the map is to erase an element in the containers. When I erase an element in the map by a key, I also need to erase an element in the list. I also need the opposite (erasing the least recently value). I found that my idea that to use pointers explicitly (as in the comments) does not work because I need actually an iterator to erase an element in the containers.

UPDATE2: I'm asking this because I felt a little weird that I can not do this. I often use STL container as a basic data structure (as everyone does). For example, std::map can be used as alternative to implementation of binary tree with explicit struct and pointers. STL containers are well designed and I have not experienced that I can not use STL container to express some structure that can be done by struct and pointers. They may not guarantee that STL container has same property as struct and pointer structure have. But still, with such simple structure I felt a little strange I can not express it with STL containers.

Answer 1

You are probably looking for a multi-index container, as the one found in boost. It allows you to have maps / sets sorted and accessible by multiple key types.

Boost bimap is a similar tool, with only two keys/ indices, essentially allowing you to access a map by both key and value.