Re: STL and finding objects by name

Matthew Bucknall wrote:


This is a situation that occurs very frequently: having an object in
an associative container, where the object itself provides the key.

For the sake of explanation below, let's assume Whole = Key + Extra.

std::set<Whole> is bad because it doesn't allow you to look up by Key
alone, and you have to construct a Whole object when all you want is
just to look up by Key, as described in the problem. You may not even
be able to construct a Whole object just from Key, without Extra.

std::map<Key, Extra> is bad because Extra doesn't have access to Key.
Boost.Bimap, a variation on this, is a good library and I'm glad to see
it, but it adds extra complication and it's not often what you want,
either; having a map where you can look up Key by Extra is one thing,
and having Key right inside an object is another. Many operations of
Extra, including even construction, may require Key at hand. Providing
an ordering between Extra objects may be another difficulty/impossibility.

std::map<Key, Whole> solves most of the problems and is easy to use,
but duplicates Key and results in a wasted space (and time).

This situation shows a deficiency in the 'set or map' classification
of the associative containers currently in the standard library.
std::set<V> requires key_type (V) to be the same as value_type (V),
whereas std::map<K, M> requires key_type (K) to be separate from
mapped_type (M), but there's no container that allows something in
between. I think a new container that allows arbitrary mapping from
value_type to key_type, via parametrization, would be helpful:

     template <class V, class K, class ToKey,
               class Comp = std::less<K>,
               class Alloc = std::allocator<V> >
     class associative
     // Stores nodes of V. Uses ToKey(...)(V) to get K.
     {
     public:
         typedef V value_type;
         typedef K key_type;
     // ...
     };

     // the current standard library associative container equivalences:

     struct identity
     {
         template <class T>
         const T& operator()(const T& t) const { return t; }
     };

     struct get_first
     {
         template <class T1, class T2>
         const T1& operator()(const std::pair<T1, T2>& p) const
         { return p.first; }
     };

     template <class V>
     using set = associative<V, V, identity>;

     template <class K, M>
     using map = associative<std::pair<const K, M>, K, get_first>;

Then the OP's problem can be solved by the following:

     struct get_name
     {
         const std::string& operator()(const Thing& t) const
         { return t.get_name(); }
     };

     typedef associative<Thing, std::string, get_name> map;

What do you think?

--
Seungbeom Kim

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]