Associative container using a vector
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?
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<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?
Is this multi-index? http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html
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; }; Am 31.03.2013 19:22, schrieb Michael Marcin: template<class Value> class index;
template<class Mapped,class OptionalTraits=boost_optional_traits> class vector_map;
Is there anything like that?
Is this multi-index?
I don't think so. At least I can't find it. You could implement my "struct A" above using Boost.MultiIndex as it uses a vector and a map, but I can't find a map implementation that uses a vector with empty values for almost-contiguous keys. keep in mind the one-to-many relationship between A and B. I'd like to be able to do ONE map lookup to receive a key with which you can access many associated data values in B objects.
Le 31/03/13 19:48, Stefan Strasser a écrit :
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; }; Am 31.03.2013 19:22, schrieb Michael Marcin: template<class Value> class index;
template<class Mapped,class OptionalTraits=boost_optional_traits> class vector_map;
Is there anything like that?
Is this multi-index?
I don't think so. At least I can't find it. You could implement my "struct A" above using Boost.MultiIndex as it uses a vector and a map, but I can't find a map implementation that uses a vector with empty values for almost-contiguous keys. keep in mind the one-to-many relationship between A and B. I'd like to be able to do ONE map lookup to receive a key with which you can access many associated data values in B objects.
Hi, The architecture of Boost.MultiIndex don't need shuch a double indirection. Is as if you had the A and the Bs in a single Node. IIRC, I believe the a and the bs instances must be created at once when inserting on the multiindex. Your approach is to map values of type A to a continuous index and then use this index to access other vectors of Bs. This could work on some cases, but ensuring that the index associated to a specific 'a' doesn't change is not easy to preserve if the lookup for the index must be fast. The main difference of both approaches is that Boost.Multiindex insert all (A and the Bs at once), while your design allows to insert A and the Bs independently. An alternative to consider could be to create a multiindex with A and pointers to Bs. Best, Vicente
Am 01.04.2013 03:43, schrieb Vicente J. Botet Escriba:
The architecture of Boost.MultiIndex don't need shuch a double indirection. Is as if you had the A and the Bs in a single Node. IIRC, I believe the a and the bs instances must be created at once when inserting on the multiindex.
Thanks for the explanation, Vicente. I can't use that approach for various reasons. Here's my implementation of a "contiguous map" if anyone else is interested: http://pastebin.com/dKzRfkMm it works like a std::map, except that the key_type is always std::size_t, and after a map.insert(make_pair(100,v)), even though map.size() is 1, the internal vector has a size of 101. so the keys must be fairly contiguous to not waste space, but not completely.
participants (3)
-
Michael Marcin -
Stefan Strasser -
Vicente J. Botet Escriba