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 wha开发者_StackOverflow中文版t I need in terms of sorting, but it is an unordered collection. I am looking for a small run time as possible.

---

There are four sorted containers in the C++ standard library:

std::set - A sorted sequence of unique values.
std::map - A sorted sequence of unique key/value pairs.
std::multiset - A sorted sequence of values (possible repeats).
std::multimap - A sorted sequence of key/value pairs (possible repeats).

If you just want a sorted queue, then what you are looking for is std::priority_queue, which is a container adaptor rather than a stand-alone container.

#include <queue>

int main()
{
    std::priority_queue<int> q;
    q.push(2);
    q.push(3);
    q.push(1);
    assert(q.top() == 3); q.pop();
    assert(q.top() == 2); q.pop();
    assert(q.top() == 1); q.pop();
    return 0;
}

If you want to store your own types in a priority_queue then you need to define operator< for your class.

class Person
{
public:
    Person(int age) : m_age(age) {}

    bool operator<(const Person& other) const
    {
        return m_age < other.m_age;
    }

private:
    int m_age;
};

Creating a priority_queue of Persons would then give you a queue with the oldest people at the front.

---

The STL container choice flowchart (from this question):

---

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

---

std::map for sorted container

std::queue for queue.

std::priority_queue for sorted queue

---

std::set is an ordered collection; iterating over it will give you the elements in order (either as defined by the < operator or a custom predicate). Finding and removing the first element are O(1).

Alternatively you could use std::priority_queue, which is basically a heap and allows efficient insert and least item removal.

In fact it's harder to find unordered (hashed) containers - they weren't part of the original standard, although they were widely available in non-standard form.

Of course you may find that simply holding your items in a sorted vector is faster, even if it is theoretically slower, if the number of items is not significantly large.