23

Boost を使用した C++ プログラムで、キーが double のタプルである順序付けられていないマップを作成しようとしています。

typedef boost::tuples::tuple<double, double, double, double> Edge;
typedef boost::unordered_map< Edge, int > EdgeMap;

マップの初期化は正常に完了しますが、キーと値を入力しようとすると、

EdgeMap map;
Edge key (0.0, 0.1, 1.1, 1.1);
map[key] = 1;

次のエラー メッセージが表示されます。

/usr/include/boost/functional/hash/extensions.hpp:176: error: no matching function for call to ‘hash_value(const boost::tuples::tuple<double, double, double, double, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type>&)’

これは、タプル キーのハッシュ関数を指定する必要があるためだと思います。どうやってやるの？

編集：

以下の提案に従って、次の実装を作成しました。

#include <boost/tuple/tuple.hpp>
#include <boost/unordered_map.hpp>

typedef boost::tuples::tuple<double, double, double, double> Edge;

struct ihash
    : std::unary_function<Edge, std::size_t>
{
    std::size_t operator()(Edge const& e) const
    {
        std::size_t seed = 0;
        boost::hash_combine( seed, e.get<0>() );
        boost::hash_combine( seed, e.get<1>() );
        boost::hash_combine( seed, e.get<2>() );
        boost::hash_combine( seed, e.get<3>() );
        return seed;
    }
};

struct iequal_to
    : std::binary_function<Edge, Edge, bool>
{
    bool operator()(Edge const& x, Edge const& y) const
    {
        return ( x.get<0>()==y.get<0>() &&
                 x.get<1>()==y.get<1>() &&
                 x.get<2>()==y.get<2>() &&
                 x.get<3>()==y.get<3>());
    }
};

typedef boost::unordered_map< Edge, int, ihash, iequal_to > EdgeMap;

int main() {

    EdgeMap map;
    Edge key (0.0, 0.1, 1.1, 1.1);
    map[key] = 1;

    return 0;
}

短くすることは可能ですか？

4

6 に答える 6

12

実際、 の一般的なハッシュ関数を完全に定義できますboost::tuple。唯一の要件は、ADL によって取得されるように、同じ名前空間内に存在することです。

彼らがまだそれを書いていないことに、私は実際に驚いています。

namespace boost { namespace tuples {

  namespace detail {

    template <class Tuple, size_t Index = length<Tuple>::value - 1>
    struct HashValueImpl
    {
      static void apply(size_t& seed, Tuple const& tuple)
      {
        HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
        boost::hash_combine(seed, tuple.get<Index>());
      }
    };

    template <class Tuple>
    struct HashValueImpl<Tuple,0>
    {
      static void apply(size_t& seed, Tuple const& tuple)
      {
        boost::hash_combine(seed, tuple.get<0>());
      }
    };
  } // namespace detail

  template <class Tuple>
  size_t hash_value(Tuple const& tuple)
  {
    size_t seed = 0;
    detail::HashValueImpl<Tuple>::apply(seed, tuple);
    return seed;
  }

} }

注：私はそれが正しいことを証明しただけで、テストしていません。

于 2010-09-01T06:47:54.843 に答える
10

前付が少し必要です。の基本的な実装のため、オーバーロードが正しく解決できるように構造をboost::tuples::tuple作成します。Edgeそうしないと、一致するものはありません

  • boost::hash_value(const Edge &)
  • operator==(const Edge &, const Edge &)

以下のコード:

struct Edge {
  Edge(double x1, double x2, double x3, double x4)
    : tuple(x1,x2,x3,x4) {}
  boost::tuples::tuple<double, double, double, double> tuple;
};

// XXX: less than ideal implementation!
bool operator==(const Edge &a, const Edge &b)
{
  return a.tuple.get<0>() == b.tuple.get<0>() &&
         a.tuple.get<1>() == b.tuple.get<1>() &&
         a.tuple.get<2>() == b.tuple.get<2>() &&
         a.tuple.get<3>() == b.tuple.get<3>();
}

// XXX: me too!
std::size_t hash_value(const Edge &e)
{
  std::size_t seed = 0;
  boost::hash_combine(seed, e.tuple.get<0>());
  boost::hash_combine(seed, e.tuple.get<1>());
  boost::hash_combine(seed, e.tuple.get<2>());
  boost::hash_combine(seed, e.tuple.get<3>());
  return seed;
}

typedef boost::unordered_map< Edge, int > EdgeMap;
于 2010-08-31T19:00:15.013 に答える
1

それはすべてドキュメントにあります...

次のようなものが必要になります。

std::size_t hash_value(Edge const& e)
{
    std::size_t seed = 0;
    boost::hash_combine( seed, e.get<0>() );
    boost::hash_combine( seed, e.get<1>() );
    boost::hash_combine( seed, e.get<2>() );
    boost::hash_combine( seed, e.get<3>() );
    return seed;
}

...そしてあなたは定義することができます：

boost::unordered_map< Edge, int, boost::hash< Edge > > EdgeMap;

...実際にはこれがデフォルトであるため、明示的なハッシュ定義がなくても機能するはずです。

boost::unordered_map< Edge, int > EdgeMap;
于 2010-08-31T18:25:37.633 に答える
0

Boostのドキュメントには、必要なインターフェイスが記載されています。関係する価値観についてもっと知らなければ、これ以上言うのは難しいです。キーオブジェクトを入力として指定すると、決定論的なsize_tを生成する必要があります。つまり、結果が入力値のみに依存する純粋関数であるため、同じ入力を与えると常に同じハッシュコードが生成されます。

于 2010-08-31T18:26:24.863 に答える