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.

"*I looked into set, this is what I need in terms of sorting, but it is an unordered collection*" Huh? `set` is ordered, `unordered_set` isn't. — ildjarn, Jun 27 '11 at 19:50
`set` is ordered, using `std::less` by default, so looping through `myset.begin()` to `myset.end()` will go through the elements in ascending order. — Node, Jun 27 '11 at 19:54
@ildjarn & @Fetissov I think I must have misread it then. Thank you for clarifying. — Jim, Jun 27 '11 at 19:59

Peter Alexander · Answer 1 · 2011-06-27T19:57:08.887

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.

score 54 · Answer 2 · edited May 23 '17 at 10:31

54

The STL container choice flowchart (from this question):

edited May 23 '17 at 10:31

Community

1
1

answered Jun 27 '11 at 19:56

Igor

26,650
27
89
114

1

Even looking at this diagram I can't say what would be the best one to use in my quastion http://stackoverflow.com/questions/9329011/mfc-dictionary-collection-with-key-unicity-and-ordering-by-position – sergiol Feb 24 '12 at 19:30
3

Great chart! but link became broken. Anyway here is updated version for C++11: http://stackoverflow.com/a/22671607/3052438 – MaMazav Aug 12 '15 at 11:10

Aasmund Eldhuset · Accepted Answer · 2013-04-24T11:36:13.873

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

score 7 · Answer 4 · answered Jun 27 '11 at 19:48

7

std::map for sorted container

std::queue for queue.

std::priority_queue for sorted queue

answered Jun 27 '11 at 19:48

littleadv

20,100
2
36
50

Hmmm, I dont think map is what I am looking for. I might as well just use set, but there is nothing where they combine them into one adt? – Jim Jun 27 '11 at 19:52
1

@Jim - what is it that you need? *sortedQueue* as you described is `std::priority_queue`. I mentioned `map` because you asked for a general sorted container (at least that is what I understood from your discussion of *sortedCollection*). – littleadv Jun 27 '11 at 19:53
I think priority queue is exactly what I need, thanks. I dont think it was there when I made that comment. – Jim Jun 27 '11 at 19:57
std::set for sorted container. Map is pair were the data is sorted by a separate key. – Martin York Jun 27 '11 at 21:21

score 2 · Answer 5 · edited Nov 18 '16 at 20:56

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.

Are there any Sorted Collections in C++?

5 Answers5