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).