Re: [Boost-users] [multi-index] question for a complex query

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2008-03-04 17:06:31

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-----------------