当T是基本类型时，std :: vector< T> :: clear（）的复杂性是什么？ [英] What is the complexity of std::vector<T>::clear() when T is a primitive type?

问题描述

我知道clear（）操作的复杂度在容器的大小上是线性的，因为必须调用析构函数。但是原始类型（和POD）呢？似乎最好的办法是将向量大小设置为0，以使复杂度恒定。

I understand that the complexity of the clear() operation is linear in the size of the container, because the destructors must be called. But what about primitive types (and POD)? It seems the best thing to do would be to set the vector size to 0, so that the complexity is constant.

如果可能的话，std是否也可能:: unordered_map？

If this is possible, is it also possible for std::unordered_map?

推荐答案

似乎最好的方法是设置矢量大小

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

通常，将向量的大小调整为零与向量。因此，将 vector 的大小设置为零比调用 clear（）没有优势-两者本质上是相同的。

In general, the complexity of resizing a vector to zero is linear in the number of elements currently stored in the vector. Therefore, setting vector's size to zero offers no advantage over calling clear() - the two are essentially the same.

但是，至少有一个实现（libstdc ++，源于 bits / stl_vector.h ）通过使用部分模板为原始类型提供O（1）复杂度

However, at least one implementation (libstdc++, source in bits/stl_vector.h) gives you an O(1) complexity for primitive types by employing partial template specialization.

clear（）的实现将其导航到 std :: 中的_Destroy（从，到）函数 bits / stl_construct.h ，执行非平凡的编译时优化：它声明一个辅助模板类 _Destroy_aux ，其模板参数类型为 bool 。该类对 true 有部分专业化，对 false 显式专业化 c $ c>。这两个专业都定义了一个称为 __ destroy 的静态函数。如果template参数为 true ，则函数体为空；否则，函数体为空。如果参数为 false ，则正文包含调用 T 的析构函数的循环，方法是调用 std :: _ Destroy（ptr）。

The implementation of clear() navigates its way to the std::_Destroy(from, to) function in bits/stl_construct.h, which performs a non-trivial compile-time optimization: it declares an auxiliary template class _Destroy_aux with the template parameter of type bool. The class has a partial specialization for true and an explicit specialization for false. Both specializations define a single static function called __destroy. In case the template parameter is true, the function body is empty; in case the parameter is false, the body contains a loop invoking T's destructor by calling std::_Destroy(ptr).

诀窍来自第126行：

std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
__destroy(__first, __last);

根据 __ has_trivial_destructor 检查。对于内置类型，检查器返回 true ，对于具有非平凡析构函数的类型，返回 false 。结果，对 __ destroy 的调用成为 int ， double 和其他POD类型。

The auxiliary class is instantiated based on the result of the __has_trivial_destructor check. The checker returns true for built-in types, and false for types with non-trivial destructor. As the result, the call to __destroy becomes a no-op for int, double, and other POD types.

std :: unordered_map 与 vector 的原因在于，与删除对象本身 ^* 相比，它可能需要删除代表POD对象哈希桶的结构。可以将 clear 优化为 O（1），但这在很大程度上取决于实现，所以我会

The std::unordered_map is different from the vector in that it may need to delete structures that represent "hash buckets" of POD objects, as opposed to deleting objects themselves^*. The optimization of clear to O(1) is possible, but it is heavily dependent on the implementation, so I would not count on it.

^* 确切的答案取决于实现：哈希表基于开放式寻址（线性探测，二次方程）实现 冲突分辨率 探测等）可能能够删除 O（1）中的所有存储桶；不过，基于单独链接的实现必须逐个删除存储桶。

^* The exact answer depends on the implementation: hash tables implementing collision resolution based on open addressing (linear probing, quadratic probing, etc.) may be able to delete all buckets in O(1); implementations based on separate chaining would have to delete buckets one-by-one, though.

这篇关于当T是基本类型时，std :: vector< T> :: clear（）的复杂性是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！