make_heap関数オブジェクトを使用

Question

make_heapのためにどの演算子をオーバーロードする必要がありますか？それは（）演算子ですか？私のアルゴリズムで既に別のケースに定義されている場合私の場合は誰でもmake_heapを使う正しい方法を提供できますか？より理解するために、以下のコードをご覧ください。私のアルゴリズムで今

vertex_iterator GraphComponents::graph::find_vertex_by_key(int key) 
{ 
    return std::find_if(_vertices.begin(), _vertices.end(), GraphComponents::vertex(key)); 
} 

find_if次のstd方法でグラフを構築しながら、私は

bool operator() (vertex &v) const 
{ 
    return (v.key() == _key); 
} 

これは私がFunctionオブジェクトとして頂点を使用する使用されてきた頂点クラス内

別の状況下でここで

std::list<int> GraphComponents::graph::breadth_first_search (int key, int start_key) 
{ 
    std::vector<GraphComponents::vertex *> heap; 
    for (vertex_iterator copy_iter = _vertices.begin(); copy_iter != _vertices.end(); ++copy_iter) { 
    heap.push_back(&(*copy_iter)); 
    } 
    std::make_heap(heap.begin(), heap.end(), vertex(<should be distance>)); 
} 

私は比較して、キーを使用する必要はありませんが、私は最短距離を持つ頂点がヒープの一番上にあるので、距離のメンバーを使用します。自分のヒープを実装するのが短く、これを回避するにはどうすればよいでしょうか？

Answer 1

タイプの2つの引数をとる関数を実装し、左辺の引数を右辺の引数よりも相対的に小さくする必要がある場合はtrueを返します。 （小さいほうが大きい）

次に、その関数を第3引数としてmake_heapに渡します。または、前述のセマンティクスを使用してoperator<を実装することができます。また、関数を渡さない場合に使用されます。あなたのケースでは

http://en.wikipedia.org/wiki/Strict_weak_ordering

、あなたの要素がポインタであるので、その関数がすでにすべてのポインタ型に対して定義されているあなたは、operator<を書き込むことはできません。ですから、このような何か別の関数を記述する必要があります。

bool CompareByDistance(const GraphComponents::vertex * lhs, 
         const GraphComponents::vertex * rhs) 
{ 
    return lhs->distance() < rhs->distance(); 
}