Динамически отсортированные контейнеры STL

Question

Я довольно новичок в STL, поэтому мне было интересно, есть ли какие-нибудь динамически сортируемые контейнеры? В настоящее время мое текущее мышление состоит в том, чтобы использовать вектор в сочетании с различными алгоритмами сортировки, но я не уверен, существует ли более подходящий выбор с учетом (предположительно) линейной сложности вставки записей в отсортированный вектор.

Чтобы уточнить "динамически", я ищу контейнер, в котором я могу изменить порядок сортировки во время выполнения - например, отсортировать его в порядке возрастания, а затем повторно отсортировать в порядке убывания.

Answer 1

Вы захотите посмотреть на std :: map

std::map<keyType, valueType>

Карта отсортирована на основе оператора <, предусмотренного для keyType. </p>

или

std::set<valueType>

Также сортируется по оператору <аргумента шаблона, но не допускает дублирование элементов. </p>

Там в

std::multiset<valueType>

, который делает то же самое, что и std :: set, но допускает идентичные элементы.

Я настоятельно рекомендую Josuttis «Стандартную библиотеку C ++» для получения дополнительной информации. Это наиболее полный обзор библиотеки std, очень читабельный, и полон неясной и не очень темной информации.

Кроме того, как упоминалось 17 из 26, Effective Stl от Meyers стоит прочитать.

Answer 2

Если вы знаете, что будете сортировать по одному значению по возрастанию и по убыванию, тогда set is your friend. Используйте обратный итератор, если хотите «отсортировать» в обратном направлении.

Если ваши объекты сложны, и вы собираетесь сортировать различными способами на основе полей-членов в объектах, то вам, вероятно, лучше использовать вектор и сортировку. Попробуйте сделать все вставки сразу, а затем вызовите сортировку один раз. Если это невозможно, то для больших коллекций объектов может быть лучше использовать deque, чем vector.

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

Answer 3

Звучит так, как будто вы хотите многоиндексный контейнер . Это позволяет вам создать контейнер и указать этому контейнеру, каким образом вы можете проходить через него элементы. Затем контейнер хранит несколько списков элементов, и эти списки обновляются при каждой вставке / удалении.

Если вы действительно хотите пересортировать контейнер, вы можете вызвать функцию std::sort для любого std::deque, std::vector или даже простого массива в стиле C. Эта функция принимает необязательный третий аргумент, чтобы определить, как сортировать содержимое.

Answer 4

stl не предоставляет такой контейнер. Вы можете определить свой собственный, опираясь либо на set/multiset, либо на vector, но вам придется пересортировать каждый раз, когда изменяется функция сортировки, вызывая sort (для vector) или создание новой коллекции (для set/multiset).

Если вы просто хотите перейти от увеличения порядка сортировки к уменьшению порядка сортировки, вы можете использовать обратный итератор для своего контейнера, вызывая rbegin() и rend() вместо begin() и end(). И vector, и set/multiset являются обратимыми контейнерами, так что это подойдет и для любого из них.

Answer 5

std::set в основном отсортированный контейнер.

Answer 6

Set и MultiSet используют базовое двоичное дерево; Вы можете определить оператор <= для собственного использования. Эти контейнеры сохраняют свою сортировку, поэтому может быть не лучшим выбором, если вы переключаете параметры сортировки. Векторы и списки, вероятно, лучше всего подходят, если вы собираетесь прибегать к ним совсем немного; В общем, список имеет свою сортировку (обычно сортировку слиянием), и вы можете использовать алгоритм двоичного поиска stl по векторам. Если вставки будут доминировать, список превосходит вектор. </p>

Answer 7

Ответ, как всегда, зависит.

set и multiset подходят для сортировки предметов, но обычно оптимизированы для сбалансированного набора операций добавления, удаления и выборки. Если у вас есть мужественные операции поиска, то сортированный vector может быть более подходящим, а затем используйте lower_bound для поиска элемента.

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

Поэтому я бы порекомендовал отсортированный вектор. Но не забудьте передать тот же предикат в lower_bound, который вы передали в предыдущую сортировку, поскольку результаты будут неопределенными и, скорее всего, ошибочными, если вы передадите неверный предикат.

Answer 8

теоретически лучшим решением должно быть ассоциативное хранилище (set, multiset, map, multimap).

На практике это зависит от среднего количества элементов, которые вы вводите. для менее чем 100 элементов вектор, вероятно, является лучшим решением из-за: - избегая непрерывного распределения-освобождения - дружественный кэш благодаря локальности данных эти преимущества, вероятно, будут превосходить непрерывную сортировку. Очевидно, это также зависит от того, сколько вставки-удаления вам нужно сделать. Собираетесь ли вы делать вставку / удаление для каждого кадра?

В более общем плане: вы говорите о приложении, критичном к производительности?

не забывайте преждевременно оптимизировать ...

Answer 9

Это не так просто. По моему опыту вставка / удаление используется реже, чем поиск. Преимущество отсортированного вектора в том, что он занимает меньше памяти и более кэш-дружественен. Если у вас есть версия, совместимая с картами STL (например, та, которую я связал ранее), то легко переключаться назад и вперед и использовать оптимальный контейнер для каждой ситуации.

Answer 10

Вы обязательно должны использовать набор / карту. Как говорит Хаззен, вы получаете O (log n) insert / find. Вы не получите это с отсортированным вектором; вы можете получить O (log n) find с помощью бинарного поиска, но вставка - это O (n), потому что вставка (или удаление) элемента может привести к смещению всех существующих элементов в векторе.