Есть ли отсортированные коллекции в C ++? - PullRequest
Новая
       9

Есть ли отсортированные коллекции в C ++?

19 голосов
/ 27 июня 2011

В Smalltalk вы можете создать sortedCollection, то есть вы можете добавить элемент, и он вставит его в правильное местоположение.

Есть ли что-нибудь подобное в C ++?Или, что еще лучше, есть что-то вроде sortedQueue, такое, что когда вы добавляете элемент, он сортирует его в структуру, похожую на очередь, из которой вы можете просто извлечь первый элемент?

Я смотрел в set,это то, что мне нужно с точки зрения сортировки, но это неупорядоченная коллекция.Я ищу небольшой пробег, насколько это возможно.

Ответы [ 5 ]

53 голосов
/ 27 июня 2011

В стандартной библиотеке C ++ есть четыре отсортированных контейнера:

std::set - отсортированная последовательность уникальных значений.
std::map -Сортированная последовательность уникальных пар ключ / значение.
std::multiset - отсортированная последовательность значений (возможные повторы).
std::multimap - отсортированная последовательностьпары ключ / значение (возможные повторы).

Если вы просто хотите отсортированную очередь, то вы ищете std::priority_queue, то есть контейнерный адаптер вместо автономного контейнера. 

#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;
}

Если вы хотите хранить свои собственные типы в priority_queue, тогда вам нужно определить operator< для вашего класса. 

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;
};

Создание priority_queue из Person s даст вам очередь с самыми старыми людьми впереди.

51 голосов
/ 27 июня 2011

Блок-схема выбора контейнера STL (из этот вопрос):

image

20 голосов
/ 27 июня 2011

Вы, похоже, ищете std::priority_queue, который находится в заголовочном файле <queue>.С push() вы можете вставить элемент в очередь с приоритетами;с top() вы получите самый большой на данный момент элемент в очереди (или самый маленький, в зависимости от того, как вы реализуете operator<);а с pop() вы удалите самый большой / самый маленький элемент.

Насколько я знаю, он реализован с кучей, которая делает сложность времени каждой операции push и pop O (lgп) .Просто смотреть на верхний элемент можно в O (1) .

7 голосов
/ 27 июня 2011

std :: map для отсортированного контейнера

std :: queue для очереди.

std :: priority_queue для отсортированной очереди

2 голосов
/ 27 июня 2011

std::set - упорядоченная коллекция;итерация по нему даст вам элементы в порядке (как определено оператором < или пользовательским предикатом).Поиск и удаление первого элемента - это O (1).

В качестве альтернативы вы можете использовать std::priority_queue, который в основном представляет собой кучу и позволяет эффективно вставлять и удалять наименьшее количество элементов.

На самом деле это сложнеечтобы найти неупорядоченные (хешированные) контейнеры - они не были частью исходного стандарта, хотя они были широко доступны в нестандартной форме.

Конечно, вы можете обнаружить, что простое хранение ваших предметов в отсортированном векторебыстрее, даже если теоретически он медленнее, если количество предметов невелико.

...