являются контейнерами STL .push_back ()

Question

Это может показаться глупым, из-за чего я извиняюсь, я написал немного кода для Playstation 2 для универа.Я пишу своего рода API для графического синтезатора.Я использую синтаксис, сходный с синтаксисом openGL, который является конечным автоматом.

Таким образом, ввод будет выглядеть примерно так:

gsBegin(GS_TRIANGLE);

gsColor(...);
gsVertex3f(...);
gsVertex3f(...);
gsVertex3f(...);

gsEnd();

На данный момент это отлично подходит для линий / треугольников / квадратов с определенным количеством вершин, однако такие вещи как LINE_STRIP или TRIANGLE_FANвзять неопределенное количество очков.Меня несколько раз предупреждали об использовании контейнеров stl из-за метода push_back () в этой ситуации из-за чувствительности ко времени (оправдано ли это).

Если это не оправдано, что будет лучшим способомиметь дело с неопределенным количеством ситуации.В настоящее время у меня есть массив, который может содержать 30 вершин одновременно, это лучший способ справиться с такой ситуацией?

Answer 1

Вектор push_back амортизировал сложность с постоянным временем, потому что он экспоненциально увеличивает емкость вектора.(Я предполагаю, что вы используете vector, потому что он идеально подходит для этой ситуации.) Однако на практике рендеринг кода очень чувствителен к производительности, поэтому, если push_back вызывает перераспределение вектора, производительность может снизиться.

Вы можете предотвратить перераспределение, резервируя емкость перед ее добавлением.Если вы наберете myvec.reserve(10);, вы гарантированно сможете добавить 10 элементов до того, как вектор будет перераспределен.

Однако для этого все же необходимо заранее знать, сколько элементов вам нужно.Кроме того, если вы создаете и уничтожаете множество различных векторов, вы все равно занимаете много памяти.Вместо этого просто используйте one vector для всех вершин и используйте его повторно.Вызов clear() возвращает его пустым , сохраняя выделенную ему емкость .Таким образом, вам на самом деле не нужно ничего резервировать - первые несколько раз, когда вы его используете, он будет перераспределяться и расти, но как только он достигнет своего пикового размера, ему больше не нужно будет перераспределять.Приятно то, что вектор находит приблизительный размер, который ему нужен, и как только он «подогревается», дальнейшее распределение отсутствует, поэтому это высокая производительность.

Короче говоря:

• Используйте один постоянно сохраненный std::vector
• push_back столько, сколько хотите
• Когда вы закончите, clear().

Inна практике это будет работать так же хорошо, как и массив C, но без жесткого ограничения на размер.

Answer 2

Университет, а?Просто скажите им, что push_back имеет амортизированную сложность с постоянным временем , и они будут счастливы.

Answer 3

Всегда есть альтернатива использования deque.

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

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

Существует также альтернатива LLVM: SmallVector<T,N>, которая предварительно выделяет (прямо в векторе) пространство для N элементов и просто вернется к использованию традиционной векторной реализации, когда размер слишком сильно увеличится.

Answer 4

Во-первых, избегайте использования glBegin / glEnd, если можете, и вместо этого используйте что-то вроде glDrawArrays или glDrawElements.

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

Answer 5

Вы всегда можете оснастить контейнер, который вы хотите использовать, соответствующим распределителем, который учитывает ограничения платформы и ожидаемые сценарии роста / сжатия и т. Д. *

Answer 6

Недостатком использования std::vector в такой ситуации является обеспечение правильного управления распределением памяти.В таких системах, как PS2 (PS3 кажется немного лучше в этом), выделение памяти происходит безумно медленно, и если вы не зарезервируете нужное количество места в векторе для начала (и при добавлении необходимо несколько раз изменить размерпредметы), вы замедлите свою игру до ползучего ползания.Если вы знаете, какой будет ваш максимальный размер, и зарезервируйте его при создании вектора, у вас не возникнет проблем.

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