c++ Data Structure that remains sorted by value & operates FIFO

Question

I am looking for a data structure that performs fast sorted insertion and operates based on FIFO.

What I am trying to achieve is a data structure of a fixed size to hold a series of values. At each new step of an iteration, I want to efficiently be able to find the min or max value (so I want the data structure to be sorted at all times) and upon the request to insert a new element, the oldest element be automatically (or at least able to be efficiently) popped / discarded.

So I guess I am looking for some sort of of FIFO priority queue.

Any help much appreciated.

Answer 1

Why not have both an std::set or multiset, and a regular FIFO queue like std::queue of iterators into that set? At every insertion, check if the queue became bigger than your maximum size, then remove the front element from the queue and the set.