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

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

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

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

Ответы

Ответ 1

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

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

Ответ 2

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

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 затем предоставит вам очередь с самыми старыми людьми спереди.

Ответ 3

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

kQnCS.png

Ответ 5

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

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

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

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