
Boost : 
From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 20070224 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 easeofuse 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
keybased (ordered, hashed) and non keybased (sequenced,
random access). Among the former, there are unique flavors
that don't allow duplicate keys to be entered into the
container. Keybased 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 keybased 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 keybased indices
of a multiindex 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk