Xây dựng một bản đồ có thứ tự với các bộ như phím

Question

Trong một chương trình C++ với Boost, tôi đang cố gắng để xây dựng một bản đồ có thứ tự mà phím tuples của đôi:

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

Khởi tạo bản đồ hoàn OK, tuy nhiên, khi tôi cố gắng để cư nó với các phím và đánh giá cao

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

tôi gặp phải thông báo lỗi sau:

/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>&)’ 

Tôi đoán điều này là bởi vì tôi cần phải chỉ định một hàm băm cho các khóa tuple. Làm thế nào tôi có thể làm điều đó?

EDIT:

Tiếp theo gợi ý dưới đây, tôi đã viết thực hiện như sau:

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

Có thể rút ngắn nó?

Answer 1

Bạn cần một chút front matter. Do việc triển khai cơ bản là boost::tuples::tuple, hãy tạo cấu trúc Edge để cho phép quá tải giải quyết chính xác. Nếu không, bạn sẽ không nhận được các trận đấu cho

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

Mã dưới đây:

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; 

Answer 2

Đó là tất cả trong tài liệu ...

• http://www.boost.org/doc/libs/1_38_0/doc/html/hash/custom.html
• http://www.boost.org/doc/libs/1_38_0/doc/html/hash/combine.html

Bạn sẽ cần một cái gì đó như:

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

... và sau đó bạn có thể xác định:

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

... thực sự đây là mặc định, vì vậy nó sẽ làm việc mà không cần định nghĩa rõ ràng băm bây giờ:

boost::unordered_map< Edge, int > EdgeMap; 

Answer 3

Các tài liệu Boost cung cấp cho các required interface. Không biết nhiều hơn về các giá trị liên quan, thật khó để nói nhiều hơn. Cho một đối tượng quan trọng làm đầu vào, nó phải tạo ra một size_t là xác định - nghĩa là, nó là một hàm thuần túy, trong đó kết quả phụ thuộc hoàn toàn vào giá trị đầu vào, vì vậy cho cùng một đầu vào sẽ luôn tạo ra cùng một mã băm.

Answer 4

Trên thực tế, bạn hoàn toàn có thể định nghĩa một hàm băm chung boost::tuple. Yêu cầu duy nhất là nó sống trong cùng một không gian tên để nó được chọn bởi ADL.

Tôi thực sự ngạc nhiên khi họ chưa viết.

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

} } 

Lưu ý: Tôi chỉ chứng minh là đúng, tôi chưa thử nghiệm nó.

Answer 5

Mã này từ Generic hash for tuples in unordered_map/unordered_set cung cấp hỗ trợ kỳ diệu cho tất cả các C++ 11 bộ tiêu chuẩn của các loại có thể băm (chuỗi, int, v.v ...).

Không có gì đáng ngạc nhiên khi nó trông rất giống với giải pháp của Matthieu M. ở trên nhưng không có phụ thuộc tăng cường.

Đặt mã trong một tập tin header và bao gồm nó và bộ có thứ tự của các bộ sẽ làm việc ra khỏi hộp:

#include <tuple> 
namespace std{ 
    namespace 
    { 

     // Code from boost 
     // Reciprocal of the golden ratio helps spread entropy 
     //  and handles duplicates. 
     // See Mike Seymour in magic-numbers-in-boosthash-combine: 
     //  https://stackoverflow.com/questions/4948780 

     template <class T> 
     inline void hash_combine(std::size_t& seed, T const& v) 
     { 
      seed ^= hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); 
     } 

     // Recursive template code derived from Matthieu M. 
     template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1> 
     struct HashValueImpl 
     { 
      static void apply(size_t& seed, Tuple const& tuple) 
      { 
      HashValueImpl<Tuple, Index-1>::apply(seed, tuple); 
      hash_combine(seed, get<Index>(tuple)); 
      } 
     }; 

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

    template <typename ... TT> 
    struct hash<std::tuple<TT...>> 
    { 
     size_t 
     operator()(std::tuple<TT...> const& tt) const 
     {            
      size_t seed = 0;        
      HashValueImpl<std::tuple<TT...> >::apply(seed, tt);  
      return seed;         
     }            

    }; 
}