C++ Speichern eines Werts in einem ungeordneten Paar

Question

Ich möchte einen Gleitkommawert für ein ungeordnetes Paar Ganzzahlen speichern. Ich kann dazu keine leicht verständlichen Tutorials finden. ZB für das ungeordnete Paar {i,j} Ich möchte einen Fließkommawert f speichern. Wie kann ich Werte wie diese einfügen, speichern und abrufen?

Answer 1

Hier einige indikative Code:

#include <iostream> 
#include <unordered_map> 
#include <utility> 

struct Hasher 
{ 
    int operator()(const std::pair<int, int>& p) const 
    { 
     return p.first^(p.second << 7)^(p.second >> 3); 
    } 
}; 

int main() 
{ 
    std::unordered_map<std::pair<int,int>, float, Hasher> m = 
    { { {1,3}, 2.3 }, 
     { {2,3}, 4.234 }, 
     { {3,5}, -2 }, 
    }; 

    // do a lookup 
    std::cout << m[std::make_pair(2,3)] << '\n'; 
    // add more data 
    m[std::make_pair(65,73)] = 1.23; 
    // output everything (unordered) 
    for (auto& x : m) 
     std::cout << x.first.first << ',' << x.first.second 
      << ' ' << x.second << '\n'; 
} 

Beachten Sie, dass es auf der Konvention beruht, die Sie speichern die ungeordneten Paare mit der niedrigeren Nummer zuerst (wenn sie nicht gleich ist). Sie können es als bequem empfinden, eine Hilfsfunktion zu schreiben, die ein Paar akzeptiert und in dieser Reihenfolge zurückgibt, sodass Sie diese Funktion beim Einfügen neuer Werte in die Map und beim Verwenden eines Paares als Schlüssel zum Suchen nach einem Wert in der Karte.

Ausgang:

4.234 
3,5 -2 
1,3 2.3 
65,73 1.23 
2,3 4.234 

Sehen Sie es auf ideone.com. Wenn Sie eine bessere Hash-Funktion erstellen möchten, suchen Sie einfach eine Implementierung von hash_combine (oder verwenden Sie Boost's) - viele Fragen hier auf SO erklärt, wie das für std::pair<> s zu tun.

Answer 2

Sie implementieren einen Typ UPair mit Ihren Anforderungen und Überlast ::std::hash (das ist die seltene Gelegenheit, dass Sie etwas in std implementieren können).

#include <utility> 
#include <unordered_map> 

template <typename T> 
class UPair { 
    private: 
    ::std::pair<T,T> p; 
    public: 
    UPair(T a, T b) : p(::std::min(a,b),::std::max(a,b)) { 
    } 
    UPair(::std::pair<T,T> pair) : p(::std::min(pair.first,pair.second),::std::max(pair.first,pair.second)) { 
    } 
    friend bool operator==(UPair const& a, UPair const& b) { 
     return a.p == b.p; 
    } 
    operator ::std::pair<T,T>() const { 
     return p; 
    } 
}; 
namespace std { 
    template <typename T> 
    struct hash<UPair<T>> { 
    ::std::size_t operator()(UPair<T> const& up) const { 
     return ::std::hash<::std::size_t>()(
       ::std::hash<T>()(::std::pair<T,T>(up).first) 
      )^
      ::std::hash<T>()(::std::pair<T,T>(up).second); 
     // the double hash is there to avoid the likely scenario of having the same value in .first and .second, resulinting in always 0 
     // that would be a problem for the unordered_map's performance 
    } 
    }; 
} 

int main() { 
    ::std::unordered_map<UPair<int>,float> um; 
    um[UPair<int>(3,7)] = 3.14; 
    um[UPair<int>(8,7)] = 2.71; 
    return 10*um[::std::make_pair(7,3)]; // correctly returns 31 
} 

Answer 3

einfache Weise ungeordnet int-Paare zu handhaben ist unter Verwendung std::minmax(i,j)std::pair<int,int> zu erzeugen. Auf diese Weise können Sie Ihre Speicher wie folgt implementieren:

std::map<std::pair<int,int>,float> storage; 
    storage[std::minmax(i,j)] = 0.f; 
    storage[std::minmax(j,i)] = 1.f; //rewrites storage[(i,j)] 

Zugegeben richtige Hashing Sie etwas mehr Leistung geben würde, aber es gibt wenig Schaden in dieser Art von Optimierung zu verschieben.