在字符串开头附加字符会导致超出内存限制

Question

[在编码问题上，假设我的string s为length 50000

我正在基于一些约束来创建另一个字符串。

下面的代码给了我结果。

string res = "";

for(int i = 0; i < s.length(); i++)
{
    if(/* some constraint satisfied */)
    {
        res += s[i];
    }
}

下面的代码在在线裁判上抛出了Memory Limit Exceeded。

string res = "";

for(int i = s.length() - 1; i >= 0; i--)
{
    if(/* some constraint satisfied */)
    {
        res = s[i] + res;
    }
}

1. 是否在第二种情况下每次都创建一个新字符串？

2. 如果是，那么如何在向后迭代时避免使用它。

3. 我是否需要在开始时保留内存？

4. 如果是，大小应该是多少？

任何帮助将不胜感激。

Answer 1

第二个版本效率很低，因为在长字符串的开头重复插入一个字符意味着所有字符需要移位一个位置。此外，res += s[i]可以利用res缓冲区中的空闲容量（当字符串超过容量时，字符串的大小乘以它们的大小，以便最后一次重复插入不需要每次都重新分配内存），而res = s[i] + res总是分配一个新的字符串并将其移到res。

而不是展开自己的循环并犯很多错误（错误的索引类型，次优的增减运算符用法，环绕式错误），请与std::copy_if（在标头std::copy_if中定义）一起使用（在标题<algorithm>中定义）：

<algorithm>

如果事先知道满足条件的粗略字符，也可以使用std::back_inserter。>