CODEWITHSUNDEEP
c++boostboost-multi-index
Kirill Golikov
Kirill Golikov

Reputation: 1374

boost::multi_index_container: How to use composite_key (x,y) to support rectangular search?

typedef boost::multi_index_container
< Record,
  indexed_by 
  < ordered_non_unique 
    < tag<ByP>,
      composite_key < Record,
                      const_mem_fun<Record, double, &Record::hit_x>,
                      const_mem_fun<Record, double, &Record::hit_y>
    >
  >,   // ...
>

As you can see, there is index by Point(x,y) (ByP). Now I'm using the next function:

size_t  adjacencyRectPoints (std::list<Record> &range, const Point  &min, const Point &max)
{
  MultiIndexMoves::index<ByP>::type  &index = store_.get<ByP> ();     
  /* Range searching, i.e.the lookup of all elements in a given interval */
  auto itFirstLower = index.lower_bound (boost::tuple<double, double> (min));
  auto itFirstUpper = index.upper_bound (boost::tuple<double, double> (max));

  size_t count = 0U;
  for ( auto it = itFirstLower; it != itFirstUpper; ++it )
  {
    if ( (min.x <= it->hit.x && min.y <= it->hit.y)
      && (max.x >= it->hit.x && max.y >= it->hit.y) )
    {
      range.push_back (*it);
      ++count;
    }
  }
  return count;
}

This function returns all points from rectangle: (min.x < x < max.x && min.y < y < max.y). It is working.

But, how you can see, the container returns much more points, that I expected, and I have to filter them one more time. I think, that acting is wrong.

I thought, that I had to define the comparator by myself to get only right points. But that way of comparing is not fit for boost::multi_index_container:

struct Compare
{
  bool  operator() (const Point &p, const Point &q) const
  { return  (p.x < q.x) && (p.y < q.y); }
};

(first comment @RichardHodges)

Upvotes: 0

Views: 300

Answers (1)

sehe
sehe

Reputation: 393934

Firstly, the comparator seems wrong to me (it doesn't look like it does define a total weak ordering as required).

Secondly, the key type on a composite key is logically a tuple of the constituent parts. The default comparison implementation is provided by boost (as a a lexicographical memberwise comparison¹).

This is much more likely to be what you want. If you must override it some way, use: http://www.boost.org/doc/libs/1_60_0/libs/multi_index/doc/reference/key_extraction.html#composite_key_compare

¹ <boost/tuple/tuple_comparison.hpp> and c++11's std::tuple also defines the same operators

Upvotes: 0

Related Questions