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

 


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