Access violation with std::vector

Hi all,

I have problem with vector which I can't solve.

The key function is as follows:

Code:

---

void CHull::computeHull(std::vector<myPoint> & aPoints, std::vector<myPoint> & aHull)
{
        // Sort given points by y-coordinate (break tie with lower x-coordinate)
        // (this is automatically done inside the sorting callback function)
        CGeomUtils::sortByY(aPoints);

        myPoint p0 = aPoints.front();

        std::vector<myPoint>::iterator start = aPoints.begin() + 1;

        // Sort points in counterclockwise order by polar angle relative to p0
        // If two or more points have the same polar angle, keep just the farthest from p0
        // (others are just the convex combination of p0 and the farthest one and we don't
        // have to consider them since they won't be part of the hull)
        CGeomUtils::sortByAngleRelativeTo(p0, start, aPoints.end());

        int m = aPoints.size() - 1;

        // Clear output array
        aHull.clear();

        myPoint p1 = aPoints.at(1);
        myPoint p2 = aPoints.at(2);
        myPoint top;
        myPoint nextToTop;
        myPoint cur;

        aHull.push_back(p0);
        aHull.push_back(p1);
        aHull.push_back(p2);

        int size = 0;       

        for (int i = 3; i <= m; ++i)
        {
                size = aPoints.size();

                top = mHull.back();
                nextToTop = mHull.at(mHull.size() - 2);
                cur = aPoints.at(i);

                while ((td = CGeomUtils::getTurnDirection(nextToTop, top, cur)) != tLeft)
                {
                        aHull.pop_back();

                        // Pathological case (consider p0, p1, p2, p3 on a straight line :-))
                        if (aHull.size() < 2)
                                break;

                        top = aHull.back();
                        nextToTop = aHull.at(aHull.size() - 2);
                }

                mHull.push_back(cur);
        }
}

---

The problematic line which gives me Access Violation exception is the bold one, the blue coloured ones are those which involve that critical aPoints vector.

m (the upper bound of the 'for' loop) is typicaly let's say 1000 so aPoints contains 1000 myPoint elements. But the violation always occurs in the beginning, when i is e.g. 10. So I traced it, got the breakpoing before the bold line and what I inspected is that before the critical moment of the violation, size (which holds the current size of aPoints) suddenly gets some garbage value, for example 10967136, all of sudden.

I can't see there any command that would alter aPoints vector, but indeed there is something happening...

Thank you for any suggestions.

Please post the aPoints class. Just the class definition, not the implementation.

Please post CGeomUtils::sortByAngleRelativeTo. We don't know if you are calling std::sort correctly.

As a matter of fact, why not test by calling std::sort directly instead of indirectly as you're doing now, so as to verify the problem isn't a general problem with the sorting.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by s_k

I can't see there any command that would alter aPoints vector, but indeed there is something happening...

---

Assuming that you have sorted, then possibly the aPoints class is not safely copyable and assignable, and sorting assumes that the type that is being sorted is copyable, assignable, and safely destructable.

That's why we need to see this aPoints class.

Regards,

Paul McKenzie

Ok Paul, here it is:

Code:

---

class CGlobalStorage 
{
public:
        CGlobalStorage();
        virtual ~CGlobalStorage();

        ...       
        std::vector<myPoint> points;
        std::vector<myPoint> hull;       
};

CGlobalStorage gs;

int main(int argc, char* argv[])
{
        // This just fills gs.points with some random points
        CGeomUtils::generateRandomPoints(1000, gs.points, maxX, maxY);
       
        CHull::computeHull(gs.points, gs.hull);
}

typedef struct _myPoint
{
        int x;
        int y;

        _myPoint() : x(0), y(0) {}
        _myPoint(int _x, int _y) : x(_x), y(_y) {}
        _myPoint(const _myPoint & aP) : x(aP.x), y(aP.y) {}
} myPoint;

void CGeomUtils::sortByAngleRelativeTo(const myPoint & relativeTo, std::vector<myPoint>::iterator start,  std::vector<myPoint>::iterator end)
{
        CGeomUtils::relativePoint = relativeTo;

        std::sort(start, end, CGeomUtils::sortByAngleRelativeTo_callback);
}

bool CGeomUtils::sortByAngleRelativeTo_callback(myPoint a, myPoint b)
{
        double angle1 = CGeomUtils::getAngleRelative(CGeomUtils::relativePoint, a);
        double angle2 = CGeomUtils::getAngleRelative(CGeomUtils::relativePoint, b);

        if (CGeomUtils::IS_EQUIV(angle1, angle2))
                return false;

        if (angle1 < angle2)
                return true;

        return false;
}

---

The prototype is wrong in the sorting criteria. The types should be const references, not objects:

Code:

---

bool CGeomUtils::sortByAngleRelativeTo_callback(const myPoint& a,
                                                                              const myPoint& b)

---

Regards,

Paul McKenzie

Also,

1) typedef struct is not necessary in a C++ program:

Code:

---

struct myPoint
{
//...
};

---

2) Don't start names with leading underscores. Names with leading underscores are reserved for the compiler.

3) Don't code a copy constructor when you don't need to. The members of the myPoint struct are copyable just fine with the default copy constructor.

Regards,

Paul McKenzie

Thank you, I corrected it.

But I'm still getting the same error :( On the same line and as usual, size has right before the access violation garbage value, now it was 100852127...

What is CGeomUtils::sortByY(aPoints)? Please post this. Does this work correctly?


Did you unit test that all of these sorts worked before you applied them to your application?

Also all of this:

Code:

---

        myPoint p0 = aPoints.front();
        std::vector<myPoint>::iterator start = aPoints.begin() + 1;
      CGeomUtils::sortByAngleRelativeTo(p0, start, aPoints.end());

---

This is invalid if the vector is empty.

Regards,

Paul McKenzie

Code:

---

void CGeomUtils::sortByY(std::vector<myPoint> & aVect)
{
        // !! Beware that this put the point with lower x-coordinate in front in case of tie with y-coordinate !!
        std::sort(aVect.begin(), aVect.end(), CGeomUtils::sortByY_callback);
}

bool CGeomUtils::sortByY_callback(const myPoint & a, const myPoint & b)
{
        // !! Beware that this put the point with lower x-coordinate in front in case of tie with y-coordinate !!
        if (CGeomUtils::IS_EQUIV_Y(a, b))
        {
                if (CGeomUtils::IS_EQUIV_X(a, b))
                        return false;
                else if (a.x < b.x)
                        return true;
                return false;
        }

        if (a.y < b.y)
                return true;

        return false;
}

---

So I think it's ok...And to your second note - I know that aPoints is not empty.

Quote:

---

Originally Posted by Paul McKenzie

Did you unit test that all of these sorts worked before you applied them to your application?

---

Yes I did and I still have the testing application which proves that the sorting mechanisms are ok...

Since we don't have your entire applicaton, the only I can tell you is to watch the internals of the vector and single step until something changes. Whatever changed the internals of the vector is what is causing the problem.

Otherwise, it could be something totally unrelated to what you posted, i.e. you've corrupted memory somewhere else in your application, and the symptoms are showing up in the sorting.

You should still check for out-of-bounds conditions (such as an empty vector).

Regards,

Paul McKenzie

Quote:

---

Originally Posted by Paul McKenzie

Otherwise, it could be something totally unrelated to what you posted, i.e. you've corrupted memory somewhere else in your application, and the symptoms are showing up in the sorting.

---

Why in the sorting? I think the sorting works fine, the problem always comes up on the bold line, ie. calling aPoints.at(i).


And what I've posted is the whole application :) Well, apart from this function, which I referred to in one of my previous posts.

Code:

---

//_____________________________________________________________________________________________________
void CGeomUtils::generateRandomPoints(unsigned int count, std::vector<myPoint> & dest, int maxX, int maxY)
{
        /*
                Here we use one small trick:
               
                Since screen y-coordinates are always positive and growing from top to the bottom,
                we can't just take the point with the lowest y-coordinate as our extreme point, because
                it would be the top-most point. Instead, we will generate all points with the negative value
                of y-cord and take the lowest as usual and hence our extreme point will be the bottom-most.

                The only thing we have to have in mind is to reverse the y-coord values again in
                CGeomUtils::hullToPoints() because we need to give only positive y-coorded points to
                Polyline() when drawing the convex hull

        */

        dest.clear();

        int xVal = 0;
        int yVal = 0;

        srand((unsigned) time(NULL));

        for (unsigned int i = 0; i < count; ++i)
        {
                double d1 = (double) rand();
                double d2 = (double) rand();
                double dr = (double) RAND_MAX;
                int xVal = (d1 / dr) * maxX;
                int yVal = (d2 / dr) * maxY;
                myPoint myp(xVal, -yVal);       

                dest.push_back(myp);
        }
}

---

How are we to run the "whole application" with no main() program and data? The only way to duplicate a problem is to do it with all the information available.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by Paul McKenzie

How are we to run the "whole application" with no main() program and data? The only way to duplicate a problem is to do it with all the information available.

Regards,

Paul McKenzie

---

I posted the main() function already.

Quote:

---

Originally Posted by s_k

Why in the sorting? I think the sorting works fine, the problem always comes up on the bold line, ie. calling aPoints.at(i).

---

What is the value of "i"? Is there an element at position "i"?

That's why the problem could be that you've corrupted the memory a long time ago, and the symptoms are showing up here.

Regards,

Paul McKenzie