Re: [Boost-users] [Multi-Index] Get container view of a non-unique-index equal_range?

Subject: Re: [Boost-users] [Multi-Index] Get container view of a non-unique-index equal_range?
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-06-11 18:58:49

AMDG

Dominique Devienne wrote:
> On Thu, Jun 11, 2009 at 3:12 PM, Steven Watanabe<watanabesj_at_[hidden]> wrote:
>   
>> Dominique Devienne wrote:
>>     
>>>  <snip>
>>> I'd like to be able to have a "view" of VehicleIndex, for example
>>>       
>> Because of the way multi_index implements hashed_non_unique,
>> there is no sequence of equal elements.
>>     
>
> What if I switch to using an ordered rather than hashed non-unique index?
> Would that change your answer?
>   

No.

>> If you try to store a pair of iterators,
>> they may be invalidated or cease to delimit the equal_range.
>>     
>
> Aren't B.MI iterators pretty resilient in the face of changes to the
> container?
>   

Yes.  But no matter how resilient an iterator is, it cannot survive when
the element that it points to is deleted.

>> <snip>
>>     
>
> That's two equal_range lookups everytime to iterate the range. I was
> hoping that B.MI had some kind of "logical" begin-range, end-range
> iterators that adjusted themselves automatically upon inserts and
> updates in fact. Am I in luck and using an ordered_non_unique index
> give me that? Maybe in 1.40 ;-) --DD
>   

No.  I don't think that multi_index can support this easily.

Suppose that we have a multi set containing {1, 2, 5, 7, 9}.
and we want a view of all the elements equal to 4L.  (Note the
different type, since multi_index allows any compatible key.  We
can't rely converting to the value type)

What range do we return?  It has to be empty, and it has to
be such that inserting 4 in the set will make the range non-empty.
The iterators begin equal, so we cannot return a pair of iterators.
Therefore, either equal elements need to be stored in some kind of
container or we need to be able to record a single position which is
never invalidated which is close to the desired range.  For
hashed_indexes, my guess is that the most optimization that you
can do is to cache the hash, and compute the begin and end iterators
separately instead of using equal_range to compute both in begin and in
end.  Having a separate linked list for each set of equal elements doesn't
really work either.  Take a look at the example I gave above again.
We have to insert an empty container for the value 4L, which any elements
equal to 4 will be inserted in.  I'm using 4L as an example, but the key
can really be an arbitrary type, so there is no way to store it except by
using type erasure.  And it only gets worse...

Suppose that now someone else wants an equal range of elements using
4LL as a key.  By this point the type information of 4L has been lost.
As far as multi_index is concerned, they are completely unrelated types.
There is absolutely no way to determine that we should use the same 
container
for both.

Okay, so suppose that we try to avoid these problems by only allowing
the exact key type for an equal_range_view.  multi_index supports
noncopyable keys.  If we do something like std::map<key_type, 
std::list<Value> >,
the key must be copyable, regardless of whether we create subranges or not.

And I'll stop here as I've already spent way to much time thinking about 
this.

In Christ,
Steven Watanabe