Flexible Associative Containers

I designed some drop-in replacements for the associative containers in the Standard Template Library for C++.  They work just like set, map, multiset, and multimap - except that you can do searches on data types other than the key type. The STL associative containers require you to create a temporary object when you search for an element within the container, and these classes eliminate the need to construct that temporary.  I called them flex_set, flex_map, flex_multiset, and flex_multimap because they allow for more flexible searches.

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

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() ); }
};

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.
  // The goal is to eliminate the need for any temporary object.
  Employee bogus( name );
  EmployeeSet::iterator it( employees.find( &bogus ) );
  return ( employees.end() == it ) ? 0 : *it;
}

By changing several member functions of std::set to be templated functions, and by overloading the comparison functor, the temporary objects can be eliminated.  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 2:
template < class Key, class Compare, class Alloc >
class flex_set
{
  // . . . other parts of flex_set class
  public:
    template< class Compare_Type >
      iterator find( const Compare_Type & x );
};

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() ); }
};

typedef flex_set< Employee *, CompareEmployees > EmployeeSet;
EmployeeSet employees;

Employee * FindEmployee( const std::string & name )
{
  // No unnecessary temporary objects here!
  EmployeeSet::iterator it( employees.find( name ) );
  return ( employees.end() == it ) ? 0 : *it;
}

An article I published in Overload describes the classes in more detail.  It also explains the reasons why various implementation decisions were made when the classes were designed.

Here are the source code files which work with the GCC implementation of the STL.
And a demo project for use with MinGW.


Home Page