C++ быстрый способ очистки или стирания вектора

Question

У меня есть код, в котором я обычно заполняю вектор между 0 и 5000 элементами. Я знаю, что максимум не превышает 5000. Вместо инициализации вектора несколько раз, я хотел бы сделать только один раз

vector<struct> myvector; 
myvector.reserve(5000); 

Однако, чтобы заполнить вектор снова, я должен очистить вектор первый, не изменяя его емкость. Поэтому обычно я вызываю myvector.clear();

Это операция O (n). Есть ли что-то простое, что я могу сделать, чтобы повысить производительность этого или это самое лучшее, что он получит?

Answer 1

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

Answer 2

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

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

Я сомневаюсь, однако, что изменение синтаксиса (например, clear() против resize() против erase(begin(), end())) приведет к каким-либо существенным различиям вообще. Синтаксис не изменяет тот факт, что (при отсутствии потоковой передачи), вызывающий N деструкторов, является операцией O (N).

Answer 3

Стоимость clear() зависит от того, что хранятся в объектах, и в частности, имеет ли они тривиальный деструктор. Если тип не имеет тривиального деструктора, то вызов должен уничтожить все сохраненные объекты, и на самом деле это операция O (n), но вы ничего не можете сделать лучше.

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

Помните, что для понимания асимптотической сложности вам нужно знать, о чем она говорит. В случае clear() он представляет собой количество вызываемых деструкторов, но если стоимость (скрытая) равна 0, то операция является no-op.