segmentation fault while inserting into priority queue

Question

My definition of priority queue is:

template<typename Node, typename Cmp = std::less<Node> >
struct deref_compare : std::binary_function<Node*,Node*,bool>
{
    deref_compare(Cmp const& cmp = Cmp())
    : cmp(cmp) {}

    bool operator()(Node* a, Node* b) const {
        return (a->getfValue()> b->getfValue());
    }

private:
    Cmp cmp;
};

typedef deref_compare<Node,std::greater<Node> > my_comparator_t;
priority_queue<Node*,vector<Node*>,my_comparator_t> openq;

I am doing:

openq.push(myNode)

After entering 3-4 nodes I am getting segmentation fault.

mynode is not empty.

How can i resolve it?

Answer 1

We need to see the code where you're inserting the nodes. It sounds like one of the nodes is being destroyed after being inserted, perhaps you're inserting a pointer to a stack-based object?

Also, it's not the problem, but your cmp is never being used, you're always doing a greater-than comparison.

Answer 2

Looks familiar.

Unfortunately you screwed up the template. If you don't want a generic solution for comparing pointers you could just as well write your functor without any template magic:

struct my_compare {
    bool operator()(Node const* n1, Node const* n2) const {
        return n1->getfValue() > n1->getfValue();
    }
};

priority_queue<Node*,vector<Node*>,my_compare> foo;

As for the error you're getting. You didn't give us enough information. It seems the problem is not with the functor you used. It's more likely that the rest of your code is to blame.

I also hope you that your nodes are managed (as in life-time management) by some other data structure (like a std::set, for example) and that they live long enough. Otherwise, it's easy to make mistakes that lead to memory leaks or undefined behaviour. Keep in mind that automatic objects (those that live on the "stack") are destroyed when their scope is left and that pointers to objects that live inside another container might become invalid after modifying the container. Check out the guarantees various containers make about iterators and when/if iterators are invalidated.