Priority queue with Pointers and Comparator C++

Question

I just started to learn C++, Half of the time I don't know what am I doing, spend hours and hours searching on Google and blindly put codes inside my project, this might be a basic question, but I just can't seems to get it right.

This is the requirement of my assignment, I need to have these:

in the Edge class:

public:
bool operator()(Edge*, Edge*)

in the Graph class:

private:
priority_queue<Edge*, vector<Edge*>, Edge> edges

I have problem declaring the priority_queue. Details:

If I directly use these, the edge class will give me an error of "must have an argument of class", I understand that I can't overload two pointers into the bool operator, so this is what I have tried:

in the Edge.cpp:

#include "Edge.h"
using namespace std;

Edge::Edge(Vertex* s, Vertex* d, double w)
{
    source = s;
    destination = d;
    weight = w;
}

double Edge::getWeight()
{
    return weight;
}

struct CompareWeight : public std::binary_function<Edge*, Edge*, bool>
{
    bool operator()(Edge* e1,Edge* e2)
    {
        double w1 = e1->getWeight();
        double w2 = e2->getWeight();

        if(w1>w2){
            return true;
        }
        else {
            return false;
        }
    }
};

^ I am not even sure about putting struct inside the class is correct or not, Plus in this cause I don't know what to put inside my Edge.h file.

in the Edge.h:

#include "Vertex.h"
class Edge
{
    public:
        Edge(Vertex*, Vertex*, double);
        double getWeight();
        friend struct CompareWeight; // ??? does not seems right
    private:
        Vertex* source;
        Vertex* destination;
        double weight;
}

As for the Graph class is where the real problem is, I can't even get pass declaring the priority queue without getting an error.

in the Graph.h

#include "Vertex.h"
#include "Edge.h"
#include <vector>
#include <queue>

class Graph
{
    public:
        ...

    private:
        priority_queue<Edge*, vector<Edge*>, Edge> edges
        // This give pointer error: no match for call to '(Edge) (Edge*&, Edge*&)'
}

second attempt:

// same as above
private:
    priority_queue<Edge*, vector<Edge*>, CompareWeight> edges
    // This give error: 'CompareWeight' not declared in this scope

I don't know why for the first error, but the second error I understood it clearly, but I don't know how to fix it, should I put something in front of CompareWeight? I tried many things, nothing work.

Any help will be greatly appreciated! otherwise I would probably just fail this course. First time asking in stackoverflow, if I did anything wrong please tell me.

Answer 1

Your requirement of implementing bool operator()(Edge*, Edge*) as a regular member of class Edge is possible, but rarely is it done that way.

Comparators for standard library algorithms come in the following idiomatic flavors, all of which must provide a strict weak ordering of the contained objects within the sequence being worked over:

1. Stand-alone functor class
2. Stand-alone operator < overload
3. Object-class member operator < overload.
4. Stand-alone function
5. Static class function
6. Static class functor class
7. A few others...

The fifth (5) on this list is the closest thing that looks like what they instruction was trying to do, but it is never implemented as operator(). It is possible to do (1) as a member of Edge, but to do so the Edge type must support default construction. I'll explain in a minute how this can be done. Of the options listed above, the best candidates for performance (likeliness of inlining) and implementation ease are (1) and (6) for this specific case. If your queue held actual Edge objects rather than Edge pointers (3) would be a natural fit as well as offer decent performance.

The point of a comparator for ordered containers and container adapters like a priority queue is to compare two items that are held within in compliance with a strict weak ordering. If you don't know what that is, see this link. In implementation, it comes down to this: if, and only if x < y return true, otherwise return false. That means the following must be enforced:

• x < x always returns false
• if x < y returns true, then y < x must return false
• if both x < y and y < x return false, then x is equivalent to y

It is a common mistake to accidentally code one's comparator to not abide by these rules. Guard against that.

Anyway, I digress. One way of doing this correctly given your class definitions and using (1) from the list above is:

Class Edge

class Edge
{
public:
    Edge(Vertex* src, Vertex* dst, double w)
        : source(src), destination(dst), weight(w)
    {
    };

    // note: const-ness
    double getWeight() const { return weight; }

    Vertex const* getSource() const { return source; }
    Vertex* getSource() { return source; }

    Vertex const* getDestination() const { return destination; }
    Vertex* getDestination() { return destination; }

private:
    Vertex* source;
    Vertex* destination;
    double weight;
};

Class CmpEdgePtrs

struct CmpEdgePtrs
{
    bool operator()(const Edge* lhs, const Edge* rhs) const
    {
        return lhs->getWeight() < rhs->getWeight();
    }
};

Class Graph

class Graph
{
    // rest of class stuff

private:
    priority_queue<Edge*, vector<Edge*>, CmpEdgePtrs> edges;
};

Honestly, this is screaming for usage of shared smart pointers, but I leave that to you. The code above stands a very strong chance of inlining the comparator throughout the usage locations within the standard library algorithms that implement the priority queue logic, and as such performance will stand a strong chance of being optimal given your constraints of a container of pointers.

---

Fulfilling Assigned Requirements

This can be done entirely within class Edge, since it is after all just a class type. The third type passed as the template parameter for the priority queue adapter is something that exposes bool operator(), and there is nothing stopping you from just making an instance of Edge do that for you. It is odd, but it will none-the-less work with a couple modifications:

First, move the bool operator()(const Edge*, const Edge*) const to the Edge class, declared as public. Second, provide a default constructor for Edge, since it will be needed by the internal algorithms of the priority queue when creating the functor to perform the comparisons.

class Edge
{
public:
    // regular parameterized construction
    Edge(Vertex* src, Vertex* dst, double w)
        : source(src), destination(dst), weight(w)
    {
    };

    // ADDED: allows parameterless initialization
    Edge() 
        : source(), designation(), weight() 
    {}

    // note: const-ness
    double getWeight() const { return weight; }

    Vertex const* getSource() const { return source; }
    Vertex* getSource() { return source; }

    Vertex const* getDestination() const { return destination; }
    Vertex* getDestination() { return destination; }

    // ADDED: used when an instance of `Edge` is used as comparator functor
    bool operator ()(const Edge* lhs, const Edge* rhs) const
    {
        return lhs->weight < rhs->weight;
    }

private:
    Vertex* source;
    Vertex* destination;
    double weight;
};


class Graph
{
    // rest of class stuff

private:
    // NOTE: uses Edge-type as the functor type that will
    //  deliver the comparison of Edge pointers.
    priority_queue<Edge*, vector<Edge*>, Edge> edges;
};

This is highly unusual, but has the benefit of allowing the functor direct access to the member variables of Edge objects being compared rather than going through public getters and setters or having to friend a comparator. It has a downside though. There is nothing stopping someone besides the container adapter from constructing Edge objects without specifying source, destination, and weight.

In short, there is little benefit to doing it like this, and potential problems in improper usage of the code required to make this work, and for that, I would recommend the first option instead.

Best of luck