std::vector和std::string的重新分配策略

Question

std::vector和std::string的重新分配策略

c++gccstl

12

在GCC的实现中，std::string和std::vector所使用的重新分配策略是什么？

我对具体的策略很感兴趣：当我向vector（或string）附加项时，它可能会超出预留大小，然后会发生重新分配，但新大小将作为旧大小的函数是什么？在删除元素的情况下，实际重新分配和释放内存的阈值是多少（再次，新的大小将是什么）？

其他编译器的答案也将不胜感激。

- Guy

为了澄清问题（考虑到@Paul的解决方案），我不是关心如何避免重新分配内存，而是想学习实现中使用的策略。 - Guy

4个回答

7

vector和string都保证push_back的复杂度是“摊销常数”，这意味着调用push_back n次所花费的时间除以n，当n变大时，会受到一个常数的限制。要实现这一点的唯一方法是通过几何级数增长来增加容量大小，即新容量是旧容量的某个固定倍数。这样做，您只需要很少的重新分配。

在实现中，通常使用2或1.5等增长因子，但任何大于1的数字都可以。

不过，这与reserve没有交互作用。如果在每次push_back之前调用reserve（size（）+ 1），则可能会每次都有重新分配。

- Kerrek SB

4

std::vector有size和capacity两种方法。编写一个简单的程序来确定内存分配方式并不太困难。每个实现甚至每个版本的策略都可能会改变。

我看到的一种策略是使用递增的增量，这是一种自适应策略：给予更多的资源来避免频繁地对数据进行重排。但是增量的因子是值得讨论的。简单的复制可能会过于快速增长。

后来

出于好奇心，我编写了那个程序。这是输出（g++ 4.3.3）：

capacity from 0 to 1 increased by 1 at size 1
capacity from 1 to 2 increased by 1 at size 2
capacity from 2 to 4 increased by 2 at size 3
capacity from 4 to 8 increased by 4 at size 5
capacity from 8 to 16 increased by 8 at size 9
capacity from 16 to 32 increased by 16 at size 17
capacity from 32 to 64 increased by 32 at size 33
capacity from 64 to 128 increased by 64 at size 65
capacity from 128 to 256 increased by 128 at size 129
capacity from 256 to 512 increased by 256 at size 257
capacity from 512 to 1024 increased by 512 at size 513
capacity from 1024 to 2048 increased by 1024 at size 1025
capacity from 2048 to 4096 increased by 2048 at size 2049
capacity from 4096 to 8192 increased by 4096 at size 4097
capacity from 8192 to 16384 increased by 8192 at size 8193
capacity from 16384 to 32768 increased by 16384 at size 16385
capacity from 32768 to 65536 increased by 32768 at size 32769
capacity from 65536 to 131072 increased by 65536 at size 65537
capacity from 131072 to 262144 increased by 131072 at size 131073
capacity from 262144 to 524288 increased by 262144 at size 262145
capacity from 524288 to 1048576 increased by 524288 at size 524289

在构造函数中使用初始分配会产生相同的进度，使用初始值而不是1。

- laune

2

关于reserve的具体工作方式，现在还无法确定。你可以像这样使用它：

std::vector<T> myV;
myV.reserve(<space known to be needed>);

因此，您知道只有在超出该空间之后才会调用reserve（也不会执行任何重新分配）。

- Paul Evans

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

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

- Marc Glisse · Accepted Answer

请看 bits/stl_vector.h 中的函数 _M_check_len。它包括：

const size_type __len = size() + std::max(size(), __n);

当您添加n个元素时，基本策略是将大小加倍或增加n，以较大者为准。 pop_back 永远不会释放内存。libc++ (LLVM) 的做法与此完全相同。

阅读代码是了解字符串、释放内存等策略的唯一方法。