Combining equal_range with bind2nd and binary_function

Question

I have a sorted collection of

class Thing
{
public:
   item a;
   item b;
   other data;
};

vector<Thing> Things;

using

class MultiValuedComparator
{
public:
   item a;
   item b;

   MultiValuedComparator(item c, item d)
   {
      a = c;
      b = d;
   }
};

Since I have duplicates of item a, and item b (but not other data), I want to grab a range of those data structures that match item a AND item b. The collection is sorted by item a only.

I thought equal_range would be an appropriate method to do this. Since I needed to match more than one item I inherited from binary_function.

struct RangeByA : public std::binary_function<Thing, MultiValuedComparator>
{
   bool operator()(const Thing &left, const MultiValuedComparator &right)
   {
      return left.a == right.a && left.b == right.b;
   }
}

I don't know how to write the equal_range function so it does this. I tried:

void somefunction()
{
   typedef pair<vector<Thing>::iterator, 
                vector<Thing>::iterator> startEndIterPair;

   MultiValuedComparator mvc(1, 2);

   startEndIterPair p = equal_range
      (
      Things.start(), 
      Things.end(), 
      std::bind2nd(RangeByA, mvc)
      );
}

but this code complains of no match for 'operator<' in '_middle._gnu_cxx::__normal_iterator .. etc at the call to equal_range

How do I write this so equal_range will work? I have no idea where to place the overloaded operator. RangeByA does not seem to accept it.

Answer 1

The requirement of a comparator for equal_range is a strict weak ordering (not equality). In addition, the comparator must be able to be called with the arguments in both orders:

comparator(*iter, value); // items less than lower bound
comparator(value, *iter); // items greater than upper bound

The result of equal_range, then, is the range of iterators where both of these calls return false.

A simple adjustment, then, is to add a constructor to your MultiValuedComparator that accepts a Thing, allowing a Thing object to be converted to a MultiValuedComparator object for comparison:

class MultiValuedComparator
{
public:
   item a;
   item b;

   MultiValuedComparator(item c, item d)
   {
      a = c;
      b = d;
   }

   MultiValuedComparator(const Thing &thing)
   {
      a = thing.a
      b = thing.b
   }
};

And then adjust your comparator to only use MultiValuedComparator and to use a strict weak ordering:

struct RangeByA : public std::binary_function<MultiValuedComparator, MultiValuedComparator>
{
   bool operator()(const MultiValuedComparator &left, const MultiValuedComparator &right)
   {
      // Sorted by a first, then b if necessary
      return (left.a < right.a)
              || (!(right.a < left.a) && (left.b < right.b)));
   }
};

An alternative to the above, which will avoid copies (from Thing to MultiValuedComparator), is to simply implement operator() in both directions (Thing vs. MultiValuedComparator and MultiValuedComparator vs. Thing), dropping the inheritance of std::binary_function (not needed here):

struct RangeByA
{
   bool operator()(const Thing &left, const MultiValuedComparator &right) {
      // ... (same body as above)
   }

   bool operator()(const MultiValuedComparator &left, const Thing &right) {
      // ... (same body as above)
   }
};