Объединение equal_range с bind2nd и binary_function

Question

У меня есть отсортированная коллекция

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

vector<Thing> Things;

с использованием

class MultiValuedComparator
{
public:
   item a;
   item b;

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

Поскольку у меня есть дубликаты элемента a и элемента b (но не других данных), я хочу получить диапазон из тех структур данных, которые соответствуют элементу a и элементу b. Коллекция отсортирована только по пунктам.

Я думал, что equal_range будет подходящим методом для этого. Поскольку мне нужно было сопоставить более одного элемента, я унаследовал от двоичной_функции.

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

Я не знаю, как написать функцию equal_range, чтобы она это делала. Я попробовал:

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)
      );
}

но этот код жалуется на несоответствие 'operator <' в '__middle .__ gnu_cxx :: __ normal_iterator .. и т.д. при вызове equal_range </p>

Как мне написать это так, чтобы equal_range работал? Я понятия не имею, где разместить перегруженный оператор. RangeByA, похоже, не принимает его.

Answer 1

Требование компаратора для equal_range - строгий слабый порядок (не равенство). Кроме того, компаратор должен вызываться с аргументами в обоих порядках:

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

Таким образом, результатом equal_range является диапазон итераторов, в котором оба этих вызова возвращают false.

Таким образом, простая настройка заключается в добавлении конструктора к вашему MultiValuedComparator, который принимает Thing, что позволяет преобразовать объект Thing в объект MultiValuedComparator для сравнения:

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

А затем настройте компаратор так, чтобы он использовал только MultiValuedComparator и использовал строгий слабый порядок:

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)));
   }
};

Альтернативой вышеупомянутому, которая позволит избежать копирования (из Thing в MultiValuedComparator), является простая реализация operator() в обоих направлениях (Thing против MultiValuedComparator и MultiValuedComparator против Thing), отбрасывая наследование std::binary_function ( здесь не нужен):

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)
   }
};