[boost] std::tr1::unordered* and functional/hash

From: Dave Handley (dave.handley_at_[hidden])
Date: 2006-09-29 11:17:00

My first question here is a simple one - are there any plans for an
implementation of unordered_set etc. from TR1 to be included in boost.
Since the vast majority of the std::tr1 libraries are from boost, except
for this one, it seems an obvious gap to try and fill.

 

My second thought concerns the interface in std::tr1 for unordered_set -
specifically for the find, count and equal_range functions.  In the
std::tr1 documents that I have read, the interface is very vanilla:

 

// lookup

iterator find(const key_type& k);

const_iterator find(const key_type& k) const;

size_type count(const key_type& k) const;

std::pair<iterator, iterator> equal_range(const key_type& k);

std::pair<const_iterator, const_iterator> equal_range(const key_type& k)
const;

 

However, the interface we use on our internal version of this is
slightly different - based primarily on the interface for
boost.multi_index:

 

template <typename CompatibleKey>

iterator find(const CompatibleKey &k);

template <typename CompatibleKey, typename CompatibleHash, typename
CompatiblePred>

iterator find(const CompatibleKey &k, const CompatibleHash &hash, const
CompatiblePred &pred);

etc.

 

This is useful for performance reasons in many cases.  For example, in
the case of an unordered_set<std::string>  we can then provide a hash
function and comparator that work with both std::string and const char
*.  This can then either be provided through the type of the container,
or simply through the second version of the find function.

 

For example:

struct StringHasher

{

size_t operator()(const char *str_) const;

size_t operator()(const std::string &str_) const;

};

struct StringComparator

{

bool operator()(const char *lhs_, const std::string &rhs_) const;

            bool operator()(const std::string &lhs_, const char *rhs_)
const;

            bool operator()(const std::string &lhs_, const std::string
&rhs_) const;

};

 

typedef std::tr1::unordered_set<std::string, StringHasher,
StringComparator> Set1;

typedef std::tr1::unordered_set<std::string> Set2;

 

Set1 set1;

set1.find("abc");   // This will not create a std::string temporary in
the find function.

 

Set2 set2;

set2.find("abc", StringHasher(), StringComparator());  // This will also
not create a temporary

set2.find("abc");  // This will create a temporary

 

My final thought is that it would be useful if the boost.functional/hash
provided functionality as standard similar to the
StringHasher/StringComparator above.  I use this sort of code a lot when
I'm working with hash containers and boost.multi_index and it seems
wasteful to have to rewrite it regularly - especially when it is so
simple to do.

 

Any thoughts on these points?

 

Dave Handley