Re: [boost] [Review][bimap]

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2007-02-24 10:21:07

----- Mensaje original -----
De: Thorsten Ottosen <thorsten.ottosen_at_[hidden]>
Fecha: Sábado, Febrero 24, 2007 3:38 pm
Asunto: Re: [boost] [Review][bimap]
Para: boost_at_[hidden]

[...]
> >>>>3. consider adding
> >>>>
> >>>>     insert( const key&, const key2& )
> >>>>
> >>>>  for performance and ease-of-use reasons.
> >>>
> >>>
> >>>It may be a good idea but to insert the the relation I have to use
> >>>Boost.MultiIndex functions, so the performance will be the same.
> >>
> >>Well, not if Boost.MultiIndex adds this function too :-)
> > 
> > 
> > That will not be possible, because Boost.MultiIndex works with 
> general> structures not with two values. :(
> 
> I would like to hear Joaquin's  take on this. I have trouble 
> understanding why you can't delay construction/assignment of a 
> pair until it is actually needed.

Hello Thorsten,

As Matías says, the more generic nature of Boost.MultiIndex
makes it difficult (though probably not impossible) to implement
a delayed construction insertion facility. Let me explain
the situation: Boost.MultiIndex indices can be classified into
key-based (ordered, hashed) and non key-based (sequenced,
random access). Among the former, there are unique flavors
that don't allow duplicate keys to be entered into the
container. Key-based indices have an associated key extractor
which can be roughly though of as a functor taking an element
and returning its key information. In the case of a bimap
consisting of two key-based indices, you have

  key1(v)==v.left;
  key2(v)==v.right;

where v is of the relation type associated to the bimap.
Now consider how we'd have to implement a delayed construction
insert facility for B.MI that could particularize well for the
bimap case. A first approach to this problem could be to
provide an insert member function like this:

  insert(const key1_type& k1,...,const keym_type& km);

where k1,...,km stand for the keys of the m key-based indices
of a multi-index container. Leaving aside practical
difficulties of how to metaprogram this, there is a
fundamental problem: you don't have any guarantee that the
actual element value can be constructed from these keys
alone; in fact, in general this is not the case (unlike
in the case of bimap).

A more suitable approach would be the following:

  template<typename ConstructionInfo>
  insert(
    const key1_type& k1,...,const keym_type& km,
    const ConstructionInfo& info);

where info is such that the expression value_type v(info)
is well defined. The idea is that info can be used to
construct the element once it is determined by using
the provided keys that the insertion is not banned and
the insertion points have been calculated. In
the particular case of bimap,

  insert(const key1& k1,const key2& k2);

would be translated roughly to the following call to
B.MI API:

  insert(k1,k2,std::make_pair(cref(k1),cref(k2));

where there are provisions to convert the pair of
references to an actual relation type. Even so,
this mechanism implies unwanted temporaries, if
you analyze it carefully.

So, the problem is far (IMHO) from simple and involves
other important and as of yet not completely settled
issues like move constructors and extended allocators
(see http://www.open-
std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html,
problem #5). It is something I would love to address, but
currently I can't think of a satisfactory way to do it.
Suggestions are most welcome :)

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo