在字符串中添加字符和压入字符有什么区别?

Question

我正在做一个问题，我在字符串中使用for循环添加一个字符，像这样:

for(int i=0;i<n;i++){
str = ch + str;
}

对于小输入，此代码运行良好。但是当输入量变得相当大时，就会超过内存限制。然后我把代码换成:

for(int i=0;i<n;i++){
str.push_back(ch);
}
reverse(str.begin(),str.end());

它起作用了。为了我自己的理解，我想知道原因。

Answer 1

第一个在字符串的开头添加一个字符。为了做到这一点，它创建了一个只包含ch的新字符串，然后它复制了所有的str，然后把这个临时字符串移回str。此操作至少需要足够的内存来保存字符串的两个副本。

第二个在现有字符串的末尾添加一个字符，字符串可能已经有了这个字符的空间，所以只是附加字符而不使用任何额外的内存。在某些时候，字符串需要增长，此时你将再次需要更多的内存，通常这将需要足够的内存来存储字符串的当前大小加上新的大小(例如，如果字符串实现决定将字符串的大小增加一倍，你将需要足够的内存来存储字符串的当前大小的三倍)

Answer 2

我想说这是由于内存碎片和非常接近内存不足的边界。

在str = ch + str;中，您每次分配一个长1个字符的新字符串，然后释放旧字符串。如果没有其他分配，它将需要大约3倍的内存字符串的总长度。如果在循环中有其他分配，那么它可以高达O(n^2)。

对于str.push_back(ch);，当达到容量时，字符串将增长一些因子，从而导致更少的分配。如果没有其他分配，这仍然可能是总字符串大小的2.3倍。对于分配，它可以是O(n * log(n))，其中log是生长因子的基数。