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

StackOverflow https://stackoverflow.com/questions/67426

  •  09-06-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

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

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

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

Другие советы

Вам нужно посмотреть std::map

std::map<keyType, valueType>

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

Или 

std::set<valueType>

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

Есть

std::multiset<valueType>

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

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

Кроме того, как упоминалось в 17 из 26, стоит прочитать «Эффективный Stl» Мейерса.

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

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

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

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

std::set по сути представляет собой отсортированный контейнер.

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

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

теоретически ассоциативный контейнер (набор, мультимножество, карта, мультикарта) должен быть вашим лучшим решением.

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

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

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

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

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

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

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

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

Карты и наборы STL представляют собой отсортированные контейнеры.

Я поддерживаю рекомендацию книги Дуга Т. Книга Джосуттиса STL — лучшее, что я когда-либо видел, как учебное, так и справочное издание.

Эффективный STL это также отличная книга для изучения внутренних деталей STL и того, что следует и не следует делать.

Для «совместимого с STL» отсортированного вектора см. A.AssocVector Александреску из Локи.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top