I was doing a question where I was adding a character using for loop in string like this:

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

This code was running fine for small inputs. But when the input became quite large the memory limit exceeded. Then I switched my code with:

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

And it worked. I want to know the reason why for my own understanding.

CodePudding user response：

The first adds a character to the beginning of the string. I'm order to do this it creates a new string containing just ch, then it copies all of str in to it then moves this temporary string back into str. This operation requires at least enough memory to hold two copies of the string.

The second adds a character on to the end of the existing string, the string likely already has space for this character so just appends the character without using any additional memory. At some point the string will need to grow, at this point you'll again need more memory, typically this would need enough memory for the current size of the string plus the new size (e.g if the string implementation decides to double in size you'll need enough memory for three times the current size of the string)

CodePudding user response：

I would say this is due to memory fragmentation and being very close to the out-of-memory boundary.

In str = ch str; you are allocating a new string that is 1 char longer every time and then freeing the old string. If there are no other allocations it will need about 3 times the total length of the string of memory. If there are any other allocations in the loop then it can go as high as O(n^2).

With str.push_back(ch); the string will grow by some factor when it reaches capacity causing a lot fewer allocations. Without other allocations this could still be something like 2.3 times the total string size. With allocations it could be O(n * log(n)) where log is to the base of the growth factor.