爲什麼超出內存限制？

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避免了在動態內存中創建臨時緩衝區。如果字符串足夠大，加倍同時使用的副本數量可以使程序的峯值內存使用量大致增加一倍。另外，額外的臨時分配可能會增加動態內存空間的碎片化，這會增加動態內存管理的開銷。這兩個因素可能會導致超出程序的內存限制。