[Multi-Index] Get container view of a non-unique-index equal_range?
Given for example class Ident : public noncopyable { .. .}; class VehicleIdent : public Ident { ... }; struct ByUid {}; struct ByType {}; struct ByNKey {}; struct VehicleIdentHash { ... }; struct VehicleIdentPred { ... }; typedef boost::multi_index_container< shared_ptr<VehicleIdent>, indexed_by< hashed_unique< // primary (surrogate) key tag<ByUid>, BOOST_MULTI_INDEX_CONST_MEM_FUN( Ident, const Uid&, uid ) >, hashed_unique< // natural key (logical primary key) tag<ByNKey>, identity< shared_ptr<VehicleIdent> >, VehicleIdentHash, VehicleIdentPred >, // additional index to iterate on a type range (e.g. all Cars) hashed_non_unique< tag<ByType>, BOOST_MULTI_INDEX_CONST_MEM_FUN( VehicleIdent, const string&, type ) > >
VehicleIndex;
typedef VehicleIndex::index<ByUid>::type VehicleByUid; typedef VehicleIndex::index<ByType>::type VehicleByType; typedef VehicleIndex::index<ByNKey>::type VehicleByNKey; I'd like to be able to have a "view" of VehicleIndex, for example compatible with unordered_set in this case since using a hashed index, for a given vehicle type ("Audi" for example), and going further have this view allow inserts which would go into the "master" vehicle index under the cover, validated by its unique indexes. In pseudo-code, something a bit like this: struct VehicleMake { VehicleByType::EqualRangeView& models_; VehicleMake(const string& name) : models_(get<ByType>(get_vehicle_index()).equal_range_view(name)) {} }; With models_ behaving has a normal container one can iterate on (begin, end), query (empty, find, count), modify (insert, erase, clear, etc...), those operations only affecting the VehicleIndex elements matching the VehicleByType given range, and possibly asserting all inserts are valid for the range (the vehicles added via the "range view" have the type matching the range's type). Can this be done? Has it been considered as a possible extension, and is it even feasible given the current B.MI design? Any input on how to achieve or emulate the above would be appreciated. Thanks, --DD PS: The above design is synthetic of course. We have a parent-child hierarchy of C++ objects where parents have lists of their children, but now there's a list of all children, from all parents, in a B.MI, indexed (non-unique) on the parent instance, and I'd like the "concrete" list maintained by each parent to become the kind of "view" I'm describing above. Right now I'm manually maintaining the sync of the existing and the new "master" list (the B.MI index), having to "sprinkle" the code to keep them in sync, but the "view" approach above would be cleaner IMHO, and avoid many potential bugs from forgetting to "sprinkle" in all the right places.
AMDG Dominique Devienne wrote:
Given for example
<snip>
I'd like to be able to have a "view" of VehicleIndex, for example compatible with unordered_set in this case since using a hashed index, for a given vehicle type ("Audi" for example), and going further have this view allow inserts which would go into the "master" vehicle index under the cover, validated by its unique indexes.
In pseudo-code, something a bit like this:
struct VehicleMake { VehicleByType::EqualRangeView& models_;
VehicleMake(const string& name) : models_(get<ByType>(get_vehicle_index()).equal_range_view(name)) {} };
With models_ behaving has a normal container one can iterate on (begin, end), query (empty, find, count), modify (insert, erase, clear, etc...), those operations only affecting the VehicleIndex elements matching the VehicleByType given range, and possibly asserting all inserts are valid for the range (the vehicles added via the "range view" have the type matching the range's type).
Can this be done? Has it been considered as a possible extension, and is it even feasible given the current B.MI design?
Any input on how to achieve or emulate the above would be appreciated. Thanks, --DD
Because of the way multi_index implements hashed_nonunique, there is no sequence of equal elements. If you try to store a pair of iterators, they may be invalidated or cease to delimit the equal_range. You could try looking up the iterators on demand, if you don't mind the extra overhead. template<class MultiIndexContainer, class Tag, class Key> struct equal_range_view { public: equal_range_view(MultiIndexContainer& c, const Key& k) : container_(c), key_(k) {} typedef ... iterator; iterator begin() const { return(container_.equal_range(key_).first); } iterator end() const { return(container_.equal_range(key_).second); } private: MultiIndexContainer& container_; Key key_; }; In Christ, Steven Watanabe
On Thu, Jun 11, 2009 at 3:12 PM, Steven Watanabe<watanabesj@gmail.com> wrote:
AMDG
Dominique Devienne wrote:
<snip> I'd like to be able to have a "view" of VehicleIndex, for example
Because of the way multi_index implements hashed_non_unique, there is no sequence of equal elements.
What if I switch to using an ordered rather than hashed non-unique index? Would that change your answer?
If you try to store a pair of iterators, they may be invalidated or cease to delimit the equal_range.
Aren't B.MI iterators pretty resilient in the face of changes to the container? I remember reading that in the doc, and was actually thinking of replacing some yummy code (below) that takes copies of a container with a B.MI, since my reading of the doc was that i, as an iterator from the B.MI, would not be invalidated by side-effects of calling detach() which end up erasing other elements (or itself) from observers_. Did I read that wrong? ObserverList copy = *observers_ ; for (ObserverList::iterator i(copy.begin()); i != copy.end(); ++i) { Observer* obs = *i; // still a valid observer? if (observers_->contains(obs)) { if (obs) { obs->detach(this) ; } else { cerr << "null observer ignored" << endl; } } }
You could try looking up the iterators on demand, if you don't mind the extra overhead.
template<class MultiIndexContainer, class Tag, class Key> struct equal_range_view { public: equal_range_view(MultiIndexContainer& c, const Key& k) : container_(c), key_(k) {} typedef ... iterator; iterator begin() const { return(container_.equal_range(key_).first); } iterator end() const { return(container_.equal_range(key_).second); } private: MultiIndexContainer& container_; Key key_; };
That's two equal_range lookups everytime to iterate the range. I was hoping that B.MI had some kind of "logical" begin-range, end-range iterators that adjusted themselves automatically upon inserts and updates in fact. Am I in luck and using an ordered_non_unique index give me that? Maybe in 1.40 ;-) --DD
In Christ, Steven Watanabe
AMDG Dominique Devienne wrote:
On Thu, Jun 11, 2009 at 3:12 PM, Steven Watanabe<watanabesj@gmail.com> wrote:
Dominique Devienne wrote:
<snip> I'd like to be able to have a "view" of VehicleIndex, for example
Because of the way multi_index implements hashed_non_unique, there is no sequence of equal elements.
What if I switch to using an ordered rather than hashed non-unique index? Would that change your answer?
No.
If you try to store a pair of iterators, they may be invalidated or cease to delimit the equal_range.
Aren't B.MI iterators pretty resilient in the face of changes to the container?
Yes. But no matter how resilient an iterator is, it cannot survive when the element that it points to is deleted.
<snip>
That's two equal_range lookups everytime to iterate the range. I was hoping that B.MI had some kind of "logical" begin-range, end-range iterators that adjusted themselves automatically upon inserts and updates in fact. Am I in luck and using an ordered_non_unique index give me that? Maybe in 1.40 ;-) --DD
No. I don't think that multi_index can support this easily. Suppose that we have a multi set containing {1, 2, 5, 7, 9}. and we want a view of all the elements equal to 4L. (Note the different type, since multi_index allows any compatible key. We can't rely converting to the value type) What range do we return? It has to be empty, and it has to be such that inserting 4 in the set will make the range non-empty. The iterators begin equal, so we cannot return a pair of iterators. Therefore, either equal elements need to be stored in some kind of container or we need to be able to record a single position which is never invalidated which is close to the desired range. For hashed_indexes, my guess is that the most optimization that you can do is to cache the hash, and compute the begin and end iterators separately instead of using equal_range to compute both in begin and in end. Having a separate linked list for each set of equal elements doesn't really work either. Take a look at the example I gave above again. We have to insert an empty container for the value 4L, which any elements equal to 4 will be inserted in. I'm using 4L as an example, but the key can really be an arbitrary type, so there is no way to store it except by using type erasure. And it only gets worse... Suppose that now someone else wants an equal range of elements using 4LL as a key. By this point the type information of 4L has been lost. As far as multi_index is concerned, they are completely unrelated types. There is absolutely no way to determine that we should use the same container for both. Okay, so suppose that we try to avoid these problems by only allowing the exact key type for an equal_range_view. multi_index supports noncopyable keys. If we do something like std::map<key_type, std::list<Value> >, the key must be copyable, regardless of whether we create subranges or not. And I'll stop here as I've already spent way to much time thinking about this. In Christ, Steven Watanabe
On Thu, Jun 11, 2009 at 5:58 PM, Steven Watanabe<watanabesj@gmail.com> wrote:
AMDG
Dominique Devienne wrote: That's two equal_range lookups everytime to iterate the range. I was hoping that B.MI had some kind of "logical" begin-range, end-range iterators that adjusted themselves automatically upon inserts and updates in fact. Am I in luck and using an ordered_non_unique index give me that? Maybe in 1.40 ;-) --DD
No. I don't think that multi_index can support this easily. <snip> And I'll stop here as I've already spent way too much time thinking about this.
Thank you for your time. Your suggestion to dynamically access the range on demand sounds like the only viable way to implement this equal_range view, thanks again. Best regards, --DD
participants (2)
-
Dominique Devienne -
Steven Watanabe