I was solving a question in which I have to add a single character in front of a string multiple times so I just use
string l ="";
char c = 'x';
l = c l;
but when I run it, it shows the memory limit is exceeded? Instead when I used
string l ="";
char c = 'x';
l = c;
reverse(l.begin(),l.end());
It was compiled successfully. I want to know why this is happening?
CodePudding user response：
c l results in a new std::string (temporary) object which holds the new string contents, meaning the old string's contents prefixed by c.
Now, where should this std::string object store the string data? It can't reuse the memory of l, since at that point we don't know yet that the string is going to be assigned to l. In general we might want to reuse the l with the old string contents.
So this temporary has to allocate memory for the whole (prefixed) string and copy the contents into it.
Of course, then we assign the temporary string to l and in that case (since the temporary string won't be usable anymore afterwards) l can just reuse the memory used by the temporary object.
The compiler might realize how these two steps will end up with only one string object in the end and might skip the extra allocation, but I think that is generally unlikely.
With l = c;, no extra string object is created. Instead you are directly appending to l. Now it could be the case that l doesn't have enough memory reserved to append the extra c into. In that case it is also likely to reallocate memory and copy the original string contents to the new larger allocation. But that would only happen for certain sizes of l. If you repeatedly add characters like this, then this will happen only occasionally and the strategy used by the standard library to reallocate memory will make it so that there is only a constant factor in time cost. However, you still might be getting lucky that the maximum memory used doesn't exceed the limit.
If reallocation is required, then the two shown code snippets should use roughly the same maximum memory (in this particular step).
Of course your second example results in a reserved string. I think you might have intended to reverse it before appending c as well.
You can keep using c l though. You should just make sure to indicate that the contents of l are not required anymore after that operation (because l will be replaced by the result of c l anyway). That is done with std::move:
// for std::move
#include<utility>
/*...*/
l = c std::move(l);
That should have about the same memory usage as your second case, but shouldn't require moving all characters twice to reverse twice.
Alternatively as mentioned by @TedLyngmo in the comments, the most straight-forward way to append a character at the beginning is probably to use the insert member function which allows you to specify where exactly you want to add the character:
l.insert(l.begin(), c);
Neither of all of these are time efficient. If you have to repeatedly add characters at the beginning, but not at the end, then it would be better to only store the reversed version of the string and modify the rest of the algorithm to work with the reversed string. Appending to the end of a string is usually cheap, but appending to the front is always time costly.
CodePudding user response：
l = c l will allocate a new string object, and then overwrite the old one (when you assign).
l = c will do the extension in-place.
Let's say l has length N. c has length one of course.
So c l has length N 1. So it uses N 1 space, plus N space for the original l we have already. So 2N 1 space total.
l = c just adds it in-place, so we just need N 1 space total.
(of course, we don't know specifically how exactly these are implemented, but this should give you an idea of the memory usage.)