Improving on std::map

In an article I wrote for the December 2003 edition of Overload magazine, I proposed a more flexible version of the standard library's map template, called map3. This page provides a sample implementation which is intended to demonstrate how the proposed interface works.

The template is called map3 because it has three parameters instead of the four that std::map uses. It implements very similar functionality but does not require that the stored value type be an instance of std::pair. The template parameters are as follows:

template <
  typename Traits,
  typename Compare
        = std::less <typename Traits::key_type>,
  typename Allocator
        = std::allocator <typename Traits::value_type>
> class map3;

As you can see, the template requires a traits class, which provides the necessary information about the values stored in the map. The traits class should provide the following interface:

struct traits {
  typedef some type  key_type;
  typedef some type  mapped_type;
  typedef some type  value_type;

  static key_type const &get_key    (value_type const &);
  static mapped_type &   get_mapped (value_type &);
  static value_type      construct  (key_type const &);
};

The construct static member function is necessary in order to emulate the semantics of std::map::operator[], which will insert a value for a given key if none currently exists. Actually, due to the extreme simplicity of the demonstration implementation, this function is also used in the find member function. In a better implementation, find would not require this. Hopefully the other member functions and member types are self-explanatory.

The sample implementation, provided in the tarball map3.tar.gz, is licensed for free use as described in the contained header file comments. It includes some very simple demonstration programs, one of which requires the reference counted pointer template from the boost libraries.

Please send any comments, queries or suggestions to RaoulGough@yahoo.co.uk, preferably including the word map3 in the subject line so I know the mail is not SPAM.

The contents of this page and the code available for download from it are Copyright (c) 2003 by Raoul Gough.