如果元素类型是原始类型，那么std::vector::resize()向下调整大小是否需要O(1)时间？

Question

5

我知道在C++中，std::vector::resize函数在新大小比旧大小小的情况下不会分配新的内存。此外，如果元素类型是具有析构函数的用户定义类，则该析构函数可能会针对调整大小后“丢失”的每个元素进行调用，因此在这种情况下，运行时间将与大小差异成线性关系。

然而，如果元素类型是一个原始类型，例如std::vector<int>，则没有需要调用的析构函数。在这种情况下，是否存在任何理由使resize向下调整的时间复杂度不为O(1)？

- xdavidliu

3

不能保证，但大多数流行的实现会这样做。 - Incomputable

即使多余元素的销毁是O(n)，也不能阻止它成为n * 0。 - Bo Persson

@BoPersson 那个陈述是微不足道的；O(f(N)) 意味着当 N 趋近于无穷大时被 f(N) 上界所限制，因此我们可以轻易地说“任何”f，包括指数、阶乘等，都不能阻止 O(f(N)) 为零。 - xdavidliu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JMAA · Accepted Answer

标准似乎并没有对这种复杂度做出保证。但是，正如您所指出的那样，在这种情况下也没有理由使用大于常数的复杂度。复杂度仅保证为O(n)。

对于基本类型，我会惊讶地发现有编译器将其实现为线性的，但确定您的编译器设置的最佳方法是进行简单测试。