Are there any Sorted Collections in C++?

Question

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.

Answer 1

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.

Answer 2

The STL container choice flowchart (from this question):