Boost Multi-Index Custom Composite Key Comparer

Question

I'm looking to write a custom comparer for a boost ordered_non_unique index with a composite key. I'm not exactly sure how to do this. Boost has a composite_key_comparer, but that won't work for me, because one of the comparers for a member of the key depends on a previous member. This is a simplified example, but I want the index to sort descending on third_ when second_ is 'A' keeping 0 values for third_ first and use std::less in all other cases. Hopefully that makes sense. I would like the code below to print out:

3,BLAH,A,0
5,BLAH,A,11
2,BLAH,A,10
4,BLAH,A,9
1,BLAH,A,8

The code would go in place of WHAT GOES HERE???. Thanks for any help.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/key_extractors.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <iostream>

namespace bmi = boost::multi_index;
namespace bt = boost::tuples;

struct Widget
{
  Widget (const std::string& id, const std::string& f, char s, unsigned int t)
  : id_(id)
  , first_(f)
  , second_(s)
  , third_(t)
  { }

  ~Widget () { }

  std::string id_;
  std::string first_;
  char second_;
  unsigned int third_;
};

std::ostream& operator<< (std::ostream& os, const Widget& w)
{
  os << w.id_ << "," << w.first_ << "," << w.second_ << "," << w.third_;
  return os;
}

struct id_index { };
struct other_index { };

typedef bmi::composite_key<
  Widget*,
  bmi::member<Widget, std::string, &Widget::first_>,
  bmi::member<Widget, char, &Widget::second_>,
  bmi::member<Widget, unsigned int, &Widget::third_>
> other_key;

typedef bmi::multi_index_container<
  Widget*,
  bmi::indexed_by<
    bmi::ordered_unique<
      bmi::tag<id_index>,
      bmi::member<Widget, std::string, &Widget::id_>
    >,
    bmi::ordered_non_unique<
      bmi::tag<other_index>,
      other_key,
      ***************WHAT GOES HERE???***************
    >
  >
> widget_set;

typedef widget_set::index<other_index>::type widgets_by_other;
typedef widgets_by_other::iterator other_index_itr;

int main ()
{
  widget_set widgets;
  widgets_by_other& wbo_index = widgets.get<other_index>();
  Widget* w;

  w = new Widget("1", "BLAH", 'A', 8);
  widgets.insert(w);
  w = new Widget("2", "BLAH", 'A', 10);
  widgets.insert(w);
  w = new Widget("3", "BLAH", 'A', 0);
  widgets.insert(w);
  w = new Widget("4", "BLAH", 'A', 9);
  widgets.insert(w);
  w = new Widget("5", "BLAH", 'A', 11);
  widgets.insert(w);

  std::pair<other_index_itr,other_index_itr> range =
    wbo_index.equal_range(boost::make_tuple("BLAH", 'A'));

  while (range.first != range.second)
  {
    std::cout << *(*range.first) << std::endl;
    ++range.first;
  }

  return 0;
}

Answer 1

Hi, I think you have hit the wall.

You may want to refer here: Ordered Indices

As with the STL, you will actually have to provide the comparison criteria yourself, and thus you will have the ability to tailor it to your needs.

As explained on the page I linked (in 'Comparison Predicates' section):

The last part of the specification of an ordered index is the associated comparison predicate, which must order the keys in a less-than fashion.

Thus, your work is two-fold:

1. You need to define a suitable comparison predicate, which operates on your types
2. You need to indicate to Boost.MultiIndex that you wish to use this predicate for the actual comparison of the keys

Here is an example, I am not sure I understood your requirements fully though so you may have to check it indeed sort as you wish.

struct WidgetComparer
{
  bool operator()(const Widget& lhs, const Widget& rhs) const
  {
    if (lhs._second == 'A' && rhs._second == 'A')
    {
      return lhs._third == 0 || rhs._third < lhs._third;
    }
    else
    {
      return lhs._third < rhs._third;
    }
  } // operator()
};

And then, you just have to complete your index. So replace "other key" with identity < Widget > and "WHAT GOES HERE" with WidgetComparer.

And here you goes!

The important point is that you should not focus on the 'key' part of the container. The key is nothing by itself, it is the couple (key,comparison predicate) which does the actual ordering. The focus is on keys in the documentation to enhance code reuse (and in particular, to benefit from the comparison predicates that are already implemented like std::less).

As an alternative, you could have decided to code a "operator<" for your Widget class or to specialize the std::less algorithm. If you intend to use this way of sorting more than once, you should probably prefer this solution. However if your container is the only one which will use it, then a custom predicate is better.

Hope that helped.