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

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

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

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

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

Вы захотите посмотреть на станд.:: карта

std::map<keyType, valueType>

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

Или

std::set<valueType>

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

Существует

std::multiset<valueType>

который делает то же самое как станд.:: набор, но позволяет идентичные элементы.

Я высоко reccomend "Библиотека Стандарта C++" Josuttis для получения дополнительной информации. Это - самый всесторонний обзор библиотеки станд., очень читаемой, и переполненной неясной и not-so-obscure информацией.

Кроме того, как упомянуто 17 из 26, Эффективный Stl Meyers стоит чтения.

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

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

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

Я вторая книжная рекомендация T Doug - книга STL Josuttis является лучшей, я когда-либо видел и как изучение и как справочник.

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

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

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

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

помните к не, преждевременно оптимизируют...

Для "STL совместимый" отсортированный вектор см. A. AssocVector Alexandrescu от Loki.

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

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

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

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

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