Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk