Re: [boost] Associative container using a vector

Subject: Re: [boost] Associative container using a vector
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2013-03-31 13:22:58

Stefan Strasser wrote:
> Hi everyone,
>
>
> I often find myself using a specific data structure and I'm wondering
> whether:
>   - it has a wellknown name
>   - there is a generic equivalent in a boost library
>   - or there is interest to add one.
>
> The basic idea is that you have a bunch of values stored in one object
> of type A:
>
> struct A{
>      vector<Value> values;
> };
>
> and then you have multiple objects of type B that each have to associate
> data with each value stored in A. you could use:
>
> struct B{
>      map<Value,Data> data;
> };
>
> but since A::values already provides a contiguous index for the values
> you can just as well store the data in B in a vector with matching
> indexes, and make sure that the indexes used in A::values don't change:
>
> 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;
> };
>
> keep in mind that there is one object A for many objects B. you can now
> access the associated data of many objects B by looking up the index
> once in object A, and by wasting some space in B::data for unused entries:
>
> b.data[a.index[value]]
>
> If Data is a pointer or any other type that knows an empty() state, you
> can also get rid of optional<> and generalize it as two template like:
>
> 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?

http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html