Является ли `std :: vector & lt; primitive & gt; :: clear ()` операцией с постоянным временем?

призвание clear() на вектор вызовем деструкторы того, что хранится в векторе, который является линейной временной операцией. Но так ли это, когда вектор содержит такие примитивные типы, как int или же double?

11

Решение

Я считаю, что ответ зависит от реализации. Занимает в большинстве линейное время, но некоторые реализации могут решить оптимизировать это.

Per ‘Влияет ли очистка вектора на его емкость?‘, ни MSVC, ни G ++ не уменьшают емкость своих векторов, даже когда .clear называется. Глядя на заголовки G ++, видно, что .clear постоянное время с распределителем по умолчанию, если элементы являются скалярными (примитивные арифметические типы или указатели).

4

Другие решения

Подумайте об этом от POV о том, как vector скорее всего реализовано. Когда вы вызываете:

 delete [] internalPtr;

Что просходит?

  • Куча должна вернуть непрерывный блок пространства
  • деструкторы должны срабатывать или каждый объект в internalPtr

Первое должно произойти для примитивных типов, но деструкторы для них не существуют. Так delete[] будет выполняться исключительно на основании того, как быстро куча может удалить блок памяти

2

По этой ссылке:

http://www.cplusplus.com/reference/vector/vector/clear/

Это говорит о сложности clear() является линейным по размеру (разрушения).

0

Ну … это говорит о том, что clear () является линейной, но мы также знаем, что она вызывает деструктор каждого элемента …

http://www.cplusplus.com/reference/vector/vector/clear/

Что если вызов деструктора не является линейным?

Однако в примитивах вызов деструктора является линейным (или постоянным, это не важно, если оно не более чем линейное)

так что да, на примитивах понятно () всегда линейная операция

0
По вопросам рекламы [email protected]