我知道 clear() 操作的复杂性与容器的大小成线性关系，因为必须调用析构函数。但是原始类型（和 POD）呢？似乎最好的办法是将向量大小设置为 0，以便复杂度保持不变。
如果这是可能的，std::unordered_map 也可以吗？
问问题
4828 次
2 回答
9
似乎最好的办法是将向量大小设置为 0，以便复杂度保持不变。
通常，将向量的大小调整为零的复杂性与当前存储在vector. 因此，将vector的大小设置为零比跟注没有任何优势clear()——两者本质上是相同的。
但是，至少一个实现（libstdc++，source in bits/stl_vector.h）通过使用部分模板特化为原始类型提供了 O(1) 复杂度。
的实现clear()导航到std::_Destroy(from, to)函数 in bits/stl_construct.h，该函数执行非平凡的编译时优化：它声明了一个辅助模板类_Destroy_aux，其模板参数类型为bool。该类对 有部分特化和true对 的显式特化false。两种特化都定义了一个名为__destroy. 如果模板参数为true，则函数体为空；如果参数是false，则主体包含一个循环T，通过调用std::_Destroy(ptr).
诀窍出现在第 136 行：
std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
__destroy(__first, __last);
辅助类根据__has_trivial_destructor检查结果实例化。检查器返回true内置类型以及false具有非平凡析构函数的类型。结果，对 、 和其他 POD 类型的调用变为无__destroy操作。intdouble
std::unordered_map不同之处vector在于它可能需要删除代表 POD 对象的“哈希桶”的结构，而不是删除对象本身*。clearto的优化O(1)是可能的，但它在很大程度上取决于实现，所以我不会指望它。
*确切答案取决于实现：基于开放寻址（线性探测、二次探测等）实现冲突解决的哈希表可能能够删除O(1); 但是，基于单独链接的实现必须一个接一个地删除存储桶。
于 2012-11-20T19:35:43.667 回答
0
std::_Destroy最终被 使用的gcc 版本会clear()尝试根据类型是否具有微不足道的析构函数进行模板化，因此在这种情况下，即使没有优化通过，复杂度也是恒定的。但是我不知道模板的效果如何。
于 2012-06-27T23:33:27.530 回答