C ++ Data structure that is still sorted by value & controls FIFO

I am looking for a data structure that performs quick insert sorting and works on the basis of FIFO.

What I'm trying to achieve is a fixed size data structure to hold a series of values. At each new stage of the iteration, I want to efficiently find the minimum or maximum value (so I want the data structure to be sorted at any time), and after asking to insert a new element, the oldest element will be automatically (or at least it can be effective ) jumped / thrown out.

So, I think I'm looking for some sort of priority FIFO queue.

Any help is greatly appreciated.