为什么C++二元加法运算符触发TLE而复合赋值运算符效率更高？

我在LeetCode求解Sort Characters By Frequency题目时，使用二元运算符拼接字符串的代码触发了TLE（超时），改用复合赋值运算符后即可正常通过，两份代码如下：

触发超时的代码 #

class Solution {
public:
    string frequencySort(string s) {
        
        unordered_map<char, int> m;
        for(int i = 0; i < s.length(); i++)
            m[s[i]]++;
        
        priority_queue<pair<int, char>> pq; // 基于频率的大顶堆
        for(auto x = m.begin(); x != m.end(); x++)
            pq.push(make_pair(x->second, x->first));
        
        string ans = "";
        while (!pq.empty())
        {
            for(int i = 0; i < pq.top().first; i++)
                ans = ans + pq.top().second;
            pq.pop();
        }
        
        return ans;
    }
};

可正常通过的代码 #

class Solution {
public:
    string frequencySort(string s) {
        
        unordered_map<char, int> m;
        for(int i = 0; i < s.length(); i++)
            m[s[i]]++;
        
        priority_queue<pair<int, char>> pq; // 基于频率的大顶堆
        for(auto x = m.begin(); x != m.end(); x++)
            pq.push(make_pair(x->second, x->first));
        
        string ans = "";
        while (!pq.empty())
        {
            for(int i = 0; i < pq.top().first; i++)
                ans += pq.top().second;
            pq.pop();
        }
        
        return ans;
    }
};

两者的核心区别来自C++ std::string对两种运算符的实现逻辑完全不同：

• ans = ans + pq.top().second的执行逻辑：
  每次运行+运算时，都会申请一块大小为当前ans长度+1的全新内存，把原有ans的全部内容拷贝到新内存，再把新字符写入末尾，最后将新生成的临时字符串赋值给ans，同时释放旧内存。如果最终ans总长度为n，整体拼接的时间复杂度是O(n²)，输入字符串较长时必然会超时。
• ans += pq.top().second的执行逻辑：
  +=运算符直接在ans已有的内存空间上追加内容。std::string内部会预分配大于实际存储长度的缓冲空间（即capacity属性），只要追加后的总长度不超过缓冲容量，就不需要重新申请内存和拷贝原有数据；只有容量不足时才会触发扩容，一般扩容为原容量的1.5~2倍，整体扩容的总拷贝次数是O(log n)级别，整体拼接的时间复杂度为O(n)，性能远高于前者。

你还可以省略循环拼接的步骤，直接调用append方法一次性拼接多个相同字符，进一步降低开销：

while (!pq.empty()) {
    ans.append(pq.top().first, pq.top().second);
    pq.pop();
}

内容的提问来源于stack exchange，提问作者Chirag