Boost logo

Boost :

Subject: [boost] [intrusive] advanced lookup/insertion suggestion
From: Rei Thiessen (rei.thiessen_at_[hidden])
Date: 2012-02-14 18:27:43


Something that has bothered me with the advanced lookup and insertion
functions is that I have to specify the hash/equality functors at every
invocation site:

c.find(key,key_hash(),key_equality());
c.insert_check(key,key_hash(),key_equality(),cd);

If we don't consistently use the same (key_hash,key_equality) pair for a
given (element_type,key_type) pair,
the container invariant will likely be broken.
Thus, I think it's very un-"C++ like" to have to specify these two types
at every invocation site.

Assuming that we don't want to embed (key_type,key_hash,key_equality)
directly into the type of a container,
the library could use a type operator to automatically deduce the
appropriate hash/equality functions given an element/key type pair at the
find/insert member function instantiation point:

// library
template<typename ElementType, typename KeyType>
struct element_key_info
{};

// different name to avoid overload confusion.
// instantiation succeeds only when
// element_key_info is properly specialized
template<typename KeyType>
iterator unordered_set::find_key( KeyType const& k )
{...}

...

// user
namespace intrusive{
template<>
struct element_key_info<element_type,key_type>
{
        typedef key_hash hash_type;
        typedef key_equality equality_type;
};
}

element_type e(...);
c.insert( e );
key_type k(...);
... = c.find_key( k );

These new signatures do not allow non-default-constructible hash/equality
functors, but the original signatures that do are still available.
I think this makes the code simpler and safer in exchange for some
additional type declarations.
Would this be a worthwhile addition to the intrusive associative
containers?


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