eine ungeordnete Karte mit Tupel als Schlüssel

Question

In einem C++ Programm mit Boost-Gebäude, versuche ich, eine ungeordnete Karte, deren Schlüssel Tupeln von Doppel zu bauen:

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

Initialisierung der Karte OK abgeschlossen ist, aber wenn ich versuchen sie es mit den Tasten zu füllen und Werte

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

ich die folgende Fehlermeldung auftreten:

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

Ich vermute, dies liegt daran, dass ich eine Hash-Funktion für die Tupel-Schlüssel angeben muss. Wie kann ich das machen?

EDIT:

die folgenden Informationen, schrieb ich die folgende Umsetzung:

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

Ist es möglich, sie zu verkürzen?

Answer 1

Sie benötigen ein bisschen front matter. Erstellen Sie aufgrund der zugrunde liegenden Implementierung von boost::tuples::tupleEdge eine Struktur, um die Überladungen ordnungsgemäß zu beheben. Andernfalls werden Sie keine Treffer erhalten für

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

-Code unten:

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

Es ist alles in der Dokumentation ...

• 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

Sie etwas brauchen würde, wie:

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

... und dann können Sie definieren:

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

... tatsächlich ist dies Standard, so dass es jetzt ohne explizite Hash-Definition funktionieren soll:

boost::unordered_map< Edge, int > EdgeMap; 

Answer 3

Die Boost-Dokumentation der required interface gibt. Ohne mehr über die Werte zu wissen, ist es schwer, viel mehr zu sagen. Wenn ein Schlüsselobjekt als Eingabe gegeben wird, muss es eine size_t erzeugen, die deterministisch ist - d. H. Es handelt sich um eine reine Funktion, bei der das Ergebnis nur vom Eingabewert abhängt, sodass die gleiche Eingabe immer denselben Hash-Code ergibt.

Answer 4

Eigentlich könnte man durchaus eine allgemeine Hash-Funktion für boost::tuple definieren. Die einzige Voraussetzung ist, dass sie sich im selben Namensraum befindet, damit sie von ADL erfasst wird.

Ich bin eigentlich überrascht, dass sie nicht schon einen geschrieben haben.

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

} } 

Hinweis: Ich habe es nur bewiesen, ich habe es nicht getestet.

Answer 5

Dieser Code von Generic hash for tuples in unordered_map/unordered_set bietet magische Unterstützung für alle C++ 11 Tupel von standardmäßigen hashbaren Typen (Strings, Ints usw.).

Es überrascht nicht, dass es der Lösung von Matthieu M. sehr ähnlich ist, aber ohne Abhängigkeiten.

Setzen Sie den Code in einer Header-Datei und schließen Sie sie und ungeordnete Sätze von Tupeln wird aus der Box arbeiten:

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

    }; 
}