Контейнер STL, скорость создания / разрушения - PullRequest
Новая
       8

Контейнер STL, скорость создания / разрушения

0 голосов
/ 23 июня 2011

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

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

Таким образом, вопрос: Какой контейнер ((STL или нет) [предпочтительно первый]) дает мне самое быстрое (порядок не имеет значения) добавление, удаление и произвольный доступ к элементам?

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

Дополнительная информация: по сути, я делю свой экран на сетку неопределенного размераи когда объект перемещается, я собираюсь найти квадрат, в котором в данный момент находится верхний левый угол, а затем нижний правый угол (при условии, что объект, конечно, квадратный), поэтому я буду знать все текущие позиции сетки, занимаемые объектом.Когда я выполняю обнаружение столкновений, я выполняю только проверки позиций сетки с более чем одним объектом, когда я проверяю на наличие столкновений , надеюсь, это будет намного быстрее, чем в моей предыдущей системе =]

Ответы [ 2 ]

2 голосов
/ 23 июня 2011

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

Подумайте о том, чтобы придерживаться std::vector: он предлагает постоянное-временный произвольный доступ ко всем элементам в последовательности и постоянное время вставки и удаления в конце последовательности.

Поскольку вы говорите, что порядок не имеет значения, вы также можете получить постоянное удаление любого элементаот середины последовательности, перемещая элемент от конца последовательности, чтобы он заменил удаляемый элемент;как то так: 

void remove_element(std::vector<Entity>& v, std::vector<Entity>::iterator it)
{
    std::vector<Entity>::iterator last_element_it = v.end() - 1;
    if (it != last_element_it) {
        using std::swap;
        swap(*it, *last_element_it);
    }
    v.erase(last_element_it);
}
1 голос
/ 23 июня 2011

Какой контейнер ((STL или нет) [предпочтительно первый]) дает мне самое быстрое (порядок не имеет значения) добавление, удаление и произвольный доступ к элементам?

Никто из них. Вы должны выбрать, какие вещи вы хотите.

Добавление конца к вектору std :: vector также быстро, как и удаление с конца. Но вставка / удаление в другом месте повредит, по крайней мере, несколько.

Вставка и удаление из списка std :: list будет очень быстрым независимо от того, где, но нет произвольного доступа.

В std :: deque есть вставка и удаление в стиле std :: vector, как в начале, так и в конце, и он имеет произвольный доступ.

У меня такой вопрос: как часто вам нужен произвольный доступ к списку объектов столкновений? Не будет ли большая часть ваших операций повторяться по списку (для каждого объекта делать X)? Если это так, я бы пошел на std :: list.

В качестве альтернативы, вы можете использовать std :: map, где ключ карты - это своего рода уникальный идентификатор объекта. Это даст вам более медленную вставку / удаление, чем std :: list (из-за необходимости сбалансированного двоичного дерева), но вы получите возможность доступа к сущности по идентификатору достаточно быстро. Что может быть важно.

Std :: map, вероятно, находится на полпути между std :: vector / deque и std :: list в этом отношении. Более медленная вставка / удаление, чем у списка, более медленный произвольный доступ, чем у вектора / очереди, но вы получаете некоторые из них.

При этом я очень сомневаюсь, что такого рода оптимизация будет очень полезна для вас. Сколько таких объектов у вас будет, может быть, несколько тысяч? Как часто вы их трогаете? Вы действительно думаете, что тип используемого вами контейнера будет значительным фактором в производительности вашей системы столкновений?

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

...