Re: [boost] Associative container using a vector

Subject: Re: [boost] Associative container using a vector
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2013-03-31 21:43:48

Le 31/03/13 19:48, Stefan Strasser a écrit :
> >> struct A{
> >>      vector<Value> values;
> >>      vector<std::size_t> freelist;
> >>      map<Value,std::size_t> index;
> >>
> >>      void erase(...){ push index of unused value to freelist; }
> >>      void push_back(Value){ reuse a freelist entry or 
> values.push_back; }
> >> };
> >> struct B{
> >>      vector<optional<Data> > data;
> >> };
> Am 31.03.2013 19:22, schrieb Michael Marcin:
>>> template<class Value>
>>> class index;
>>>
>>> template<class Mapped,class OptionalTraits=boost_optional_traits>
>>> class vector_map;
>>>
>>> Is there anything like that?
>>>
>>
>> Is this multi-index?
>>
>
> I don't think so. At least I can't find it.
> You could implement my "struct A" above using Boost.MultiIndex as it 
> uses a vector and a map, but I can't find a map implementation that 
> uses a vector with empty values for almost-contiguous keys.
> keep in mind the one-to-many relationship between A and B. I'd like to 
> be able to do ONE map lookup to receive a key with which you can 
> access many associated data values in B objects.
>
>
Hi,

The architecture of Boost.MultiIndex don't need shuch a double 
indirection. Is as if you had the A and the Bs in a single Node. IIRC, I 
believe the a and the bs instances must be created at once when 
inserting on the multiindex.

Your approach is to map values of type A to a continuous index and then 
use this index to access other vectors of Bs.
This could work on some cases, but ensuring that the index associated to 
a specific 'a' doesn't change is not easy to preserve if the lookup for 
the index must be fast.

The main difference of both approaches is that Boost.Multiindex insert 
all (A and the Bs at once), while your design allows to insert A and the 
Bs independently.
An alternative to consider could be to create a multiindex  with A and 
pointers to Bs.

Best,
Vicente