在 C++ 中使用新运算符和调用结构的构造函数时获取内存损坏 (Malloc)

Question

我正在尝试 this problem ，我现在不关心这个程序的逻辑或算法。我担心的是我遇到了分段错误。为此，我尝试使用 gdb，它显示了 "malloc : memory corruption"。这个问题一直困扰着我，因为我多次使用新运算符并遇到分段错误。我不知道为什么？但是跟踪测试用例的输出让我觉得 while 循环有问题。请帮我改正错误。

这是我的代码 link，我一直在努力在 Whosebug 上正确插入代码，所以使用了 ideone。它还具有给出分段错误的测试用例。

我收到以下错误消息。 * `./mergeoverlapping' 中的错误：malloc()：内存损坏：0x0000000000a8e130 *

已中止

（程序退出代码：134）按return继续

#include <bits/stdc++.h>
using namespace std;
// debug statement
#define TRACE
#ifdef TRACE
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y)                                                           \
  cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)                                                        \
  cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": "   \
       << z << endl;
#define trace4(a, b, c, d)                                                     \
  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": "   \
       << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)                                                  \
  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": "   \
       << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f)                                               \
  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": "   \
       << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | "   \
       << #f << ": " << f << endl;
#else
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif

// Structure of Interval defined by nterviewbit
struct Interval {
  int start;
  int end;
  Interval() : start(0), end(0) {}
  Interval(int s, int e) : start(s), end(e) {}
};

// operator just in case I needed sorting
bool compare(Interval a, Interval b) {
  if (a.start < b.start)
    return true;
  if (a.end < b.end)
    return true;
  return false;
}

// swap function to check if start is greater than end , if so then swap them
void swapp(Interval *t) {
  if (t->start > t->end) {
    int p = t->end;
    t->end = t->start;
    t->start = p;
  }
}

class Solution {
public:
  vector<Interval> merge(vector<Interval> &A) {
    vector<Interval> ans;
    sort(A.begin(), A.end(), compare);
    for (int i = 0; i < (int)A.size(); i++) {
      trace2(A[i].start, A[i].end);
      swapp(&A[i]);
      trace2(A[i].start, A[i].end);
    }
    int j = 0;
    int sz = A.size();
    while (j < sz) {
      while (j + 1 < sz and
             max(A[j].start, A[j + 1].start) <= min(A[j].end, A[j + 1].end)) {
        Interval *x = new Interval(min(A[j].start, A[j + 1].start),
                                   max(A[j].end, A[j + 1].end));
        trace2(x->start, x->end);
        trace2(A[j].start, A[j].end);
        A[j] = *x;
        trace2(A[j].start, A[j].end);
        trace2(A[j + 1].start, A[j + 1].end);
        A[j + 1] = *x;
        trace2(A[j + 1].start, A[j + 1].end);
        j++;
        delete x;
      }
      ans.push_back(A[j]);
      j++;
    }
    // for(int i=0;i<ans.size();i++){
    //     printf("i %d [%d %d]",i,ans[i].start,ans[i].end);
    //     cout<<endl;
    // }
    return ans;
  }
};
// BEGIN CUT HERE

int main() {
  Solution *obj = new Solution();
  // x denotes the number of intervals
  int x;
  cin >> x;
  vector<Interval> v;
  // an interval input consist of 2 integers start and end marked by a and b
  // respectively
  for (int i = 0; i < x; i++) {
    int a, b;
    cin >> a >> b;
    Interval *interval = new Interval(a, b);
    trace2(interval->start, interval->end);
    v.push_back(*interval);

    delete interval;
  }
  vector<Interval> ans = obj->merge(v);
  for (int i = 0; i < (int)ans.size(); i++) {
    printf("i %d [%d %d]", i, ans[i].start, ans[i].end);
    cout << endl;
  }
}

Answer 1

std::sort 的比较器必须定义严格的弱排序（解释如 here）。

你的比较者没有。尝试比较两个区间 (2,3) 和 (1,4)，然后以相反的顺序比较相同的区间。

因此该行为是未定义的，您的 sort 函数可能会崩溃，或者更糟的是，破坏内存区域并在以后导致崩溃。

将比较器更改为例如

 return a.start < b.start || a.start == b.start && a.end < b.end

应该可以解决这个崩溃问题。

在 C++ 中使用新运算符和调用结构的构造函数时获取内存损坏 (Malloc)

Getting Memory Corruption (Malloc) while using new operator and calling constructor of a structure in C++

c++

algorithm

new-operator