[boost] Associative container using a vector

Subject: [boost] Associative container using a vector
From: Stefan Strasser (strasser_at_[hidden])
Date: 2013-03-31 13:24:35

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?