3

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.

oracle3001
  • 1,090
  • 19
  • 31
  • possible duplicate of [priority queue with limited space: looking for a good algorithm](http://stackoverflow.com/questions/2933758/priority-queue-with-limited-space-looking-for-a-good-algorithm) – geekosaur Apr 21 '12 at 21:10
  • That poster was asking about a data structure where "Elements need not to be sorted in any way". I need fixed size, FIFO and for it to remain sorted at all times. – oracle3001 Apr 21 '12 at 21:15
  • Is this not suitable: http://msdn.microsoft.com/en-us/library/4ef4dae9.aspx? Depending on the size of the container I would just use a vector or deque and apply the `algorithm` functions `sort`, `min` and `max` as and when you need, it should still be fast enough for what you want – EdChum Apr 21 '12 at 21:19
  • I am going to be doing this millions of times and as part of a real time process, so my initial thoughts were that continually having to re-sort wasn't the best way of going. – oracle3001 Apr 21 '12 at 21:23
  • Let me try that again if network will stay up long enough: actual dupe was http://stackoverflow.com/questions/5329312/free-implementation-of-bounded-priority-queue-in-c which apparently incorrectly points to that one. – geekosaur Apr 21 '12 at 21:26
  • Sorry I still don't see a solution in that post. That again meets the fixed size and sorted, but no discussion of removing the "oldest" element if a request for an insert is sent and the max size has been reached. – oracle3001 Apr 21 '12 at 21:33

1 Answers1

5

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.

Tavian Barnes
  • 12,477
  • 4
  • 45
  • 118
  • I can see how it is very efficient to keep popping from the head of a queue or heap of pointers. However, how efficient is continuous removal operations from a set, where the element maybe to anywhere in the binary search tree? – oracle3001 Apr 21 '12 at 22:23
  • According to http://www.sgi.com/tech/stl/SortedAssociativeContainer.html, erasing given an iterator is O(1). – Tavian Barnes Apr 21 '12 at 22:25
  • Ok cool...I am now thinking I might use Boost Circular Buffer to store the pointers. After the "run in period", then it should simply by a matter of popping the front element on each iteration. – oracle3001 Apr 21 '12 at 22:36
  • For anybody who comes to this thread...I have now found that apparently what one is looking for is LRU (least recently used) Map, or LRA (least recently added) Map depending on your needs. – oracle3001 Apr 21 '12 at 22:56