Re: [boost] Associative container using a vector

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

Is this multi-index? http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html