STD :: String及其自动内存调整大小

Question

我对C ++很新，但我知道您不能像STD :: String类一样使用Memory Willy Nilly，似乎让您做。例如：

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

字符串类如何处理越来越小？我认为它会分配默认数量的内存，如果需要更多，则 newSA更大的内存块，并将其复制到其中。但是，每次调整大小时都必须复制整个字符串，这不是很低效率吗？我真的不能想到可以做到的另一种方式（但显然有人做到了）。

为此，如何透明地处理媒介，队列，堆栈等诸如矢量，队列，堆栈等的所有类别？

Answer 1

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

Answer 2

您的分析是正确的 - 它 是 每次需要调整大小时都无法复制字符串。这就是为什么常见建议不鼓励使用模式的原因。使用字符串 reserve 功能要求它为您的内容分配足够的内存 打算 存放在其中。然后进一步操作将填充该内存。 （但是，如果您的提示太小，则字符串仍然会自动增长。）

容器通常还会尝试通过分配比需要更多的内存来减轻频繁重新分配的影响。一种常见的算法是，当字符串发现其不空时，它 双打 它的缓冲尺寸，而不仅仅是分配保持新值所需的最低限度。如果字符串一次是一个字符，则这种二倍算法将时间复杂性降低到摊销线性时间（而不是二次时间）。它还降低了程序对内存破碎的敏感性。

Answer 3

尽管我不知道STD :: String的确切实现，但是大多数需要处理动态内存增长的数据结构可以通过做您所说的准确来做到这一点 - 分配默认的内存量，如果需要更多的内存，然后创建一个更大的块并复制自己。

您解决明显的低效率问题的方式是分配超出所需的内存。使用的内存之比：向量/字符串/列表/等的总内存通常称为 负载因子 （也用于略有不同含义的哈希表）。通常是1：2的比例 - 也就是说，您分配了两倍的内存。当您用完空间时，您将分配新数量的内存两倍，并使用它。这意味着，随着时间的流逝，如果您继续将内容添加到向量/字符串/等，则需要越来越少地复制该项目（因为内存创建是指数级的，并且您插入新项目当然是线性的），因此，这种记忆处理方法所花费的时间并不像您想象的那么大。根据 摊销分析, ，然后您可以看到该插入 m 使用此方法进入向量/字符串/列表中的项目只是M的大键，而不是M².