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

Question

I was trying this problem and I am not concerned with the logic or algorithm of this program right now. My concern is I am getting the segmentation fault. For that I tried using gdb which showed me a "malloc : memory corruption". This problem has been haunting me as many times I use new operator and get segmentation fault. I am not able to figure out why?. But tracing output on a test case made me think something is wrong with the while loop. Please help me to correct my mistake.

Here is my code link, I was struggling to properly insert code on stackoverflow so used ideone. It also has the test case for which It gives segmentation fault.

I am getting following error message. * Error in `./mergeoverlapping': malloc(): memory corruption: 0x0000000000a8e130 *

Aborted

(program exited with code: 134) Press return to continue

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

You appear to be using `free` on something allocated with `new`. — , Jun 03 '17 at 20:28
Stop using pointers and `new`. You don't need any of those in this program. If you came to C++ from Java, forget all you know about it and start afresh. C++ is completely different, none of your experience translates. — n. m. could be an AI, Jun 03 '17 at 20:33
@Stargateur, I apologise for posting screenshot, I removed it and wrote the message instead. — Atul, Jun 03 '17 at 20:40
@NeilButterworth, I tried both but it does not change anything — Atul, Jun 03 '17 at 20:43
@NeilButterworth, can you tell if I am accessing any memory, I should not have. — Atul, Jun 03 '17 at 20:50
Like this: `ClassName variable(ctorArg1, ctorArg2);` or like this `callingAFunction(ClassName(ctorArg1, ctorArg2));`. It looks like you need to read a C++ book. This question is so basic, it is unclear how you plan to ever write anything at all in C++ without being able to answer it. — n. m. could be an AI, Jun 03 '17 at 20:50
If you want any help, you need to post an example of input file which causes your program to crash. — n. m. could be an AI, Jun 03 '17 at 20:53
@n.m. can you please click the link code I have put, it contains the test case as well — Atul, Jun 03 '17 at 20:59

score 1 · Accepted Answer · answered Jun 03 '17 at 21:47

1

A comparator for std::sort must define a strict weak ordering (explained e.g. here).

Your comparator doesn't. Try to compare two intervals (2,3) and (1,4), then the same intervals in the reverse order.

Thus the behaviour is undefined and your sort function may crash, or worse, corrupt the memory arena and cause a crash later.

Changing the comparator to e.g.

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

should fix this crash.

answered Jun 03 '17 at 21:47

n. m. could be an AI

112,515
14
128
243

@Thank you very much n.m. for thr help. I always doubted that something is wrong with the way I work with new and pointers but learned a new thing today . Would you suggest me more elegant ways to work with new and pointer? – Atul Jun 03 '17 at 22:05
The most elegant way to work with new and pointers is to avoid them entirely, which is very doable with this program. – n. m. could be an AI Jun 03 '17 at 22:16

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

1 Answers1