Вызов clear()
на векторе вызовет деструкторы того, что хранится в векторе, что является линейной операцией времени. Но это тот случай, когда вектор содержит примитивные типы, такие как int
или double
?
Является ли `std::vector <primitive>:: clear()` постоянной операцией времени?
Ответ 1
Я считаю, что ответ зависит от реализации. Это занимает не более линейного времени, но некоторые реализации могут решить оптимизировать это.
Per 'Является ли очистка вектора влиять на его емкость?', ни MSVC, ни g++ не уменьшают емкость их векторов, даже когда вызывается .clear
. Глядя на заголовки g++, очевидно, что .clear
является постоянным временем с распределителем по умолчанию, если элементы являются скалярными (примитивные арифметические типы или указатели).
Ответ 2
Подумайте об этом из POV о том, как возможно реализовать vector
. Когда вы вызываете:
delete [] internalPtr;
Что происходит?
- Куча должна вернуть непрерывный блок пространства
- деструкторы должны запускать или каждый объект в innerPtr
Первое должно существовать для примитивных типов, но деструкторов для них не существует. Таким образом, delete[]
будет выполняться полностью на основе того, как быстро куча может удалить блок памяти
Ответ 3
В этой ссылке:
http://www.cplusplus.com/reference/vector/vector/clear/
Он говорит, что сложность clear()
является линейной по размеру (разрушениям).
Ответ 4
Ну.. он говорит, что clear() является линейным, но мы также знаем, что он вызывает деструктор каждого элемента...
http://www.cplusplus.com/reference/vector/vector/clear/
Что делать, если вызов деструктора не является линейным?
Однако, в примитивах деструктор-вызов является линейным (или постоянным, это не важно, если оно не более чем линейное)
так да, на примитивах ясно() всегда линейная операция