std :: vector <int> :: clear,constant time？

Question

std :: vector <int> :: clear,constant time？

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

如果我有一个std::vector原始类型,并且我调用clear()(这种方式push_back从头开始capacity),clear()调用将在恒定时间或线性时间内完成吗？文档说它会破坏所有元素,但是如果元素是一个int,那么就不应该有任何东西需要破坏,对吧？

编辑:我发现了一个副本,其中有一张海报,详细解释了实现可以检查析构函数是否微不足道,并给出了一个具有该检查(GCC)的编译器的示例.

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

Answer 1

Cha*_*via 5

这取决于向量的实现方式，但是具有简单析构函数的对象数组（包括诸如内置整数类型之类的 POD int）应该能够通过一次调用安全地解除分配，vector<T>::allocator_type::deallocate而无需循环遍历元素并单独调用析构函数。的实现std::vector可以使用type_traits或编译器内部来确定是否T有一个简单的析构函数，并相应地释放内部数组。您需要检查您的实现的源代码以了解它的作用，但大多数主流实现std::vector将为您提供具有平凡析构函数的类型的恒定时间解除分配（或至少为整数类型和其他 POD 的恒定时间）。

@shiplu.mokadd.im，没关系。这只是在“cppreference.com”上撰写文章的人的猜测或概括。它不是权威的，也不是标准的引用。OP 提出了一个关于 *implementation* 的问题，事实是如果 `T` 有一个简单的析构函数，`std::vector` 可以通过恒定时间释放来实现。 (3认同)
@shiplu.mokadd.im，如果保留的大小大于元素的数量，向量中的 _inserting_ 是常数时间，因此它确实取决于两个变量。另一方面，清除不依赖于向量的实际大小或保留大小。如果您必须调用析构函数，这是一个线性时间操作。但是，如果您只需要调用一些简单的析构函数（例如，使用 `int` 向量），则可以优化向量的实现以跳过该步骤。正如查尔斯解释的那样，如果可以的话，清除操作实际上变成了恒定时间。 (2认同)

归档时间：	13 年，1 月前
查看次数：	1807 次
最近记录：	13 年，1 月前