C++ data structure that supports pop oldest inserted and max

Question

I've spent a while researching this, and haven't found an answer yet, and I know that a 40+ year old language with all sorts of features probably does this.

I'm looking for a data structure to hold 500 ints only. I need to be able to compare the max int in that with a given int. I also want the structure to remove the earliest inserted, like a queue.

Is there a data structure that supports both? I do not need random access except to run min() on it.

There are priority queues, which support max but they don't autohandle the size. I can write my own function to do this but thought I would ask anyways/

Sounds like you need to roll your own wrapper around an existing container (such as list), on insert keep track of min/max and it will be pretty efficient.. — Nim, Apr 29 '16 at 04:55
The size isn't handled by the data structure. One must pop manually. — JohnAllen, Apr 29 '16 at 04:57
So when you have 500 element and insert yet one more, you want the oldest to be popped automatically - is that it? — Support Ukraine, Apr 29 '16 at 04:59
Related query: http://stackoverflow.com/questions/2933758/priority-queue-with-limited-space-looking-for-a-good-algorithm Hope this helps :) — Agam, Apr 29 '16 at 04:59
Yes, when the structure has the 501st element pushed into it, the 0th (as determined by insert time) is popped out automatically. — JohnAllen, Apr 29 '16 at 05:01
I don't think you'll find such a container in any library. I guess you need to write your own - maybe a template based class similar to priority queue — Support Ukraine, Apr 29 '16 at 05:04

John Zwinck · Answer 1 · 2016-04-29T05:00:45.850

To hold just 500 integers you want a circular buffer. It's in Boost:

http://www.boost.org/doc/libs/release/doc/html/circular_buffer.html

But this won't help you find the min or max in the container. For that you'll need these:

http://en.cppreference.com/w/cpp/algorithm/min_element http://en.cppreference.com/w/cpp/algorithm/max_element http://en.cppreference.com/w/cpp/algorithm/minmax_element

You can't exactly do both at once, because the requirement to remove the oldest element first requires sorting by insert order, whereas the requirement to find the min or max element requires sorting in order of values somehow (either linear, or as a heap like priority_queue does).

Finding the min/max of 500 integers should be extremely fast on modern machines. But if you object to the algorithmic complexity of a linear scan, you can try this:

Store your elements in a set<int> which gives you *begin() and *rbegin() to get the min and max values.
Store iterators into the set in a separate circular buffer. Set iterators are not invalidated by insert and erase of other iterators, so this is safe. When the circular buffer is full, erase the oldest iterator from the set, then erase it from the circular buffer.

Yeah I had come across that in my search. Was trying to find a built-in solution seeing as how I'm new to C++ and there are so many libs! — JohnAllen, Apr 29 '16 at 05:00
@JohnAllen: The STL has a bunch of containers but there are tons more in Boost and even more elsewhere (Intel TBB, BitMagic, etc.). I've updated my answer with a hybrid idea if you want optimal big-O performance. — John Zwinck, Apr 29 '16 at 05:02
"You can't exactly do both at once" - sure you can, if you use a data structure that's a combination of two linked lists, maintained in both age order and sorted order simultaneously. Or perhaps a tree/heap and a list, for efficient insertion in sorted order. But I doubt that's in the standard library. — user253751, Apr 29 '16 at 05:05

C++ data structure that supports pop oldest inserted and max

1 Answers1