C++: "Error: Pointer being freed was not allocated" when handling large lists

Question

I am trying to process some data in a std::vector made of 2D points; basically, I need to check whether or not all points are, directly or indirectly through another point, linked by a certain relationship that I don't think needs to be detailed here.

In order to process my data properly, I copied the data from the vector and used lists for faster handling.

I wrote the following 2D vector class:

class float2D {
public:
    float x, y;

    float2D(): x(0), y(0) {}
    float2D(int a, int b): x(a), y(b) {}

    bool CheckStuffWith(float2D &u); // does some math
};

The code used to process data looks like this:

bool CheckStuffInVector(vector<float2D> const &data) { 
    if (data.size() < 2) return true;

    // Copy the data in a list, will be thinned out progressively
    list<float2D> data_copy(data.begin(), data.end());

    // Points used to CheckStuff with the remaining points in data_copy
    list<float2D> processed_data;

    // Choose arbitrarily the last element to compare with the others
    processed_data.push_back(data_copy.back());
    data_copy.pop_back();

    list<float2D>::iterator it1;
    list<float2D>::iterator it2 = data_copy.begin();

    while (!processed_data.empty()) {
        it1 = processed_data.begin();
        if (it1->CheckStuffWith(*it2)) {
            // *it2 fulfills the relationship
            // Remove the point from data_copy
            // and put it in processed_data
            processed_data.push_back(*it2);
            data_copy.erase(it2);
        } else {
            // Move on to the next point to process
            it2++;
        }
        if (it2 == data_copy.end() && !data_copy.empty()) {
            // We checked all the necessary stuff with *it1
            // No need to keep it in processed_data
            processed_data.pop_front();
            it2 = data_copy.begin();
        } else if (data_copy.empty()) {
            break;
        }
    }

    return data_copy.empty();
}

This runs fine with relatively low values for data.size(), but I need it to work for bigger values. When the vector's size is 1,000,000, I get the following runtime error:

malloc: *** error for object 0x7fac0e341240: pointer being freed was not allocated

I can't figure out where that comes from. I probably overlooked something, but I can't see what it is; I figured an outsider's look might help :)

I also want to point out that such a problem could be handled using a tree structure, but because of the size of the problem, that might cause the tree's height to be very big (thus, risk of stack overflow?) and the fact that I want something that runs fast, I thought I'd be better off doing it this way.

Thanks in advance!

Answer 1

When you do a data_copy.erase(it2) you invalidate iterator it2, then you dereference the iterator in the next iteration of the while loop. This is UB.

I suggest you resolve this with replacing the erase line with this

it2 = data_copy.erase(it2)

which will replace the it2 iterator with a valid iterator pointing to the next element or the data_copy.end() if the list is empty.