CODEWITHSUNDEEP
c++c++11
abhishekm473
abhishekm473

Reputation: 109

Why is the memory limit exceeded?

I was doing the "Sort Characters By Frequency" problem on the LeetCode online judge.

Why does this happen?

Code

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

Upvotes: 1

Views: 15860

Answers (1)

eerorika
eerorika

Reputation: 238311

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

string operator+(string&, string&) operator copies the arguments into a new string object. You then copy this temporary return value into res - which may also involve copying into a new, larger buffer. Unless C++11 is enabled, in which case move assignment will be used, so the latter potential allocation + copy is avoided.

string& operator+=(const string&) does not create a new string object. It modifies the existing string buffer in-place - unless a larger buffer is needed, in which case reallocation cannot be avoided.

So, res += c avoids creation of temporary buffers in dynamic memory. If the string is large enough, doubling the number of simultaneously used copies can roughly double the peak memory use of the program. Also, the extra temporary allocations may increase the fragmentation of dynamic memory space, which increases the overhead of dynamic memory management. These two factors may cause the memory limit given for the program to be exceeded.

Upvotes: 11

Related Questions