std :: list или std :: multimap

Question

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

Мне бы хотелось услышать ваше мнение о том, что я должен использовать для этого инцидента.

Answer 1

std::multimap, вероятно, будет быстрее, так как это O (log n) на вставку, тогда как вставка и сортировка списка - O (n log n).

В зависимости от модели использования, вам может быть лучше использовать сортировку vector s. Если вы вставите сразу целую кучу элементов, а затем выполните несколько операций чтения, т. Е. Операции чтения и записи не будут чередоваться, вы получите лучшую производительность с vector, std::sort и std::binary_search.

Answer 2

Если вам не нужны пары ключ / значение, то std::set или std::multiset, вероятно, лучше, чем использование std::multimap.

Ссылка для std::set: http://www.cplusplus.com/reference/stl/set/

Ссылка для std::multiset: http://www.cplusplus.com/reference/stl/multiset/

Редактировать: (кажется, это было неясно раньше) Как правило, лучше использовать контейнер типа std::(multi)set или std:(multi)map, чем использовать std::list и сортировать его впоследствии каждый раз, когда вставляется элемент, поскольку std::list не очень хорошо выполняет вставку элементов в середине контейнера.

Answer 3

Вы можете рассмотреть возможность использования алгоритма lower_bound, чтобы найти место для вставки в ваш список. http://stdcxx.apache.org/doc/stdlibref/lower-bound.html

Редактировать: В свете комментария Нейла, обратите внимание, что это будет работать с любым контейнером последовательности (вектор, дек и т. Д.)

Answer 4

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

И list, и multimap избавят вас от необходимости перераспределять самих себя, просто добавляя элемент (как вы могли бы получить с вектором), поэтому в первую очередь вопрос того, сколько времени потребуется для вставки. Добавление в конец списка будет O (1), в то время как добавление в мультикарту будет O (log n). Однако мультикарта будет вставлять элементы в отсортированном порядке, в то время как если вы хотите отсортировать список, вам придется либо отсортировать список по O (n log n), либо вставить элемент отсортированным способом с помощью что-то вроде lower_bound, который будет O (n). В любом случае использовать список будет намного хуже (по крайней мере, в худшем случае).

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