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?
