Хранение в std :: map / std :: set против сортировки вектора после сохранения всех данных

Question

• Язык: C ++

• Одна вещь, которую я могу сделать, это выделить вектор размером n и сохранить все данные и затем сортируйте его, используя sort (begin (), end ()). Остальное могу поставить данные на карте или в наборе, которые упорядочены сами по себе, поэтому мне не нужно сортировать потом. Но в этом случае вставка элемента может быть более дорого из-за перестановок (наверное).

  Итак, что является оптимальным выбором за минимальное время для широкого диапазона n (количество объектов)

Answer 1

Разница между 2 заметна!

Используя набор, вы получаете O(log(N)) сложность для каждого вставляемого элемента. Таким образом, в результате вы получаете O(N log(N)), что является сложностью вставки сортировки.

Добавление всего в вектор имеет сложность O(1), и сортировка будет O(N log(N)) начиная с C ++ 11 (до этого std::sort имеет O(N log(N)) в среднем.). После сортировки вы можете использовать binary_search, чтобы иметь ту же сложность, что и в наборе.

API использования вектора в качестве набора не очень удобен, хотя он дает хорошие преимущества в производительности. Это, конечно, полезно, только когда вы можете выполнить массовую вставку данных или когда количество поисков намного больше, чем манипуляции с контентом. Алгоритм сортировки по частично отсортированному вектору, когда вам придется расширяться позже. Наконец, нужно отметить, что у вас нет таких же гарантий аннулирования итераторов.

Итак, почему векторы лучше? Локальный кеш! Вектор имеет все данные в одном блоке памяти, поэтому процессор может выполнять предварительную выборку, в то время как для набора память разбросана по месту, требующему данные, чтобы найти следующий адрес. Это делает вектор лучшей реализацией набора, чем std :: set для больших данных, когда вы можете жить с ограничениями.

Чтобы дать вам представление о кодовой базе, над которой я работаю, у нас есть несколько реализаций set и map, основанных на векторах, которые имеют свои собственные нарративы для работы. (Например: нет стирания или нет оператора [])

Answer 2

Зависит от ситуации.

map и set являются обычно красно-черными деревьями, они должны выполнять большую работу, чтобы быть сбалансированными, иначе работа над ним будет очень медленной. И он не поддерживает произвольный доступ . поэтому, если вы хотите отсортировать только один раз, вы не должны их использовать.

Но, если вы хотите продолжить вставлять элементы в контейнер и поддерживать порядок, map и set займут O(logN) время, а отсортированный vector будет O(N). Последнее намного медленнее, поэтому, если вы хотите часто вставлять и удалять , вы должны использовать map или set.