В Smalltalk вы можете создать sortedCollection, что означает, что вы можете добавить элемент и вставить его в нужное место.
Есть ли что-нибудь подобное в С++? Или еще лучше есть что-то вроде sortedQueue, так что когда вы добавляете элемент, он сортирует его в структуру, похожую на очередь, которую вы можете просто вынуть из первого элемента?
Я искал набор, это то, что мне нужно с точки зрения сортировки, но это неупорядоченная коллекция. Я ищу небольшое время работы, насколько это возможно.
Кажется, вы ищете std::priority_queue, который находится в заголовочном файле <queue>. С помощью push() вы можете вставить элемент в очередь приоритетов; с top() вы получите самый большой элемент в очереди (или самый маленький из них, в зависимости от того, как вы реализуете operator<); и с помощью pop() вы удалите самый большой/наименьший элемент.
Насколько я знаю, он реализован с помощью кучи, что делает сложность времени каждой операции push и pop O (lg n). Просто смотреть на верхний элемент выполняется в O (1).
В стандартной библиотеке С++ имеется четыре сортированных контейнера:
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 затем предоставит вам очередь с самыми старыми людьми спереди.
Блок-схема выбора контейнера STL (из этого вопроса):
std:: map для отсортированного контейнера
std:: queue для очереди.
std:: priority_queue для отсортированной очереди
std::set - упорядоченная коллекция; итерация по ней даст вам элементы по порядку (как определено оператором <, так и пользовательским предикатом). Поиск и удаление первого элемента - O (1).
В качестве альтернативы вы можете использовать std::priority_queue, который в основном представляет собой кучу и позволяет эффективно вставлять и удалять наименьшие элементы.
На самом деле сложнее найти неупорядоченные (хэшированные) контейнеры - они не были частью исходного стандарта, хотя они были широко доступны в нестандартной форме.
Конечно, вы можете обнаружить, что просто держать ваши элементы в отсортированном векторе быстрее, даже если это теоретически медленнее, если количество элементов не значительно велико.