Нужен совет, чтобы выбрать подходящий контейнер

Question

Я пытаюсь спроектировать планировщик задач для игрового движка. Задачей может быть анимация, контроллер триггера и т. Д.

Моя проблема в том, какой контейнер выбрать. Идея такова: когда вы вставляете новую задачу, контейнер должен изменить порядок и поместить задачу в нужное место. После выполнения задача может быть изменена и может быть снова запланирована или удалена. В основном это push и pop.

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

Я думаю, что очередь с приоритетами соответствует моим потребностям, но я видел, что она основана на векторной реализации, и я думаю, что этот контейнер должен быть каким-то образом оптимизирован для push и pop.

Мнения

Answer 1

Контейнеры http://adrinael.net/containerchoice

(первоисточник: Лиам Девайн )

Answer 2

A приоритетная очередь кажется лучшим вариантом для вас.

Как видите, функции pop имеют постоянную сложность, а функция push является логарифмической по времени.

Answer 3

std :: vector довольно хорош для этой задачи, особенно если «устойчивый» размер контейнера остается достаточно постоянным (количество задач в очереди не сильно отличается).

Если вам нужна обновляемая очередь (а std :: priority_queue нет), я бы посоветовал вам использовать d_ary_heap_indirect (который находится в папке Boost.Graph «detail»).Это приоритетная очередь, часто используемая для алгоритмов Dijkstra и A *, которые требуют обновляемой приоритетной очереди.В любом случае необходим произвольный доступ.Кроме того, использование косвенной функции делает вставку и удаление из очереди весьма эффективными.Наконец, вы можете выбрать свой контейнер (в качестве аргумента шаблона), но он должен иметь произвольный доступ (так что вы можете попробовать вектор или deque).Pop - это постоянное время, push и / или update - время журнала, и правильный выбор контейнера сделает вставку контейнера постоянной амортизированной (и d_ary_heap_indirect также амортизируется во второй раз, так что я не буду об этом беспокоиться),

Answer 4

Зависит от того, как часто вы будете добавлять задачи и выполнять задачи (и, вероятно, выполнять их) и сколько их будет.

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

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

Планирование - это искусство, и вам придется его профилировать, как только вы его построите.Там, наверное, слишком мало информации, так сказать.Я бы склонялся к приоритетной очереди, но учел бы другие варианты, если производительность не адекватна.

Answer 5

Вы можете указать желаемый тип контейнера с помощью std::priority_queue. Тем не менее: вы храните указатели (я полагаю, так как это звучит, как вы полиморфный и имеет идентичность), поэтому копирование обходится дешево. Вы управляете этим как куча (это то, что делает std::priority_queue), поэтому вставки сделаны используя push_back и количество перестановок (lg (n) max). Я не вижу ни одного причина даже рассмотреть другую структуру, чем std::vector.

std::priority_queue скрывает всех операторов прямого доступа (например, operator[]). Это происходит потому, что если вы измените запись, вы вероятно, сделает недействительной кучу (которая является инвариантом класса). Однако если вы хотите предоставить прямой доступ для чтения, контейнер только protected, а не private, так что вы можете извлечь из него и добавьте операторов, которые вы хотите. Я бы очень ограничился этим const операторы, однако.

Answer 6

Вектор оптимизирован для push и pop на одном конце. : -)

Для расстановки приоритетов вам придется отсортировать задания. Вектор не так уж и плох, если количество объектов достаточно мало, даже если это означает копирование объектов во время сортировки.

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