C++ stocker une valeur dans une paire non ordonnée

Question

Je souhaite stocker une valeur à virgule flottante pour une paire non ordonnée d'entiers. Je suis incapable de trouver des tutoriels faciles à comprendre. E.g pour la paire non ordonnée {i,j} Je veux stocker une valeur en virgule flottante f. Comment insérer, stocker et récupérer des valeurs comme celle-ci?

Answer 1

est ici un code indicatif:

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

Notez qu'il repose sur la convention que vous stockez les paires non ordonnées avec le nombre inférieur d'abord (si elles ne sont pas égaux). Vous pourriez trouver pratique d'écrire une fonction de support qui prend une paire et la retourne dans cet ordre, ainsi vous pouvez utiliser cette fonction lorsque vous insérez de nouvelles valeurs dans la carte et lorsque vous utilisez une paire comme clé pour essayer de trouver une valeur dans le carte.

Sortie:

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

Voir sur ideone.com. Si vous voulez faire une meilleure fonction de hachage, traquez simplement une implémentation de hash_combine (ou utilisez boost) - beaucoup de questions ici sur SO expliquant comment faire cela pour std::pair<> s.

Answer 2

Vous implémentez un type UPair avec vos exigences et surcharge ::std::hash (qui est l'occasion rare que vous êtes autorisé à implémenter quelque chose dans 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

façon simple à manipuler des paires non ordonnées int utilise pour générer std::minmax(i,j)std::pair<int,int>. De cette façon, vous pouvez mettre en œuvre votre stockage comme ceci:

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

hash Il est vrai que bon vous donnerait un peu de performance supplémentaire, mais il y a peu de mal à remettre à plus tard ce genre d'optimisation.