std::string及其自动内存调整功能

Question

我对C++还不是很熟悉，但我知道不能像std::string类那样随意使用内存。例如：

std::string f = "asdf";
f += "fdsa";

字符串类如何处理扩容和缩小？我认为它会分配一定数量的内存，如果需要更多，则使用new分配更大的内存块并将自己复制到其中。但是每次需要调整大小时都必须复制整个字符串，这不是非常低效吗？我真的想不到还有其他方式来完成此操作（但显然有人做到了）。

同样，所有stdlib类（例如vector、queue、stack等）是如何处理透明地增长和缩小的？

- Thomas T.

Answer 1

你的分析是正确的——每次需要调整大小时复制字符串确实是低效的。这就是为什么常见建议不鼓励使用这种模式。使用字符串的reserve函数请求它分配足够存储所需内容的内存。然后进行进一步操作将填充该内存。(但如果你的提示结果过小，字符串仍会自动增长。)

容器通常也会通过分配比实际需要更多的内存来减轻频繁重新分配的影响。一种常见算法是当字符串发现空间不足时，它会将缓冲区大小加倍，而不是只分配刚好能够容纳新值的最小内存量。如果字符串逐个字符逐渐增长，则此加倍算法将时间复杂度降至摊销线性时间(而不是平方时间)。它还降低了程序对内存碎片化的敏感性。

- Rob Kennedy

Answer 2

通常情况下，有一种加倍算法。也就是说，当它填满当前缓存时，它会分配一个新的缓存，大小是当前缓存的两倍，然后将当前数据复制过去。与单个分配块增长的替代方法相比，这样可以减少分配/复制操作。

- Steven Sudit

---

当然，无法避免这种情况，但你可以通过增加初始容量来将其减至最小。 - Steven Sudit

@Billy，C#程序员们也被灌输了很多次，他们应该在很多时候使用StringBuilder而不是String。 - Rob Kennedy

不一定要加倍，其他因素也可以。例如，微软似乎更喜欢1.5，至少在他们的std::vector实现中是这样。 - fredoverflow

@FredOverflow - 并不是每个因素都可以接受。例如，1.0000001几乎没有效果:p。但是，像1.5这样的因素也提供了合理的效率。它涉及到尽可能降低负载因子以减少内存开销，同时也尽量避免过多的复制，因为复制需要时间。这就像很多计算一样需要权衡。 - Stephen

实际上，一段时间以前在c++.comp.lang.moderated上有关于增长因子的讨论。测量结果表明，使用小于2的因子更好，因为分配器通常最终会分配2的幂字节块，因此比这慢增长更好。我记得Alexandrescu参与了讨论，对此感兴趣的人可以查阅相关资料。 - Matthieu M.

Answer 3

虽然我不知道std :: string的确切实现方式，但大多数需要处理动态内存增长的数据结构都是通过执行您所说的操作来完成的 - 分配默认数量的内存，如果需要更多，则创建一个更大的块并将自己复制过去。

为了解决明显的效率问题，您需要分配比所需内存更多的内存。向量/字符串/列表等使用的已用内存：总内存的比率通常称为负载因子（在哈希表中稍有不同的含义）。通常是1:2的比率 - 也就是说，你分配了两倍于所需内存的内存。当您用完空间时，分配当前数量两倍的新内存并使用它。这意味着随着时间的推移，如果您继续向向量/字符串/等添加项目，则需要越来越少地复制该项（因为内存创建是指数级的，而插入新项当然是线性的），因此这种方法处理内存所需的时间不像您可能想象的那样长。根据摊销分析原理，您可以看到使用这种方法将m个项插入向量/字符串/列表仅为Big-Theta of m，而不是m²。

- Stephen

---

@Steven - 在这种情况下，我很犹豫。有人声称C#在每次移动后都会复制一个字符串，但它并不被普遍认为是慢的...但我的理论思维当然会想到"阿尔格！n²！n²！阿尔格！" ...XD。我想我会删掉这个注释。 - Stephen

C#中的string(或者说.NETSystem.String)与std::string不是直接可比的。在.NET 3.5中，最接近的东西是StringBuilder，它是一个可变的字符集合，允许就地修改连续缓冲区，并使用ToString()创建不可变快照。在.NET 4.0中，有一个同名和具有相似功能的类，但其实现是分段的，因此它与std::string的共同之处更少了。关键点是，无论如何，重复地简单附加到string上是不被认为是可接受的。 - Steven Sudit