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

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

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

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

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

Ответ 1

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

Ответ 2

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

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

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

Ответ 3

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

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

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