为什么超出内存限制？

Question

我在Leetcode OJ上做了“按频率排序字符”问题。 任何人都可以向我解释为什么会发生这种情况？

class Solution { 

public: 
    struct Node { 
     int freq; 
     char ch; 
    }; 

    static bool lambda(struct Node a, struct Node b){ 
     return a.freq>b.freq; 
    } 

    string frequencySort(string s) { 
     if(s.size() == 0) 
      return ""; 

     string res = ""; 
     vector<Node> nums(256); 

     for(char c : s){ 
      nums[(int)c].ch = c; 
      nums[(int)c].freq++; 
     } 

     std::sort(nums.begin(), nums.end(), Solution::lambda); 

     char c; 
     for(int i=0; nums[i].freq > 0; i++){ 
      c = nums[i].ch; 
      while(nums[i].freq--){ 
       res = res + c; // If I replace this line with res += c, it gets Accepted! 
      } 
     } 

     return res; 
    } 
}; 

Answer 1

res = res + c; // If I replace this line with res += c, it gets Accepted! 

string operator+(string&, string&)运营商复制参数到一个新的字符串对象。然后，您将此临时返回值复制到res - 这可能还涉及复制到一个新的更大的缓冲区。除非启用C++ 11，否则在这种情况下将使用移动分配，因此可以避免后一个潜在分配+复制。

string& operator+=(const string&)不会创建新的字符串对象。它会就地修改现有的字符串缓冲区 - 除非需要更大的缓冲区，在这种情况下，无法避免重新分配。

因此，res += c避免了在动态内存中创建临时缓冲区。如果字符串足够大，加倍同时使用的副本数量可以使程序的峰值内存使用量大致增加一倍。另外，额外的临时分配可能会增加动态内存空间的碎片化，这会增加动态内存管理的开销。这两个因素可能会导致超出程序的内存限制。