unordered_map hash-Funktion in c++

Brauche ich zum definieren einer unordered_map wie diese unordered_map<pair<int, int>, *Foo>was ist die syntax für die Definition und die übergabe eines hash und equal Funktionen zu dieser Karte?

Habe ich versucht, übergeben Sie dieses Objekt:

class pairHash{
public:
    long operator()(const pair<int, int> &k) const{
        return k.first * 100 + k.second;
    }
};

und kein Glück:

unordered_map<pair<int, int>, int> map = unordered_map<pair<int, int>, int>(1,
*(new pairHash()));

Ich habe keine Ahnung, was die size_type_Buskets bedeutet also gab ich es 1.
Was ist der richtige Weg, es zu tun?
Danke.

InformationsquelleAutor der Frage Vladp | 2011-08-28

  1. 43

    Dies ist eine unglückliche Unterlassung in C++11; Boost hat die Antwort in Bezug auf hash_combine. Fühlen Sie sich frei, fügen Sie es aus! Hier ist, wie ich hash-Paare:

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

namespace std
{
  template<typename S, typename T> struct hash<pair<S, T>>
  {
    inline size_t operator()(const pair<S, T> & v) const
    {
      size_t seed = 0;
      ::hash_combine(seed, v.first);
      ::hash_combine(seed, v.second);
      return seed;
    }
  };
}

    Können Sie hash_combine als Grundlage für viele andere Dinge, wie Tupel und Bereiche, so könnte man hash eine ganze (bestellt) - container, zum Beispiel, wie lange jedes Mitglied ist individuell hashable.

    Jetzt können Sie nur deklarieren Sie eine neue map:

    std::unordered_map<std::pair<int, int>, my_mapped_type> mymap;

    Wenn Sie verwenden möchten Ihre homebrew hasher (die hat noch nicht gute statistische Eigenschaften), müssen Sie die template-Parameter explizit:

    std::unordered_map<std::pair<int,int>, int, pairHash> yourmap;

    Beachten Sie, dass es gibt keine Notwendigkeit, geben Sie eine Kopie der hasher-Objekt als default ist die Standard-Konstrukt eine für Sie.

    InformationsquelleAutor der Antwort Kerrek SB

  2. 10

    Wenn Sie sind in Ordnung mit der Verwendung von Boost, eine saubere Lösung ist angewiesen auf Erhöhung der Implementierung der hash-Funktion, für Paare (die in der Tat genau das tut, was kerrek-sb erklärt in seiner Antwort). Also alles, was Sie tun müssen, ist:

    #include <unordered_map>
#include <boost/functional/hash.hpp>

using namespace std;
using namespace boost;

unordered_map<pair<int, int>, int, hash<pair<int, int>>> table;

    InformationsquelleAutor der Antwort Paul Baltescu

  3. 9

    Den return-Typ der hash-Funktion sollte size_tnicht long (obwohl dies nicht die Ursache des Fehlers). Die syntax, die Sie gezeigt haben, für die Bereitstellung eine benutzerdefinierte hash-Funktion falsch ist.

    Werden Sie auch brauchen, um eine equal-Prädikat, um die oben genannten arbeiten ordnungsgemäß.

    #include <unordered_map>
#include <utility>

using namespace std;

class pairHash{
public:
    size_t operator()(const pair<int, int> &k) const{
        return k.first * 100 + k.second;
    }
};

struct pairEquals : binary_function<const pair<int,int>&, const pair<int,int>&, bool> {
  result_type operator()( first_argument_type lhs, second_argument_type rhs ) const
  {
    return (lhs.first == rhs.first) && (lhs.second == rhs.second);
  }
};     

int main()
{
  unordered_map<pair<int, int>, int, pairHash, pairEquals> myMap;

  myMap[make_pair(10,20)] = 100;
  myMap.insert( make_pair(make_pair(100,200), 1000) );
}

    EDIT:

    Sie brauchen nicht zu definieren, das gleiche Prädikat seit operator== definiert ist, für die std::pair und es tut genau das, was ich getan habe, in pairEquals. Sie müssen nur die pairEquals definition, wenn Sie erwarten, dass der Vergleich anders gemacht werden.

    InformationsquelleAutor der Antwort Praetorian

Schreibe einen Kommentar