Making a min heap that holds pair <int, custom class>

Question

I am designing a bipartite graph of Actor and Movie objects that I want to perform djikstra's algorithm on in order to find the shortest path between two Actor objects.

I already have my graph designed and building. Here is my design if you are interested...

actor.h:

/* (Vertex) Object Class to represent actors */
 class ActorNode {
         friend class Movie;
         friend class ActorGraph;
     public:
         /*Member Variables*/
         std::string name;
         std::set<Movie*> movies;
         /*Constructor*/
         ActorNode(std::string name) : name(name) {}
         /*Destructor*/
         ~ActorNode();

         /*Getters and Setters*/
         std::string getName();
         void setName(std::string actor);

         /*Member Functions*/

 };

movie.h:

 class Movie {
     public:
         friend class ActorNode;
         friend class ActorGraph;

         std::string name;
         int year;
         int weight;
         std::set<ActorNode*> cast;
         /*Constructor*/
         Movie(std::string name, int year) : name(name), year(year), weight(1) {}
         /*Destructor*/
         ~Movie();
         /*Getters and Setters*/
         std::string getMovie();
         void setMovie(std::string movie);

         int getYear();
         void setYear(int yr);

         int getWeight();
         void setWeight(int wt);

         /*Member Functions*/
 };

ActorGraph.h:

  class ActorGraph {
       public:
         unordered_map<std::string,ActorNode*> actorMap;
         unordered_map<std::string,Movie*> movieMap;

         ActorGraph(void);

         bool loadFromFile(const char* in_filename, bool use_weighted_edges);

     };

The function loadFromFile reads from a file where each line is an actor and movie they starred in along with it's year. Just allows me to more easily create a graph from a text file.

Anyways my question is in trying to implement djikstra's with my data structure.

I want to use a priority queue of pair of ints,ActorNode* where the int is going to represent my distance from the source. A priority queue by default is a max_heap but I want to make it a min heap. This is covered in some other topics where this is shown...

std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;

so i tried to follow this example for my purposes...

std::priority_queue<std::pair<int,ActorNode*>,std::vector<std::pair<int,ActorNode*>,std::greater<int>> min_heap;

but it says arguments 2 and 3 of are invalid. Is there a way to make a priority queue how I want to? Thank you!

UPDATE

OK so I have written my comparison class...

/* comparison class */
 class pairCompare{
     public:
         typedef std::pair<int, ActorNode*> p;

         struct compare{
             bool operator()(const p& a, const p& b) {
                 if (a.first > b.first) return true;
                 else return false;
             }
         };

     private:
         std::priority_queue<p,std::vector<std::pair<int,ActorNode*>>,pairCompare> pq; };

but now getting an incomplete type error...

In file included from /usr/include/c++/5/queue:64:0,
                 from movie.h:6,
                 from actor.h:8,
                 from ActorGraph.h:14,
                 from ActorGraph.cpp:15:
/usr/include/c++/5/bits/stl_queue.h: In instantiation of ‘class std::priority_queue<std::pair<int, ActorNode*>, std::vector<std::pair<int, ActorNode*> >, pairCompare>’:
ActorGraph.h:61:84:   required from here
/usr/include/c++/5/bits/stl_queue.h:391:18: error: ‘std::priority_queue<_Tp, _Sequence, _Compare>::comp’ has incomplete type
       _Compare   comp;

I researched this and the solution I found was I should forward declare my ActorNode class within my comparison class, but doesn't fix the error. Did I create my comparison class correctly? Trying to have it produce a priority queue that is a min heap.

Other question: Assuming I can get this comparison class working... Do i use the member variable, pq, by creating a comparePairs object? Maybe it would just be easier to create the compare class separate the pq that will be using it. Just seems weird to actually create a comparePairs object vs just making a priority queue and using comparePairs as the 3rd argument for what comparison to use.

Answer 1

In this line,

std::priority_queue<std::pair<int,ActorNode*>,std::vector<std::pair<int,ActorNode*>,std::greater<int>> min_heap;

In the second argument,

std::vector<std::pair<int,ActorNode*> . You don't close the angle braces. Try this:

std::priority_queue<std::pair<int,ActorNode*>,std::vector<std::pair<int,ActorNode*>>,std::greater<int>> min_heap;

On a side note, when I used to do Djikstra's or A*, I found that the std::map performed way better than the std::priority_queue. Could have been an implementation problem on my side though. You may want to check std::map if you are concerned about performance.