Performance - Using String Constructor and Using Concatenation
I am relatively new to C ++. I was tinkering with a coding problem and it had to do with converting a string to a palindrome.
I was storing the alphabets counters in a vector and then creating a palindrome like this -
string palindrome_string;
for (short i = 0; i < 26; ++i) {
alphabet_count[i] /= 2;
for (short j = 0; j < alphabet_count[i]; ++j)
palindrome_string += string(1, static_cast<char>('a' + i));
}
But for a specific test case (only input file containing only 2.10 ^ 5 e
), the program exceeded the 256MB limit. Then I replaced the inner loop with this statement only -
palindrome_string += string(alphabet_count[i], static_cast<char>('a' + i));
and the program works fine, only using about 2.4MB.
So, I want to ask if this is performance related using concatenation and constructor function, and if so, what is / possible reason for / s?
If it matters, I have compiled the program with MS VC ++ 2010.
If it helps, here is the stuff (code) - failed file (test case: 10) and successful .
source to share
std::string
must allocate memory in order of reaching amortized constant time. A simple implementation will grow 2x every time more space is needed, as stated here .
There is a possibility that every time you add something to yours palindrome_string
in the inner loop, that line is reallocating memory. However, I don't understand how it looks so awful. I mean, even if the simple implementation mentioned above has doubled the memory on the iteration of your inner loop, then there is no need to reallocate the space in many subsequent iterations, right?
source to share