How to implement a queued map?

Question

The problem: I want to be able to FIFO queue outgoing messages. For update/deletion reasons, I also want to be able to access every message in the queue based upon an object ID.

I've currently implemented a solution where data is pushed into a deque, and an iterator to that data is kept. The iterator, keyed by an object ID, is then placed into a map. This was fine in the one place that I did it, but I now find myself wanting to do this elsewhere.

Am I over-complicating the problem? Is there a data structure out there that does this already?

Answer 1

Why not make the deque a deque of IDs and the map a map from ID to object. Then when you access an ID in the deque, you look up the ID in the map. If the IDs are globally unique, you only need one map to service all the deques.

Answer 2

I would try working the other way around. Utilize the map as your primary data structure. Have the queue contain object IDs that you can use to find the object from the map. You wouldn't need to keep track of all that extra information as far as iterators and such - just a map of your data, and a queue of object IDs.

• edit- Neil beat me to it, props go to him :)

Answer 3

I have used Boost.MultiIndex to do something very similar. Using it, you can have a container that has the data just once, but it can be accessed through two (or more!) facades: one that looks like a list, and another one that behaves as a map. When you erase an element using one facade (e.g., pop from the list), the other view will be updated seamlessly.