производительность — C ++ самый быстрый способ очистить или стереть вектор
У меня есть код, где я обычно заполняю вектор от 0 до 5000 элементов. Я знаю, что максимум никогда не превышает 5000. Вместо того, чтобы инициализировать вектор несколько раз, я хотел бы сделать только один раз
vector<struct> myvector;
myvector.reserve(5000);
Однако, чтобы снова заполнить вектор, мне нужно сначала очистить вектор, не меняя его емкости. Поэтому обычно я вызываю myvector.clear ();
Это операция O (n). Есть ли что-то простое, что я могу сделать, чтобы повысить производительность этого или это лучшее из того, что он получит?
Решение
Если ваша структура имеет нетривиальный деструктор, то это нужно вызывать для всех элементов вектора, независимо от того, как он очищается. Если ваша структура имеет только тривиальный деструктор, компилятор или реализация стандартной библиотеки могут оптимизировать процесс уничтожения и дать вам операцию O (1).
Другие решения
Цена clear() сильно зависит от того, что хранятся объекты, и, в частности, есть ли у них тривиальный деструктор. Если у типа нет тривиального деструктора, то вызов должен уничтожить все сохраненные объекты, и на самом деле это операция O (n), но вы не можете сделать что-то лучше.
Теперь, если хранимые элементы имеют тривиальные деструкторы, реализация может оптимизировать затраты и clear() становится дешевой операцией O (1) (просто сброс размера —end указатель).
Помните, что для понимания асимптотической сложности вам нужно знать, о чем идет речь. В случае clear() он представляет количество вызванных деструкторов, но если стоимость (скрытая) равна 0, то операция не выполняется.
Все, что вы делаете для удаления существующих элементов из вектора, должно (потенциально) вызывать деструктор каждого уничтожаемого элемента. Поэтому, с точки зрения контейнера, лучшее, на что вы можете надеяться, это линейная сложность.
Это оставляет только вопрос о том, какие элементы вы храните в векторе. Если вы храните что-то вроде int что компилятор может / будет знать заранее, что не имеет деструктора, который можно вызвать, шансы, по крайней мере, довольно хорошие, что удаление будет иметь постоянную сложность.
Я сомневаюсь, однако, что изменение синтаксиса (например, clear() против resize() против erase(begin(), end()) ) будет иметь какое-либо существенное значение. Синтаксис не меняет того факта, что (при отсутствии потоков) вызов N деструкторов является операцией O (N).
detector