c++ stl question

Da0fa930e68676fa278377ca430e02a7
0
ttigue 101 Dec 01, 2003 at 02:19

I am using the c++ standard template library’s priority_queue to implement an A* search. The priority_queue is made up of pointers to Path’s.

class Path
{ int key;
  .....

  public:
  bool operator < (Path & right);
  bool operator > (Path & right);
};

......
bool Path::operator < (Path & right)
{  return key < right.key;  }

and the priority_queue is declared as

priority_queue <Path *, vector <Path *>, std::greater <Path *> > pq;

the problem is it is not sorting the paths by the key value - it is sorting them by the address that Path * points to. I am declaring the paths dynamically so I have to give the priority_queue pointers to the Path, but its sorting them by Path * not by the less than operator. any help would be appreciated - thanks

3 Replies

Please log in or register to post a reply.

Dfb33e1feaba7ee69d54c6b824735b32
0
Sfin 101 Dec 01, 2003 at 06:47

What you need to do is create your own Comapre function. This example code should show you exactly how to do it:

http://www.cs.dal.ca/\~sedgwick/c++/pqComp.cc

P.S. This is not my code, I found it on the net, and don’t take any credit for making it.

22b3033832c5c699c856814b0cf80cb1
0
bladder 101 Dec 01, 2003 at 08:08

mmhmm. you need to define your own comparison function object. SO, something like

struct key_comparison
{
  bool operator () ( Path* p1, Path* p2 )
  {
    return (*p1) < (*p2);
  }
};

of course you’ll need to keep your greater/less then operator overloads in the Path class. Or you can have a GetKey() function and use those inside the key_comparison function object.

Da0fa930e68676fa278377ca430e02a7
0
ttigue 101 Dec 01, 2003 at 17:38

That made it work. Thanks alot!