c++ - 性能——使用字符串构造函数与使用连接

Question

我对 C++ 比较陌生。我正在练习一个编码问题，它与将字符串转换为回文有关。

我将字母表的计数存储在一个 vector 中，然后像这样生成回文 -

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));
}

但对于一个特定的测试用例(仅包含 2.10^5 个 e 的输入)，程序超出了 256 MB 的内存限制。然后我只用这个语句替换了内部循环 -

palindrome_string += string(alphabet_count[i], static_cast<char>('a' + i));

程序运行良好，仅使用了大约 2.4 MB。

所以我想问一下这是否与使用连接与构造函数的性能有关，如果是，可能的原因是什么？

如果重要的话，我用 MS VC++ 2010 编译了程序。

如果有帮助，这里是提交(代码)- the failed one (测试用例:10)和 the successful one .

Answer 1

std::string应该以实现摊销常数时间的方式分配内存。如 here 所述，每次需要更多空间时，一个简单的实现将增长 2 倍。 .

有可能每次在内循环中向palindrome_string 添加内容时，该字符串都会重新分配内存。但是，我不明白这怎么会变得那么糟糕。我的意思是，即使上面提到的简单实现在内部循环的迭代中将内存加倍，那么它也不需要在接下来的许多迭代中再次重新分配空间，对吧？