1

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/

Improve this question
8
  • 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.. Commented Apr 29, 2016 at 4:55
  • What do you mean by they don't autohandle the size ? Commented Apr 29, 2016 at 4:56
  • The size isn't handled by the data structure. One must pop manually. Commented Apr 29, 2016 at 4:57
  • 2
    So when you have 500 element and insert yet one more, you want the oldest to be popped automatically - is that it? Commented Apr 29, 2016 at 4:59
  • Related query: stackoverflow.com/questions/2933758/… Hope this helps :) Commented Apr 29, 2016 at 4:59

1 Answer 1

Reset to default
1

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:

  1. Store your elements in a set<int> which gives you *begin() and *rbegin() to get the min and max values.
  2. 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.
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

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: 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.
"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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.