0

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

私が持っている頂点クラスの中に

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

これは、次のstdメソッドfind_ifでグラフを作成するときに使用されます。

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

今、私のアルゴリズムでは、頂点を別のコンテキストで関数オブジェクトとして使用したいと思います。

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>));
}

ここでは、比較でキーを使用したくありませんが、距離メンバーを使用して、距離が最も短い頂点がヒープの最上部になるようにします。自分のヒープを実装するのに足りない場合、これを回避するための推奨される方法は何ですか？

4

1 に答える 1

5

タイプの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();
}
于 2012-04-16T01:13:28.617 に答える