当T是基本类型时,std :: vector <T> :: clear()的复杂性是多少？

Question

我理解clear()操作的复杂性在容器的大小上是线性的,因为必须调用析构函数.但原始类型(和POD)呢？似乎最好的做法是将矢量大小设置为0,这样复杂性就是不变的.

如果可以,std :: unordered_map也可以吗？

Answer 1

似乎最好的做法是将矢量大小设置为0,这样复杂性就是不变的.

通常,将矢量大小调整为零的复杂度在当前存储在元素中的元素数量是线性的vector.因此,将vector大小设置为零并不比调用更有优势clear()- 两者基本相同.

但是,至少有一个实现(libstdc ++,source in 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变为无操作用于int,double以及其他类型的POD.

在std::unordered_map从不同的vector,它可能需要删除表示POD对象的"散列桶"结构,而不是删除对象本身^*.clearto 的优化O(1)是可能的,但它在很大程度上取决于实现,所以我不会指望它.

^*确切的答案取决于实现:基于开放寻址(线性探测,二次探测等)实现冲突解决的哈希表可能能够删除所有桶O(1); 但是,基于单独链接的实现必须逐个删除存储桶.

Answer 2

gcc 的 版本std::_Destroy（最终被 所使用clear()）尝试根据该类型是否具有简单的析构函数进行模板化，因此在这种情况下，即使没有优化过程，复杂性也是恒定的。但我不知道该模板的效果如何。