[multi-index] question for a complex query
Hello *, I currently need to implement the following use case and was wondering if this is possible with multi-index: I have a class, for simplicity all members are public wihtout accessors and mutators: class entry { public: field x; field y; filed z; }; I need a multi-index index to remember the order in which the elements were inserted and non uniquely index the inserted elements by hash of field x; Now a client could do the following queries: - get all entries in the order they were inserted (this is easy and I know how to do it) - get all entries which satisfy field x parameter in the order they were inserted. I know that I can retrieve the values dependent on hash(x), but these are probably not sorted. I know that I can project iterators, but can I project (range_retireved_via_hashed_X) to (range_retrieved_for_sequence_of_X) May be I miss smth here or should split my data in some other way to satisfy this condition. With Kind Regards, Ovanes Markarian
Hi Ovanes, Ovanes Markarian <om_boost <at> keywallet.com> writes:
Hello *,I currently need to implement the following use case and was wondering if this is possible with multi-index: I have a class, for simplicity all members are public wihtout accessors and mutators:
class entry{ public: field x; field y; field z; };
I need a multi-index index to remember the order in which the elements were inserted and non uniquely index the inserted elements by hash of field x; Now a client could do the following queries:- get all entries in the order they were inserted (this is easy and I know how to do it)- get all entries which satisfy field x parameter in the order they were inserted. I know that I can retrieve the values dependent on hash(x), but these are probably not sorted. I know that I can project iterators, but can I project (range_retireved_via_hashed_X) to (range_retrieved_for_sequence_of_X)May be I miss smth here or should split my data in some other way to satisfy this condition.
As I see it, you've got two options here to get the elements with equal x sorted by inclusion order: 1. Use an ordered index instead of (or additionally to) the hashed index: elements with equal key are guaranteedly inserted in insertion order. 2. Retrieve the range from the hashed index and sort it externally according to the insertion order: here random_access indices (http://tinyurl.com/2dvmul )come handy, as you can compare random access iterators for order precedence. So, instead of a sequenced index you'd have something like: typedef multi_index_container< entry, indexed_by< hashed_non_unique<member<entry,field,&entry::x> >, random_access<> >
multi_t;
and the range retrieval function could look like this: void range_as_inserted(const multi_t& m,field x) { typedef multi_t::nth_index_iterator<1>::type ra_iterator; typedef std::vector<ra_iterator> buffer; buffer buf; std::pair<multi_t::iterator,multi_t::iterator> p=m.equal_range(x); while(p.first!=p.second)buf.push_back(m.project<1>(p.first++)); std::sort(buf.begin(),buf.end()); for(buffer::iterator it=buf.begin(),it_end=buf.end(); it!=it_end;++it){ std::cout<<**it<<"\n"; } } The idea is: store the hash range as a vector of random access iterators to the elements and then just std::sort it, using the fact that a random_access iterator it0 is less than it1 (in our particular case) if it points to an older element (with respecto to insertion time). I can't attach files from Gmane, so please find the pasted code of a complete snippet showing technique #2 Hope this helps, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo -----------------BEGIN CODE----------------- #include <boost/multi_index_container.hpp> #include <boost/multi_index/random_access_index.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/member.hpp> #include <boost/ref.hpp> #include <algorithm> #include <iostream> #include <vector> using namespace boost::multi_index; typedef int field; struct entry { entry(int x,int y):x(x),y(y){} field x,y; }; std::ostream& operator<<(std::ostream& out,const entry& e) { return out<<e.x<<","<<e.y; } typedef multi_index_container< entry, indexed_by< hashed_non_unique<member<entry,field,&entry::x> >, random_access<>
multi_t;
void range_as_inserted(const multi_t& m,field x) { typedef multi_t::nth_index_iterator<1>::type ra_iterator; typedef std::vector<ra_iterator> buffer; buffer buf; std::pair<multi_t::iterator,multi_t::iterator> p=m.equal_range(x); while(p.first!=p.second)buf.push_back(m.project<1>(p.first++)); std::sort(buf.begin(),buf.end()); for(buffer::iterator it=buf.begin(),it_end=buf.end();it!=it_end;++it){ std::cout<<**it<<"\n"; } } int main() { multi_t m; for(int i=0;i<60;++i)m.insert(entry(0,i)); range_as_inserted(m,0); } -----------------END CODE-----------------
Joaquin, many thanks for your detailed answer. I decided to handle this problem in a bit different manner. To split the entry class in 2, where the first one with field x contains all to x related tuple items as an indexed collection. That works fine and I can use boost::transform_iterator and boost::filter_iterator to efficiently access the content of the entry without copying the iterators into the vector. Many thanks again, Ovanes On Tue, Mar 4, 2008 at 11:06 PM, Joaquin M Lopez Munoz <joaquin@tid.es> wrote:
Hi Ovanes,
Ovanes Markarian <om_boost <at> keywallet.com> writes:
[...]
class entry{ public: field x; field y; field z; };
participants (2)
-
Joaquin M Lopez Munoz
-
Ovanes Markarian