Я понимаю, что сложность операции clear() является линейной по размеру контейнера, потому что нужно вызвать деструкторы. Но как насчет примитивных типов (и POD)? Лучше всего было бы установить размер вектора на 0, чтобы сложность была постоянной.
Если это возможно, возможно ли также для std:: unordered_map?
Кажется, лучше всего будет установить размер вектора на 0, так что сложность будет постоянной.
В целом, сложность изменение размера вектора до нуля является линейной по количеству элементов, которые в настоящее время хранятся в vector. Поэтому установка размера vector до нуля не дает преимуществ по сравнению с вызовом clear() - они по существу одинаковы.
Однако хотя бы одна реализация (libstdС++, источник в bits/stl_vector.h) дает вам сложность O (1) для примитивных типов, используя специализация частичного шаблона.
Реализация clear() переходит к функции std::_Destroy(from, to) в bits/stl_construct.h, которая выполняет нетривиальный компилятор, оптимизация времени: объявляет вспомогательный шаблонный класс _Destroy_aux с параметром шаблона типа bool. Класс имеет частичную специализацию для true и явную специализацию для false. Обе специализации определяют одну статическую функцию, называемую __destroy. Если параметр шаблона true, тело функции пуст; в случае, если параметр false, тело содержит цикл, вызывающий T деструктор, вызывая std::_Destroy(ptr).
Трюк приходит на строка 126:
std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
__destroy(__first, __last);
Вспомогательный класс создается на основе результата проверки __has_trivial_destructor. Контроллер возвращает true для встроенных типов и false для типов с нетривиальным деструктором. В результате вызов __destroy становится no-op для int, double и других типов POD.
std::unordered_map отличается от vector тем, что ему может потребоваться удалить структуры, которые представляют "хэш-ведра" объектов POD, в отличие от удаления самих объектов *. Оптимизация clear до O(1) возможна, но она сильно зависит от реализации, поэтому я не буду рассчитывать на нее.
* Точный ответ зависит от реализации: хеш-таблицы, реализующие разрешение конфликтов на основе открытой адресации (линейное зондирование, квадратичное зондирование и т.д.) может удалять все ведра в O(1); Однако реализации, основанные на отдельной цепочке, должны будут удалять ведра один за другим.
gcc версия std::_Destroy, которая в конечном итоге используется clear(), пытается включить шаблон для того, имеет ли тип тривиальный деструктор, поэтому в этом случае сложность является постоянной даже без прохода оптимизации. Однако я не знаю, насколько хорошо работает шаблон.