malloc(): memory corruption (fast) c++

Question

I'm new with c++ and I'm trying to calculate the convex hull of a Point(x,y,z) set using C++.

I have called the following method in the main method:

vector<Point> convexHull(Point Points[], int n) {
    vector<Point> v;
    // Find the bottommost Point
    int ymin = Points[0].getY();
    int min = 0;
    for (int i = 1; i < n; i++) {
        int y = Points[i].getY();

        // Pick the bottom-most or chose the left most Point in case of tie
        if ((y < ymin) || (ymin == y && Points[i].getX() < Points[min].getX()))
            ymin = Points[i].getY(), min = i;
    }
    // Place the bottom-most Point at first position
    Points[min] = Points[0].swap(Points[min]);

    // Sort n-1 Points with respect to the first Point. A Point p1 comes
    // before p2 in sorted ouput if p2 has larger polar angle (in 
    // counterclockwise direction) than p1
    p0 = Points[0];
    qsort(&Points[1], n - 1, sizeof (Point), compare);

    // Create an empty stack and push first three Points to it.
    stack<Point> S; //  on debug the project I find that the problem is here 
    S.push(Points[0]);
    S.push(Points[1]);
    S.push(Points[2]);

    // Process remaining n-3 Points
    for (int i = 3; i < n; i++) {
        // Keep removing top while the angle formed by Points next-to-top, 
        // top, and Points[i] makes a non-left turn
        while (orientation(nextToTop(S), S.top(), Points[i]) != 2)
            S.pop();

        S.push(Points[i]);
    }

    // Now stack has the output Points, print contents of stack
    while (!S.empty()) {
        Point p = S.top();
        cout << "(" << p.getX() << ", " << p.getY() << ", " << p.getZ() << ")" << endl;
        v.push_back(Point(p.getX(), p.getY(), 0));
        S.pop();
    }
    return v;
}

It give this error:

*** glibc detected *** /home/user/NetBeansProjects/DGILOG-ask/dist/Debug/GNU-Linux-x86/dgilog-task: malloc(): memory corruption (fast): 0x08de1238 ***

I have searched in the web for the same error but I don't have understand what should I do.

Point.cpp

#include <iostream>
#include <math.h>
#include <ostream>

using namespace std;

#include "Point.h"

Point::Point() : x(0), y(0), z(0) {
}

Point::Point(ostream &strm) {
    strm << "Type the abscissa: ", cin >> this->x;
    strm << "Type the ordinate: ", cin >> this->y;
    strm << "Type the applicate: ", cin >> this->z;
}

Point::Point(float x, float y, float z) : x(x), y(y), z(z) {
}

/**
 * Destructor
 */
Point::~Point() {
}

//Other methods

float Point::dist2D(Point &other) {
    float xd = x - other.x;
    float yd = y - other.y;
    return sqrt(xd * xd + yd * yd);
}

float Point::dist3D(Point &other) {
    float xd = x - other.x;
    float yd = y - other.y;
    float zd = z - other.z;
    return sqrt(xd * xd + yd * yd + zd * zd);
}

Point Point::swap(Point p) {
    Point aux(x, y, z);
    x = p.x;
    y = p.y;
    z = p.z;
    return aux;
}

void Point::print(ostream &strm) {
    strm << "Point(" << this->x << "," << this->y << "," << this->z << ")" << endl;
}

bool Point::operator<(const Point &p) const {
    return x < p.x || (x == p.x && y < p.y);
}

Thanks.

Solution 1

Since you didn't post a complete program, here are some things you should look out for:

convexHull(Point Points[], int n)

Nowhere in that function do you check if n is within bounds of the Points array. You should be using vector throughout your function. For example:

 int ymin = Points[0].getY();
 int min = 0;
 for (int i = 1; i < n; i++) {
    int y = Points[i].getY();

If I pass a NULL pointer as the first argument (or even an invalid pointer), or if n is too large, you have an access violation. Using vectors greatly reduces or outright removes these issues. With vector, you have the size() member function to do sanity tests to ensure that Point has the relevant number of entries. Right now, there is no way to do such tests in your function.

Next issue:

S.push(Points[0]);
S.push(Points[1]);
S.push(Points[2]);

How do you know there are at least 3 entries in point? You don't know, and there is no way in that function to check. All you have is a pointer being passed, and some arbitrary number n. If you're using C++, you should not be in the habit of deliberately coding in a 'C'-like style. You have vector, so use it to its advantage.

Next issue:

qsort(&Points[1], n - 1, sizeof (Point), compare);

Since you didn't post what Point is, this usage of qsort() leads to undefined behavior if Points is a non-POD type.

Stop using qsort(). Usage of qsort() within a C++ program is an indication that the coder is either 1) a C programmer who is using what they're used to (with the surprising unexpected reuslts that usually follow) or 2) A newbie C++ programmer who is reading C books or programs as a guidance in writing proper C++ programs.

Use std::sort() -- you're writing a C++ app, not a C application. The std::sort is typesafe, easier to use and setup, and works for POD and non-POD types that follow a strict-weak-ordering.

Solution 2

By the look of the error, and the place you are saying it crashes (a declaration), it very well may be in the qsort function. It is the only C library call you have in the code, and the error can't be in the declaration of the stack since it is just a declaration.

The first thing you should do is check bounds

vector<Point> convexHull(Point Points[], int n) {
  vector<Point> v;
  if(n <= 3){ 
     // error
  }else{
    //the chunk of code
  } 
  return v;
}

But wait... there's more, suppose you want to replace the Points array with a vector

std::vector<Point> convexHull(vector<Point>::iterator begin, vector<Point>::iterator end) {
  std::vector<Point> returnVal;
  if(n <= 3){ 

  }else{
    //the chunk of code
  } 
  return returnVal;
}
// just don't forget to check your returnVal for empty size, error handling is a must

Or you could just use your c style old school method with a vector... which i don't recommend because you stop learning about iterators, which you should.

vector<Point> Points(100);
vector<Point> v;
if(convexHull(&Points[0], Points.size())) ///< how would you be testing this
{
   //yay
}

Oh, and by the way, implementing std::sort is really easy, don't be afraid, it is like this

std::sort (&Points[1], &Points[1]+ (n-1));

Which would be easier if Points where iterators

std::sort (begin+1, end);

You could even go further and use std::advance, which you should

vector<Point>::iterator it = begin;   
std::advance(it,1);
std::sort (it, end);

So in conclusion how would the first part look with iterators?

std::vector<Point> convexHull(vector<Point>::iterator begin, vector<Point>::iterator end)
{
  vector<Point> v;
  // Find the bottommost Point
  int ymin = begin->getY();
  vector<Point>::iterator l_it = begin; 
  vector<Point>::iterator min_position = begin;
  std::advance(l_it, 1);
  for (; l_it != end; ++l_it) 
  {
      int y = l_it->getY();

      // Pick the bottom-most or chose the left most Point in case of tie
      if ((y < ymin) || (ymin == y && l_it->getX() < min_position->getX()))
      {
          ymin = l_it->getY();
          min_position = l_it;
      }
   /// MORE CODE
}

Comments

[clcto]

Are you sure your Points[] has at least 3 elements? Have you stepped through this with a debugger?

[Tom Fenech]

What you should do is compile your code with -g and then run it through valgrind

[PaulMcKenzie]

1) Quit using qsort. Learn to use std::sort. 2) Why are you using vector<Point> (good), and at the same time using arrays of Point (questionable)?

[pm100]

run the program under valgrind (if you can)

[Eric Fortin]

Can you post definition of Point ? Especially the implementation of swap.

[Jan Hudec]

Also learn to iterate with iterators, not indices. It works for all collections and many other objects (including plain old arrays; pointer is iterator) while indices work only for vectors and plain old arrays.

[ديناصور الأمة]

@clcto Yes has more than 3 elements. I have tried to display his content with for-loop. It works well.

[ديناصور الأمة]

@EricFortin I have added the swap method definition

[ديناصور الأمة]

@brokenfoot the main is very long but I can post a peace

[Jan Hudec]

I would upvote if it was not for the output argument (yuck; always prefer return value over output parameters; with C++11 move semantics returning vectors is trivial operation), the incorrectly used int return (if you want to check it with if, it should be a bool; and the values are both true too) and the failure to use exceptions.

[Jan Hudec]

Plus std::sort is faster. Often about twice. Because the compiler can inline it.

[Jan Hudec]

It would be nice if you also included the switch to iterators. C++ has many things that have iterators, but no indices and no way to convert them to pointers, so it's a good habit to get into.

[Claudiordgz]

failure to use exceptions? You mean I should use exceptions? We use assertions to achieve that functionality. I don't believe it is wrong or right, it is just the way things are done. Choosing between one or the other should be done from the beginning and stick to it.

[Jan Hudec]

Well, if the function returns the calculated value, than the only, and most convenient too, way to return an error is an exception. Of course calling convexHull... convexHull is well defined for less than 3 points anyway, so it should not return error (except the std::bad_alloc that std::vector::push_back may throw) anyway.

[Claudiordgz]

Seems reasonable, even though it should not fail it maybe the user may want that layer of security.

[Jan Hudec]

Layer of security often comes to bite you somewhere down the road. In most situations the preferred approach is to fail fast and loud, which in most cases means assert or throw. But I agree that what is appropriate error handling depends on a lot of context we don't have here.