________________________________________ De: boost-users-bounces@lists.boost.org [boost-users-bounces@lists.boost.org] En nombre de Dominique Devienne [ddevienne@gmail.com] Enviado el: viernes, 10 de julio de 2009 20:29 Para: boost-users Asunto: [Boost-users] [Multi-Index] New "hierarchical" indexing?
In another use case, entries have a "scenario" key, where scenario is hierarchical, and I want all entries in BMI A from a given scenario and all its ancestors, with the scenarios being in BMI B (i.e. "cross-bmi"). Of course I can do a "full scan" but I'm looking for something hopefully faster/smarter.
Not entirely sure if the following is directly applicable to your problem, but anyway. If one of the keys of an index has a hierarchical nature, one can do child-of queries by taking advantage of compatible sorting criteria. Let me introduce an example. Suppose we have entries having an associated scenario which we simply model by a path showing the hierarchical relations among them: typedef std::vector<std::string> path_t; typedef flyweight<path_t> scenario_t; struct entry { entry(const scenario_t& scenario):scenario(scenario){} scenario_t scenario; // payload }; Note that we're compressing scenarios with Boost.Flyweight. This lets us dispose of an auxiliary container to hold the scenarios, which is what you're likely doing now. Our container of entries indexed by scenario is typedef multi_index_container< entry, indexed_by< ordered_non_unique<member<entry,scenario_t,&entry::scenario> > >
entry_container_t;
Now we define: struct parent_t:scenario_t { parent_t(const scenario_t& s):scenario_t(s){} }; struct children { bool operator()(const parent_t& p,const scenario_t& s)const { return std::lexicographical_compare( p.get().begin(),p.get().end(), s.get().begin(),s.get().begin()+std::min(p.get().size(),s.get().size())); } bool operator()(const scenario_t& s,const parent_t& p)const { return std::lexicographical_compare( s.get().begin(),s.get().begin()+std::min(p.get().size(),s.get().size()), p.get().begin(),p.get().end()); } }; What is this? parent_t is just a sort of alias to scenario_t that allows us to differentiate between a "terminal" scenario and a scenario used for purposes of recursive lookup. children is a compatible (with the order of entry_container_t) compare predicate that levels off scenario paths in a way that, for instance, if we have parent "a" then "a/b", "a/d", "a/b/e" etc. are deemed equivalent to the parent. This allows us to locate and count children: // count children entries of scenario s c.count(parent_t(s),children()) Please find attached a complete example shwoing the technique. Is this of any help to your particular problem? Thanks for using Boost.MultiIndex. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo