std :: vector & lt; int & gt; :: clear, постоянное время?

Возможный дубликат:
В чем сложность std :: vector<T>:: clear () когда T является примитивным типом?

Если у меня есть std::vector с примитивным типом, и я называю clear() (сюда push_back начинается в начале capacity), это clear() вызов будет завершен в постоянное или линейное время? Документация гласит, что уничтожает все элементы, но если элемент имеет тип int, уничтожать нечего, верно?


редактировать:
Я нашел дубликат с плакатом, который подробно объясняет, что реализация может проверить, тривиален ли деструктор, и приводит пример одного компилятора, который имеет эту проверку (GCC).

В чем сложность std :: vector<T>:: clear () когда T является примитивным типом?

6

Решение

Это зависит от того, как реализован вектор, но от массива объектов с тривиальными деструкторами (который включает в себя POD, такие как встроенные целочисленные типы, такие как int) должна быть в состоянии безопасно быть освобождена с помощью одного звонка vector<T>::allocator_type::deallocate без зацикливания элементов и индивидуального вызова деструкторов. Реализация std::vector можешь использовать type_traits или внутренности компилятора, чтобы определить, T имеет тривиальный деструктор, и соответственно освобождает внутренний массив. Вам нужно будет проверить исходный код вашей реализации, чтобы выяснить, что она делает, но большинство основных реализаций std::vector даст вам освобождение в постоянное время для типов с тривиальными деструкторами (или, по крайней мере, постоянное время для целочисленных типов и других POD).

3

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

Стандарт не дает никаких гарантий относительно сложности std::vector::clearхотя вы ожидаете, что операция будет линейной по размеру контейнера для сложных типов элементов и постоянной для POD.

2

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