Delete does not recognise pointer allocation from List

Question

When I try to call delete on pointers to a struct Vertex (allocated with Vertex * v = new Vertex, then successfully used and stored in an std::list in my class destructor, I get this runtime error:

graphtake3(12325,0x100082000) malloc: *** error for object 0x100200340: pointer being freed was not allocated
***

The pointers are definitely being allocated, as the application runs fine, and everything appears as it should in a stack trace, but for some reason, delete can't seem to deallocated them. What's happening here, and why doesn't delete work?

Here is the relevant abbreviated code:

#include <vector>
#include <list>
#include <iostream>
#include <string>

enum Color {BLACK, GREY, WHITE};

struct Vertex {
    int id;
    std::string name;
    Color color;

    Vertex();
    Vertex(std::string name);

    ~Vertex();

};
class Graph {
    std::vector<std::list<Vertex *>> adjList;

public:
    Graph();
    Graph (int nodeCount);

    ~Graph();

    int newVertex();
    int newVertex(std::string name);
    void newUnDirectedEdge(int v1, int v2);
    void newDirectedEdge(int v1, int v2);
    std::list<Vertex*> getConnections(int v);

    friend std::ostream& operator<<(std::ostream& os, const Graph& g);



};

and

#include "Graph.hpp"

Vertex::Vertex() {
    color = WHITE;
}

Vertex::Vertex(std::string name) {
    this->name = name;
    color = WHITE;
}

Vertex::~Vertex() {

}

Graph::Graph() {

}

Graph::Graph(int nodeCount) {
    adjList.reserve(nodeCount);
}

Graph::~Graph(){
    for (int i = 0; i<adjList.size(); i++) {

        for (std::list<Vertex*>::iterator iterator = adjList[i].begin(), end = adjList[i].end(); iterator !=end; iterator++) {
            delete (*iterator); //fails
        }
    }
}

int Graph::newVertex() {
    Vertex * v = new Vertex();
    adjList.push_back(std::list<Vertex *>(1, v));
    v->id= (int)adjList.size()-1;
    return v->id;
}

int Graph::newVertex(std::string name) {
    Vertex * v = new Vertex();
    adjList.push_back(std::list<Vertex *>(1, v));
    v->id= (int)adjList.size()-1;
    v->name= name;
    return v->id;
}

void Graph::newUnDirectedEdge(int v1, int v2) {
    newDirectedEdge(v1, v2);
    newDirectedEdge(v2, v1);
}

void Graph::newDirectedEdge(int v1, int v2) {
    Vertex * vertex2 = adjList[v2].front();
    adjList[v1].push_back(vertex2);

}
std::list<Vertex*> Graph::getConnections(int v) {
    return adjList[v];
}

std::ostream& operator<<(std::ostream& os, const Graph& g) {
    for (int i = 0; i<g.adjList.size(); i++) {
        for (std::list<Vertex*>::const_iterator iterator = g.adjList[i].begin(), end = g.adjList[i].end(); iterator !=end; iterator++) {
            os << (*iterator)->id << " (" << (*iterator)->name << ") ";
        }
        os << '\n';
    }

    return os;
}

with main:

#include <iostream>
#include "Graph.hpp"


int main(int argc, const char * argv[]) {
    Graph graph(5);

    int v1 = graph.newVertex("Paris");
    int v2 = graph.newVertex("London");
    int v3 = graph.newVertex("Lyon");
    int v4 = graph.newVertex("Nice");
    int v5 = graph.newVertex("Marseille");
    int v6 = graph.newVertex("La Rochelle");
    int v7 = graph.newVertex("Toulon");

    graph.newUnDirectedEdge(v2, v1);
    graph.newUnDirectedEdge(v1, v3);
    graph.newUnDirectedEdge(v1, v4);
    graph.newUnDirectedEdge(v3, v4);
    graph.newUnDirectedEdge(v5, v4);
    graph.newUnDirectedEdge(v7, v5);

    std::cout << graph;


    return 0;
}

Answer 1

The minute you do this, you are set up for disaster:

void Graph::newDirectedEdge(int v1, int v2) {
    Vertex * vertex2 = adjList[v2].front();
    adjList[v1].push_back(vertex2);
}

The problem is that you have not distinguished who owns a pointer. In this case, you have simply copied a pointer onto the list. But when you come around to ~Graph, you delete all pointers in the list. Some of them were obtained by new, and some were copied by the above function.

So the error was right: the pointer was not allocated. What happened is you already deleted it, and then you deleted a copy of it.

You need to rethink your design and consider pointer ownership. Or you could use the sledge-hammer approach of converting everything to std::shared_ptr. But I wouldn't actually recommend that.

A common approach for graphs is to store all your vertices (in a std::vector) and then connect in a separate structure as you have done. Then in the destructor you just rip through the vector. You could even take this as an opportunity learn how to use std::unique_ptr. =)

Answer 2

Is the problem occur in the newDirectedEdge function? In the implement of it, it copy pointer and insert list again, then two pointers for one address in the list, delete first time is ok, and second time ... crash ...