Boost logo

Boost :

From: Dave Harris (brangdon_at_[hidden])
Date: 2005-03-15 11:20:14


In-Reply-To: <d1409a$kc1$1_at_[hidden]>
daniel_at_[hidden] (Daniel James) wrote (abridged):
> Think about how such a class would be stored in the proposed unordered
> associative containers. If you use unordered_set<base*> then the hash
> function will be called for the pointer, not the class.

I imagine you would use a hasher which dereferenced the pointer.

    template<typename T>
    struct hash_ptr {
        size_t operator()(const T *p) const {
            return hash_value( *p );
        }
    };

And perhaps this should be included in boost too? Eg this:

   unordered_set< shared_ptr<MyType>, hash_ptr<MyType> >

looks reasonable to me.

> If Thorsten writes ptr_unordered_set<base> then there might be a
> problem with boost::hash<base>. Although it will equally apply to
> std::equal_to<base>.

Absolutely. In general when writing hash_value() you need to look at the
corresponding equality operator. For example:

    bool Derived::operator==( const Base &base ) const {
        if (Base::operator==( base ))
            if (const Derived *p = dynamic_cast( const Derived * >(&base))
                if (m_value == p->m_value)
                    return true;
        return false;
    }

Ideally we look at this and we decide there ought to be something in the
hash_value which corresponds to the dynamic_cast. But what?

We can try using hash_value( typeid(*this) ). However, that will be
relatively slow and may not give good results, depending on how it is
implemented. We could use our own type IDs, but allocating them is tricky.

So it is tempting not to bother, and instead use:

    size_t Derived::hash_value() const {
        // return combine_hash( Base::hash_value(), m_value );
        size_t hash = Base::hash_value();
        combine_hash( hash, m_value );
        return hash;
    }

which is correct, but will produce more collisions than if we'd used the
typeid. If hash_value( m_value ) yielded different results for different
types of value, then the number of collisions would be reduced.

The stability requirement compromises the quality of hashing.

-- Dave Harris, Nottingham, UK


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk