[boost] 4 more associative containers.

From: Rich Sposato (rds_at_[hidden])
Date: 2004-02-03 02:50:45

  Hi Everyone,

This is my debut post on Boost, and I would like to introduce some 
container classes I made so they can be considered for inclusion into 
Boost.  (I made a similar post on STLport, but members of STLport 
suggested that Boost would be a better forum because STLport only has 
standard containers.)

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

The flex_set and related containers do not have these limitations because:
a) several of the member functions are template member functions,
b) and that allows the comparison functor used with the containers to be 
overloaded for each type that can be used for searching.

Listing 1 shows the two limitations of std::set and the other 
associative containers. For this example, assume you have an Employee 
class, and you store them in a set which is ordered by employee name.

Listing 1:
class Employee
{
public:
    const std::string & GetName() const;
    // . . . other functions
};

struct CompareEmployees : std::binary_function<
const Employee *, const Employee *, bool >
{
    // Can only do a comparison of one Employee record
    // to another Employee record. Can't compare to any
    // other type.
    inline bool operator () ( const Employee * l, const Employee * r ) const
    { return ( l->GetName() < r->GetName() ); }
};

typedef std::set< Employee *, CompareEmployees > EmployeeSet;
EmployeeSet employees;

Employee * FindEmployee( const std::string & name )
{
    // This bogus object is just a temporary to find the real
    // object. All I want is to find an Employee record that
    // matches the given name, rather make such a record.
    Employee bogus( name );
    EmployeeSet::iterator it( employees.find( &bogus ) );
    return ( employees.end() == it ) ? 0 : *it;
}

Listing 2 shows all the member functions which are now templated. The 
non-templated versions of these functions inside std::set use the 
key_type. The Compare_Type template parameter in the flex_set functions 
is *not* one of the template parameters for the class itself.

Listing 2:
template < class Key, class Compare, class Alloc >
class flex_set
{
    // . . . other parts of flex_set class
public:

    template< class Compare_Type >
    size_type erase( const Compare_Type & x );

    template< class CompareType >
    size_type count( const CompareType & x ) const;

    template< class Compare_Type >
    iterator find( const Compare_Type & x );

    template< class Compare_Type >
    const_iterator find( const Compare_Type & x ) const;

    template< class Compare_Type >
    iterator lower_bound ( const Compare_Type & x );

    template< class Compare_Type >
    const_iterator lower_bound( const Compare_Type & x ) const;

    template< class Compare_Type >
    iterator upper_bound( const Compare_Type & x );

    template< class Compare_Type >
    const_iterator upper_bound( const Compare_Type & x ) const;

    template< class Compare_Type >
    pair< iterator, iterator > equal_range( const Compare_Type & x );

    template< class Compare_Type >
    pair< const_iterator, const_iterator > equal_range(
    const Compare_Type & x ) const;

};

Other than accepting a reference to a const Compare_Type in some 
functions, the flex_set class is identical to the std::set.  Even the 
basic implementation is the same.

Like the std::set class, flex_set uses the comparison functor as a 
little policy class to determine how the elements are sorted. Although 
the std::set has no need for an overloaded functor, the flex_set's real 
flexibility comes into play when using overloaded functors. I can design 
into my functor the mechanism by which an Employee record can be 
compared to a std::string or to a C-style string. Listing 3 shows the 
overloaded comparison functor.

Listing 3:
struct CompareEmployees : std::binary_function<
const Employee *, const Employee *, bool >
{
    inline bool operator () ( const Employee * l, const Employee * r ) const
    { return ( l->GetName() < r->GetName() ); }

    inline bool operator () ( const Employee * l, const std::string & r 
) const
    { return ( l->GetName() < r ); }

    inline bool operator () ( const std::string & l, const Employee * r 
) const
    { return ( l < r->GetName() ); }

    inline bool operator () ( const Employee * l, const char * r ) const
    { return ( l->GetName() < r ); }

    inline bool operator () ( const char * l, const Employee * r ) const
    { return ( l < r->GetName() ); }
};

The example shown in Listing 1 now becomes the function shown in Listing 4.

Listing 4:
typedef flex_set< Employee *, CompareEmployees > EmployeeSet;
EmployeeSet employees;

Employee * FindEmployee( const std::string & name )
{
    // No unnecessary temporary objects here!
    // And the code shows my intent of searching by name.
    EmployeeSet::iterator it( employees.find( name ) );
    return ( employees.end() == it ) ? 0 : *it;
}

I just published an article describing these containers in issue #58 of 
Overload magazine http://www.accu.org/c++sig/public/Overload.html. The 
article explains various design decisions about the classes, and goes 
into more detail about the containers.

You can also find a zip file of my implementation at 
http://www.richsposato.com/FlexSet.html along with a zip file containing 
a demo project. The implementation was made as a drop-in replacement for 
the associative containers that come with the GCC compiler. I made the 
demo project using MinGW.

Because my implementation was designed for GCC's version of the STL, the 
classes don't compile cleanly with some other implementations of the 
STL. For that reason, they will be reimplemented for Boost, if they are 
accepted.

Thanks for your consideration,

Rich Sposato