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

Ответ 1

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

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

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

Ответ 2

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

std::map<keyType, valueType>

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

Или

std::set<valueType>

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

Там же

std::multiset<valueType>

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

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

Кроме того, как упоминалось в 17 из 26, эффективный Stl by Meyers заслуживает внимания.

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

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

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

помните, что преждевременно не оптимизируйте...

Ответ 9

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

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

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

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

Ответ 10

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

Ответ 11

Карты и множества STL - это сортированные контейнеры.

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

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

Ответ 12

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