
Boost : 
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 20070224 13:48:16
JOAQUIN LOPEZ MU?Z wrote:
>  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
I guess my ignorance about the internals of Boost.MI is evident
here.
Anyway, I can't help think about it this way:
1. boost::bimap<T,U> is implemented in terms of Boost.MI
2. somewhere in this datastructure lies a bunch of T objects and U object
3. upon map.insert( bimap::relation( T(), U() ) ), the T and U object is
copied to their respective objects inside the datastructure
If that is true, I have a hard time seing how creating a temporary
relation() object can make a difference.
But, anyway, I believe you JOAQUIN.
cheers
Thorsten
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk