C++ memorizzando un valore in una coppia non ordinata

Question

Voglio memorizzare un valore in virgola mobile per una coppia non ordinata di un numero intero. Non riesco a trovare alcun tipo di tutorial facile da capire per questo. E.g per la coppia non ordinata {i,j} Desidero memorizzare un valore in virgola mobile f. Come posso inserire, memorizzare e recuperare valori come questo?

Answer 1

Ecco po 'di codice indicativo:

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

noti che si basa sulla convenzione che si memorizzano i coppia non ordinata con il numero più basso prima (se non sono uguali). Potresti trovare conveniente scrivere una funzione di supporto che prende una coppia e la restituisce in quell'ordine, quindi puoi usare quella funzione quando inserisci nuovi valori nella mappa e quando usi una coppia come chiave per cercare di trovare un valore nella mappa carta geografica.

uscita:

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

vedi sul ideone.com. Se si desidera eseguire una funzione hash migliore, è sufficiente cercare un'implementazione di hash_combine (o utilizzare boost) - molte domande qui su SO, che spiegano come farlo per std::pair<> s.

Answer 2

Si implementa un tipo UPair con i requisiti e sovraccarico ::std::hash (che è la rara occasione in cui è consentito implementare qualcosa in std).

#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

modo semplice per gestire le coppie non ordinate int sta usando std::minmax(i,j) per generare std::pair<int,int>. In questo modo è possibile implementare lo storage come questo:

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)] 

Certo corretta hashing darebbe un po 'di prestazioni, ma c'è poco danno in rimandare questo tipo di ottimizzazione.