c++ - 为什么 string::resize 的复杂度是线性的？

Question

字符串需要删除它的旧内存，然后声明一个新的内存缓冲区，两者的复杂度都是O(1)。 cplusplus.com 引用资料说这在新字符串长度 的时间复杂度上是线性的。这是因为旧字符串需要复制过来吗？如果您以空字符串开头怎么办？

基本上，我想要一个在 O(1) 时间内用大小为 n 的缓冲区声明的字符串。这可能吗？

Answer 1

新字符串的每个元素都被初始化，要么通过移动旧元素，要么通过复制 std::string::resize 的第二个参数(默认为 CharT( )).

因此初始化的次数为(new length)。

可以想象，对于某些允许就地调整 block 大小的 future 改进的分配器(如 C 库中的 realloc)，可能会发现额外的内存与旧内存相邻，并且只需要 max(0, (new length) - (old length)) 初始化。但是当前的分配器方案不支持这样。