heap-use-after-free when using references with 2D vector in C-CodePudding

I am solving this problem on leetcode: https://leetcode.com/problems/merge-intervals/

When I go to submit my solution, I get the error of AddressSanitizer: heap-use-after-free. More specifically, there is an error of Thread 1: EXC_BAD_ACCESS (code=1, address=0x0) when I hit the line of code currentMergedInterval = mergedIntervals.back(); but I don't understand why.

Whenever I modify the 2-D vector mergedIntervals, I make sure to update my vector reference, currentMergedInterval, after mergedIntervals has been modified. So it's not clear to me why this is causing an issue.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> mergedIntervals(1, intervals[0]);

        vector<int>& currentMergedInterval = mergedIntervals.back();

        int mergedIntervalEnd = 0;
        int intervalStart = 0;
        for (size_t i = 1; i < intervals.size(); i  )
        {
            mergedIntervalEnd = currentMergedInterval[1];
            intervalStart = intervals[i][0];
            
            if (mergedIntervalEnd >= intervalStart)
            {
                currentMergedInterval[1] = intervals[i][1];
            }
            else
            {
                mergedIntervals.push_back(intervals[i]);
                currentMergedInterval = mergedIntervals.back();
            }
        }
        
        return mergedIntervals;
    }
};

int main()
{
    Solution s = Solution();

    vector<vector<int>> v = {{1,3}, {2,6}, {8,10}, {15,18}};
    vector<vector<int>> sol = s.merge(v);

    // Expected output: [[1,6],[8,10],[15,18]]
    for (vector<int> vec : sol)
    {
        printf("%d %d\n", vec[0], vec[1]);
    }
}

CodePudding user response：

References can't be reassigned. Assigning to a reference variable will not change the reference, it will change the object being referenced.

Because of this, and because of adding elements to a vector might invalidate all references, pointers or iterators to elements, the two statements

mergedIntervals.push_back(intervals[i]);
currentMergedInterval = mergedIntervals.back();

could lead to undefined behavior if the reference currentMergedInterval is now invalid.

For this specific case it would be better to use iterators or pointers instead of references, since they can be reassigned.

CodePudding user response：

You have made the mistake of thinking that

currentMergedInterval = mergedIntervals.back();

reassigns your reference. But this is not true, references can never be reassigned. Instead this code assigns mergedIntervals.back() to mergedIntervals[0] (the original referee of currentMergedInterval).

You could use a pointer (or an iterator) for the same purpose

vector<int>* currentMergedInterval = &mergedIntervals.back();

with consequent changes to the rest of your code.

But I think my preference would be to not add the current interval to the merged intervals until the end.

I.e.

   vector<vector<int>> mergedIntervals;
   size_t current = 0;

...

   mergedIntervals.push_back(intervals[current]);
   current = i;
...

   mergedIntervals.push_back(intervals[current]);
   return mergedIntervals;

again with consequent changes to the rest of your code