[boost] Re: 4 more associative containers

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

Stefan Slapeta wrote:
 > Rich Sposato wrote:
>  > 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.)

 >  BTW, there is also an extention in STLPort which supports 
comparisons like > this.

When I asked about this at STLport, they said they don't have extensions 
to the STL.  Maybe I did not ask the right question.

 > I often wondered why this isn't supported by the standard containers.
 > Any idea?

I must caution that flex_set has a minor disadvantage, a problem which 
std::set does not have.  For primitive types, flex_set will cause 
code-bloat, while std::set will not.  I don't use flex_set with 
primitive types because the compiler will make 2 functions out of this 
code for flex_set< long >, while it only makes one function using 
std::set< long >.

typedef std::set< long > bunchOfLongs;
long a = 1;
short b = 2;
bunchOfLongs.erase( a );
bunchOfLongs.erase( b );

The compiler will see
flex_set< long >::erase( const long & );
as different from
flex_set< long >::erase( const short & );

But, a compiler will see both of those calls above as:
std:set< long >::erase( const long & );

For that reason, I can't advocate changing std::set's functions to be 
templated the way flex_set functions are.  I suppose if it had templated 
functions like flex_set, there would be no need for flex_set, and 
somebody would some day advocate using a less-templated class called 
no_bloat_set.  :-)

I actually consider the bloat issue as minor because most of the 
functions are inline and small.  Also, I rarely do a search using more 
than one type anyway.  My typical usage with flex_set and related 
classes is to insert using the key_type, and find, count, and erase 
using a different type.

Sometimes, the amount of code actually decreases inspite of a little 
bloat because I don't have to construct a temporary anymore.

I think that could answer why the associative containers like map do not 
have templated functions.  As to the other container types, I don't 
think they will need templated search functions.  If you use the 
sequential containers, you can use the stand-alone find, count, 
binary_search, etc... functions and pass in a predicate.

Rich