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

4 Mar 2008

      Hi Ovanes,

Ovanes Markarian  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 >,
      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             buffer;

    buffer buf;
    std::pair 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 
#include 
#include 
#include 
#include 
#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< >,
    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             buffer;

  buffer buf;
  std::pair 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-----------------

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

Joaquin M Lopez Munoz