Are there any Sorted Collections in C++?

c++ sorting boost stl adt

40,654

Solution 1

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

Solution 2

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.

Solution 3

The STL container choice flowchart (from this question):

Solution 4

std::map for sorted container

std::queue for queue.

std::priority_queue for sorted queue

Solution 5

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.

View more solutions

40,654

Jim

Updated on November 19, 2020

Comments

Jim over 3 years

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.
- ildjarn almost 13 years
  
  "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.
- Nikolai Fetissov almost 13 years
  
  You are wrong, std::set is ordered.
- Node almost 13 years
  
  set is ordered, using std::less by default, so looping through myset.begin() to myset.end() will go through the elements in ascending order.
- Jim almost 13 years
  
  @ildjarn & @Fetissov I think I must have misread it then. Thank you for clarifying.
Jim almost 13 years

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?
littleadv almost 13 years

@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).
Jim almost 13 years

I think priority queue is exactly what I need, thanks. I dont think it was there when I made that comment.
Martin York almost 13 years

std::set for sorted container. Map is pair were the data is sorted by a separate key.
sergiol about 12 years

Even looking at this diagram I can't say what would be the best one to use in my quastion stackoverflow.com/questions/9329011/…
MaMazav over 8 years

Great chart! but link became broken. Anyway here is updated version for C++11: stackoverflow.com/a/22671607/3052438