Associative container using a vector

31 Mar 2013

      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 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;
     vectorstd::size_t freelist;
     map 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 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 vector_map;

Is there anything like that?

Stefan Strasser

Michael Marcin

Stefan Strasser

Vicente J. Botet Escriba

Stefan Strasser

tags

participants (3)