Jim Jim - 7 months ago 42
C++ Question

Are there any Sorted Collections in C++?

In Smalltalk, you can create a sortedCollection, which is to say that you can add an element and it would insert it into the correct location.

Is there anything like this in C++? Or even better is there anything like a sortedQueue, such that when you add an element, it would sort it into a queue like structure that you can just pop the first element off of?

I looked into set, this is what I need in terms of sorting, but it is an unordered collection. I am looking for a small run time as possible.


You seem to be looking for the std::priority_queue, which is located in the <queue> header file. With push(), you can insert an element into the priority queue; with top(), you will get the currently largest element in the queue (or the smallest one, depending on how you implement operator<); and with pop(), you will remove the largest/smallest element.

As far as I know, it's implemented with a heap, which makes the time complexity of each push and pop operation O(lg n). Simply looking at the top element is done in O(1).