vector - 当 T 是原始类型时， std::vector::clear() 的复杂性是多少？

Question

我知道 clear() 操作的复杂性与容器的大小成线性关系，因为必须调用析构函数。但是原始类型(和 POD)呢？似乎最好的办法是将向量大小设置为 0，以便复杂度保持不变。

如果这是可能的，std::unordered_map 也可以吗？

Answer 1

It seems the best thing to do would be to set the vector size to 0, so that the complexity is constant.

一般来说， resizing a vector to zero 的复杂度与当前存储在 vector 中的元素数量成线性关系。 .因此，设置 vector的大小为零比调用 clear() 没有任何优势。 - 两者本质上是一样的。
但是，至少一个实现(libstdc++， bits/stl_vector.h 中的源代码)通过使用部分模板特化为原始类型提供了 O(1) 复杂度。 clear()的执行导航到 std::_Destroy(from, to) bits/stl_construct.h 中的函数，它执行一个重要的编译时优化:它声明了一个辅助模板类 _Destroy_aux使用类型为 bool 的模板参数.该类具有 true 的部分特化。以及 false 的显式特化.两种特化都定义了一个名为 __destroy 的静态函数。 .如果模板参数是 true ，函数体为空；如果参数是 false , body contains a loop invoking T 's destructor调用 std::_Destroy(ptr) .
诀窍来了 line 136 :

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 对象的“哈希桶”的结构，而不是删除对象本身*。 clear的优化至 O(1)是可能的，但它在很大程度上取决于实现，所以我不会指望它。

* 确切答案取决于实现:实现 collision resolution 的哈希表基于开放寻址(线性探测、二次探测等)可能能够删除 O(1) 中的所有存储桶;但是，基于单独链接的实现必须一个接一个地删除存储桶。