Wie kann ich eine ungeordnete Menge von Paaren von ganzen zahlen in C++?

Im folgenden Programm wird nicht kompiliert, eine ungeordnete Menge von Paaren von ganzen zahlen, aber es funktioniert für ganze zahlen. Kann unordered_set und Ihre member-Funktionen verwendet werden, die auf Benutzer-definierte Typen, und wie kann ich es definieren? 

#include <unordered_set>
...

class A{
...
private: 
    std::unordered_set< std::pair<int, int> > u_edge_;
};

Compiler-Fehler:

Fehler: keine passende Funktion für Aufruf von " std::unordered_set >::unordered_set()'

InformationsquelleAutor Pippi | 2013-03-01
  1. 22

    Ihren code kompiliert auf VS2010 SP1 (VC10), aber es versäumt, zu kompilieren mit GCC-g++ 4.7.2.

    Allerdings möchten Sie vielleicht zu prüfen boost::hash aus Boost.Funktionale hash ein std::pair (mit diesem Zusatz-code, kompiliert auch mit g++).

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

class A
{
private: 
    std::unordered_set< 
        std::pair<int, int>, 
        boost::hash< std::pair<int, int> > 
    > u_edge_;
};
    InformationsquelleAutor Mr.C64
  2. 36

    Es gibt keine standard-Weg, der die Berechnung eines hash auf ein paar. Fügen Sie diese definition mit Ihrer Datei:

    struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};

    Nun können Sie es wie folgt:

    std::unordered_set< std::pair<int, int>,  pair_hash> u_edge_;

    Dies funktioniert, weil pair<T1,T2> definiert Gleichheit. Für benutzerdefinierte Klassen, die nicht bieten eine Methode zum testen der Gleichheit, die Sie möglicherweise benötigen, um eine separate Funktion, um zu testen, ob zwei Instanzen gleich sind, um einander.

    Natürlich ist diese Lösung beschränkt sich auf ein paar von zwei zahlen. Hier ist ein link zu einer Antwort, die Ihnen hilft, zu definieren, eine mehr Allgemeine Weise des Verdienens des hash für mehrere Objekte.

    InformationsquelleAutor dasblinkenlight
  3. 8

    Das problem ist, dass std::unordered_set ist mit std::hash Vorlage zu berechnen hashes für seine Einträge und es gibt keine std::hash Spezialisierung für Paare. So haben Sie zwei Dinge tun:

    1. Entscheiden, welche hash-Funktion, die Sie verwenden möchten.
    2. Spezialisieren std::hash für Ihre Schlüssel-Typ (std::pair<int, int>) Verwendung dieser Funktion.

    Hier ist ein einfaches Beispiel:

    #include <unordered_set>

namespace std {
template <> struct hash<std::pair<int, int>> {
    inline size_t operator()(const std::pair<int, int> &v) const {
        std::hash<int> int_hasher;
        return int_hasher(v.first) ^ int_hasher(v.second);
    }
};

}

int main()
{
    std::unordered_set< std::pair<int, int> > edge;
}
    • Andy 'Schleichen' s Antwort hinzufügen, std-namespace. Außerdem ist es nicht illegal, nur zu undefiniertem Verhalten. Auf GCC von einer bestimmten version ist es immer gut funktionieren.
    InformationsquelleAutor
  4. 3

    Müssen Sie eine Spezialisierung für std::hash<> funktioniert mit std::pair<int, int>. Hier ist ein sehr einfaches Beispiel von, wie könnte man definieren, ist die Spezialisierung:

    #include <utility>
#include <unordered_set>

namespace std
{
    template<>
    struct hash<std::pair<int, int>>
    {
        size_t operator () (std::pair<int, int> const& p)
        {
            //A bad example of computing the hash, 
            //rather replace with something more clever
            return (std::hash<int>()(p.first) + std::hash<int>()(p.second));
        }
    };
}

class A
{
private:
    //This won't give you problems anymore
    std::unordered_set< std::pair<int, int> > u_edge_;
};
    InformationsquelleAutor Andy Prowl
  5. 1

    Ihnen fehlt eine hash-Funktion für std::pair<int, int>>. Zum Beispiel,

    struct bad_hash
{
  std::size_t operator()(const std::pair<int,int>& p) const
  {
    return 42;
  }
};

....

std::unordered_set< std::pair<int, int>, bad_hash> u_edge_;

    Können Sie sich auch spezialisieren std::hash<T> für std::hash<std::pair<int,int>>, in dem Fall kann man weglassen, der zweite template-parameter.

    • Ihre functor sollten exten std::unary_function
    • Ich dachte das Zeug veraltet.
    • Warum sollte es das tun? Diese Klasse erfüllt alle hash-Anforderungen.
    • Fair genug, aber ich arbeite immer noch mit C++03 bei der Arbeit.
    • Weil Sie nicht wissen, wer sonst noch Ihre funktoren.
    • Ich kenne das Gefühl! Aber da die Frage beschäftigt sich mit std::unordered_set ich denke, es ist sicher davon ausgehen, dass OP will einen C++11-Lösung.

    InformationsquelleAutor juanchopanza
  6. 1

    Den anderen Antworten hier alle vorschlagen, Aufbau einer hash-Funktion, die irgendwie verbindet Sie Ihre zwei Ganzzahlen.

    Dies funktionieren wird, aber produziert nicht-unique-hashes. Obwohl dies ist gut für Ihre Nutzung des unordered_set für einige Anwendungen ist es möglicherweise nicht akzeptabel ist. In Ihrem Fall, wenn Sie geschehen, wählen Sie eine schlechte hash-Funktion, kann es dazu führen, dass viele unnötige Kollisionen.

    Aber können Sie produzieren, eindeutige hashes!

    int ist in der Regel 4 bytes. Könnten Sie dies explizit durch die Verwendung int32_t.

    Den hash-Datentyp ist std::size_t. Auf den meisten Maschinen, das ist 8 Byte. Sie können überprüfen, diese bei der Zusammenstellung.

    Seit ein paar besteht aus zwei int32_t - Typen, können Sie beide zahlen in ein std::size_t um einen eindeutigen hash.

    Die wie folgt aussieht (ich kann nicht erinnern, kurzentschlossen, wie um den compiler zu zwingen behandeln ein Wert mit Vorzeichen, als wäre es für unsigned bit-manipulation, so habe ich das folgende geschrieben für uint32_t.):

    #include <cassert>
#include <cstdint>
#include <unordered_set>
#include <utility>


struct IntPairHash {
  std::size_t operator()(const std::pair<uint32_t, uint32_t> &p) const {
    assert(sizeof(std::size_t)>=8);  //Ensure that std::size_t, the type of the hash, is large enough
    //Shift first integer over to make room for the second integer. The two are
    //then packed side by side.
    return (((uint64_t)p.first)<<32) | ((uint64_t)p.second);
  }
};

int main(){
  std::unordered_set< std::pair<uint32_t, uint32_t>, IntPairHash> uset;
  uset.emplace(10,20);
  uset.emplace(20,30);
  uset.emplace(10,20);
  assert(uset.size()==2);
}
    InformationsquelleAutor Richard
  7. 0

    Wie bereits erwähnt, in den meisten anderen Antworten auf diese Frage, müssen Sie, um eine hash-Funktion für std::pair<int, int>. Da jedoch C++11, Sie können auch eine lambda-Ausdruck statt der Definition einer hash-Funktion. Der folgende code nimmt die Lösung gegeben durch dasblinkenlight als Grundlage:

    auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);

    Code auf Ideone

    Möchte ich wiederholen dasblinkenlight s Haftungsausschluss: Diese Lösung beschränkt sich auf ein paar von zwei zahlen. Diese Antwort liefert die Idee für eine Allgemeine Lösung.

    InformationsquelleAutor honk
Schreibe einen Kommentar