6

優先キューを使用するのはこれが初めてです。私は学校にダイクストラのアルゴリズムを実装しようとしていますが、これを行うには最小ヒープが必要だと思いました。現在、私のノードはポインターであり、それらの重みを比較したいのですが、>と<をポインターでオーバーロードできないと思いますか？これを達成する方法はありますか？

ここまでコーディング：

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

そして、ノードの重みを比較する構造体があります

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

ただし、この演算子関数にはパラメーターが多すぎると表示されます。私はしばらくの間、ノードで最小ヒープ優先度キューを管理し、スタックし続ける方法を見つけようとしてきました。何か案は？

4

2 に答える 2

7

私があなたの質問を正しく理解しているなら、あなたが実際に望んでいるのはファンクター（より具体的にはバイナリ述語）を作ることだと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);
}
于 2013-03-26T20:13:34.950 に答える
2

bool operator()(....)実装するには、比較ファンクターが必要ですbool operator<(....)。

struct node_comparison 
{
   bool operator()( const Node* a, const Node* b ) const 
   {
    return a->totalWeight < b->totalWeight;
   }
};
于 2013-03-26T20:14:21.510 に答える