C++ boost - Is there a container working like a queue with direct key access?

Question

I was wonndering about a queue-like container but which has key-access, like a map. My goal is simple : I want a FIFO queue, but, if I insert an element and an element with a given key is already in the queue, I want it the new element to replaced the one already in the queue. For example, a map ordered by insertion time would work .

If there is no container like that, do you think it can be implemented by using both a queue and a map ?

Answer 1

Boost multi-index provides this kind of container.

To implement it myself, I'd probably go for a map whose values consist of a linked list node plus a payload. The list node could be hand-rolled, or could be Boost intrusive.

Note that the main point of the queue adaptor is to hide most of the interface of Sequence, but you want to mess with the details it hides. So I think you should aim to reproduce the interface of queue (slightly modified with your altered semantics for push) rather than actually use it.