[boost] Re: 4 more associative containers.

From: Rich Sposato (rds_at_[hidden])
Date: 2004-02-03 17:26:53

On Mon, Feb 02, 2004 at 11:50:45PM -0800, Rich Sposato wrote:
> > The containers are called flex_set, flex_map, flex_multiset, and 
> > flex_multimap. They are similar to the 4 STL associative containers. 
> > There are two important differences between the STL containers and these:
> > 1. You can search on any type that is comparable to the key_type, rather 
> > than just the key_type. (The STL associative containers only allows 
> > searches on the same type as the key.)
> > 2. You do *not* need to create a temporary object of key_type to search 
> > through the containers. (The STL containers require you to create one 
> > temporary object to search for another.)

> A good idea.  I recall wishing for something like this a while ago; I
> don't remember if it stemmed from an actual problem in practice or just
> general unhappiness with the std:: interface in theory.

> (It might be even more swell if comparators could know about
> 'equivalence' as well, so you could test for equivalence using one
> user-defined function, rather than two calls like !c(x,y)&&!c(y,x).)

This seems like a good suggestion since it would provide a slight
efficiency since the comparison will only be done once rather than
twice. When I looked through flex_set implementation, I found only two places where equivalence is tested.  Both of those are inside insert member functions.  So, there is a benefit to adding an equivalence function to the comparison functor. Since there is no reason to templatize the insert functions, the equivalence function will not need to be overloaded as the function operators are.

Using the Employee example to define an equivalence function, I guess
it will look like this:

struct CompareEmployees : std::binary_function<
  const Employee *, const Employee *, bool >
{
  // rest of functor as shown in the introductory message.
  inline bool equivalent( const Employee * l, const Employee * r ) const
  { return ( l->GetName() == r->GetName() ); }
};

Would anybody prefer a different function name beside equivalent?

> Do you have have documentation of the new 'concepts'?  Specifically it
> seems like flex_xxxx<T> uses a new ComparableTo<T,U> concept to place
> requirements on both the Comparator and the template arguments to
> methods like find().

The only any documentation on it so far is what is on my website, and what I wrote for the journal, Overload.   Most of my website's description of flex_set is already mentioned in the introductory post to this mail list.

The ComparableTo< T, U > concept is enforced by the compiler and the comparator.  In theory, the templated member functions can
work with any type. But in practice, the compiler can only use one
of the overloaded function operators in the comparator with a
specific call to one of the templated member functions of flex_set. To designate that a specific type is comparable to the flex_set's key_type, just add another overloaded operator to the comparator.

Say, if I wanted to compare an Employee object to a Customer object, I would just add two more functions like this:

struct CompareEmployees : std::binary_function<
  const Employee *, const Employee *, bool >
{
  // rest of functor as shown in the introductory message.
  inline bool operator () ( const Employee * l, const Customer * r ) const
  { return ( l->GetName() < r->GetName() ); }
  inline bool operator () ( const Customer * l, const Employee * r ) const
  { return ( l->GetName() < r->GetName() ); }
};

Rich Sposato