Specializing boost::unordered_set to handle 'unordered' pairs

[Gladdok]

I needed a hash-container to take advantage of constant-time searches so I came to unordered_set. Unfortunately the std::unordered_set requires c++11 enabled which more than quadruples my compile times (gcc), and I would have to write a hash function for std::pair.

Fortunately boost::unordered_set does not require c++11 and it is already able to hash std::pair.

My question now is, I want to search for pairs in no particular order, ie std::pair(5,3) should be considered equal to std::pair(3,5).

Must I define both 1) a hash function that hashes to the same value for both cases? and 2) an equality function that returns true for both cases?

Foregoing this solution, I could just insert both pairs and do 2 searches instead.

[JLBorges]

> Must I define both 1) a hash function that hashes to the same value for both cases?
> and 2) an equality function that returns true for both cases?

Yes.


> Foregoing this solution, I could just insert both pairs and do 2 searches instead.

Not a good idea; that would violate the semantics of a set.


Something like this:

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

template < typename T > std::pair<T,T> ascending( const std::pair<T,T>& p )
{ return std::make_pair( std::min(p.first,p.second), std::max(p.first,p.second) ) ; }


template < typename T > struct cmp_equal_pair
{
    bool operator() ( const std::pair<T,T>& a, const std::pair<T,T>& b ) const
    { return ascending(a) == ascending(b) ; }
};

template < typename T > struct hash_pair
{
    std::size_t operator() ( const std::pair<T,T>& p ) const
    { return boost::hash_value( ascending(p) ) ; }
};

int main()
{
    boost::unordered_set< std::pair<int,int>, hash_pair<int>, cmp_equal_pair<int> > set ;
    set.insert( std::make_pair(5,3) ) ;
    assert( set.find( std::make_pair(3,5) ) != set.end() ) ;
    assert( set.find( std::make_pair(3,5) )->first == 5 ) ;
}