std :: string及其自动调整内存大小

Question

我对C++很陌生,但我知道你不能像std :: string类那样只使用内存似乎让你这么做.例如:

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

字符串类如何处理变得越来越大？我假设它分配了一个默认的内存量,如果它需要更多,它会有new更大的内存块并将自身复制到那个内存块.但是,每次需要调整大小时,必须复制整个字符串并不是很低效吗？我真的不能想到可以做到的另一种方式(但显然有人这样做了).

就此而言,所有stdlib类如vector,queue,stack等如何处理如此透明的增长和收缩？

Answer 1

你的分析是正确的-这是低效的每一个它需要调整的时间复制字符串.这就是为什么普通建议不鼓励使用模式的原因.使用字符串的reserve函数来要求它为您打算存储在其中的内容分配足够的内存.然后进一步的操作将填补该内存.(但如果你的提示结果太小,字符串也会自动增长.)

容器通常还会尝试通过分配比他们需要的更多内存来减轻频繁重新分配的影响.一种常见的算法是,当字符串发现它没有空间时,它会使其缓冲区大小加倍,而不是仅仅分配保存新值所需的最小值.如果字符串一次生成一个字符,则此倍增算法会将时间复杂度降低到分摊的线性时间(而不是二次时间).它还降低了程序对内存碎片的敏感性.

Answer 2

通常,有一个加倍的算法.换句话说,当它填充当前缓冲区时,它会分配一个两倍大的新缓冲区,然后复制当前数据.与单个分配块增长的替代方案相比,这导致更少的分配/复制操作.

Answer 3

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

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