将 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 匹配的一系列数据结构。该集合仅按项目 a 排序。

我认为 equal_range 是执行此操作的合适方法。由于我需要匹配多个从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;
   }
}

我不知道如何编写 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 时，

我该如何编写这个以便 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），即简单地在两个方向（Thing 与 MultiValuedComparator 以及 MultiValuedComparator 与 Thing）实现 operator()，从而放弃继承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)
   }
};