Re: [boost] [Review][bimap]

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2007-02-24 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 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

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 data-structure 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