Geek asks and answers

STL priority queue and pointer overload

This is my first time using a priority queue. I am trying to implement Dijkstra’s algorithm for school, and I thought I needed a little heap to do this. Now my nodes are pointers, and I want to compare their weight, but I don’t think I can overload> with pointers? Is there any way I could do this?

Code at the moment:

priority_queue<Node*, vector<Node*>, node_comparison> minHeap;

And then I have a structure to compare node weights

struct node_comparison 
{
   bool operator<( const Node* a, const Node* b ) const 
   {
    return a->totalWeight < b->totalWeight;
   }
};

However, he says there are too many parameters for this operator function. I was trying to figure out how I can manage the priority mini-heap queue with my nodes for a while and keep getting stuck. Any ideas?

+5
source share
2 answers

, , node_comparison (, ):

struct node_comparison 
{
    bool operator () ( const Node* a, const Node* b ) const 
    {
        return a->totalWeight < b->totalWeight;
    }
};

- , (operator ()) , :

Node* p1 = ...;
Node* p2 = ...;
node_comparison comp;
bool res = comp(p1, p2) // <== Invokes your overload of operator ()

, std::priority_queue , , , .

, ( , , , ):

#include <cmath>

struct my_comparator
{
    my_comparator(int x) : _x(x) { }

    bool operator () (int n, int m) const
    {
        return abs(n - _x) < abs(m - _x);
    }

    int _x;
};

, , , , . :

#include <queue>
#include <iostream>

void foo(int pivot)
{
    my_comparator mc(pivot);
    std::priority_queue<int, std::deque<int>, my_comparator> pq(mc);

    pq.push(9);
    pq.push(2);
    pq.push(17);

    while (!pq.empty())
    {
        std::cout << pq.top();
        pq.pop();
    }
}

int main()
{
    foo(7);

    std::cout << std::endl;

    foo(10);
}
+6

bool operator()(....), bool operator<(....):

struct node_comparison 
{
   bool operator()( const Node* a, const Node* b ) const 
   {
    return a->totalWeight < b->totalWeight;
   }
};
+2

More articles:


All Articles