Boost logo

Boost :

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)


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


template <typename CompatibleKey>

iterator find(const CompatibleKey &k);

template <typename CompatibleKey, typename CompatibleHash, typename

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



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

            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


Boost list run by bdawes at, gregod at, cpdaniel at, john at