Boost logo

Boost :

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
  - 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:[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?

Boost list run by bdawes at, gregod at, cpdaniel at, john at