c++ - 由比较器参数化的 STL 堆

Question

我想围绕 STL 堆编写一个包装类，允许用户提供他们自己的比较器。我想让比较器成为仿函数，以便它们可以在某些状态下关闭。

例如，考虑维护一个排序的二维点列表。排序标准是距给定点的距离。我想提供一个默认比较器，它根据与原点的距离进行排序，但也让用户可以选择根据与任意点的距离进行比较。

我的问题是:我不知道如何正确构造仿函数继承以使其以灵活的方式工作。这是用于说明我想要什么的排序点示例:

struct Point {
  int x, y;
  Point(int xx, int yy) : x(xx), y(yy) {}
  static float dist(const Point &a, const Point &b) {
    const int dx = a.x - b.x, dy = a.y - b.y;
    return sqrtf(dx*dx + dy*dy);
  }
};

// Abstract Point comparison base class.
class Comparator {
public:
  virtual bool operator()(const Point& lhs, const Point& rhs) = 0;
};

// Sorts Points according to distance from the origin.
class DefaultComparator : public Comparator {
public:
  virtual bool operator()(const Point& lhs, const Point& rhs) {
    const Point zero(0,0);
    const float dl = Point::dist(zero, lhs), dr = Point::dist(zero, rhs);
    return dl < dr;
  }
};

// Sorts Points according to distance from a given Point.
class RelativeComparator : public Comparator {
public:
  RelativeComparator(Point p) : _point(p) {}
  virtual bool operator()(const Point& lhs, const Point& rhs) {
    const float dl = Point::dist(_point, lhs), dr = Point::dist(_point, rhs);
    return dl < dr;
  }
private:
  const Point _point;
};

class SortedPoints {
public:
  SortedPoints(Comparator &comp) : _comp(comp) {}

  void push(Point p) {
    _points.push_back(p);
    std::push_heap(_points.begin(), _points.end(), _comp);
  }

  bool pop(Point &p) {
    if (_points.empty()) {
      return false;
    } else {
      std::pop_heap(_points.begin(), _points.end(), _comp);
      p = _points.back();
      _points.pop_back();
      return true;
    }
  }

private:
  typedef std::vector<Point> PointList;
  Comparator &_comp;
  PointList _points;
};

int main() {
  DefaultComparator defaultComp;
  RelativeComparator relativeComp(Point(100,100));
  SortedPoints list1 = SortedPoints(defaultComp);
  SortedPoints list2 = SortedPoints(relativeComp);
  Point p(0,0);
  list1.push(Point(15,15));
  list1.push(Point(13,13));
  list1.push(Point(5,5));
  printf("List one (relative to 0,0):\n");
  while (list1.pop(p)) {
    printf("%d,%d\n", p.x, p.y);
  }

  list2.push(Point(15,15));
  list2.push(Point(13,13));
  list2.push(Point(5,5));
  printf("List two (relative to 100,100):\n");
  while (list2.pop(p)) {
    printf("%d,%d\n", p.x, p.y);
  }
  return 0;
}

由于继承的结构方式，当 STL 堆实现试图实例化一个 Comparator(因为它是一个抽象类)时，我遇到了一个编译错误。准确的错误是:

sortedpoints.cpp: In member function ‘void SortedPoints::push(Point)’:
sortedpoints.cpp:51: error: cannot allocate an object of abstract type ‘Comparator’
sortedpoints.cpp:17: note:   because the following virtual functions are pure within ‘Comparator’:
sortedpoints.cpp:19: note:  virtual bool Comparator::operator()(const Point&, const Point&)
/usr/include/c++/4.2.1/bits/stl_heap.h: In function ‘void std::push_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point*, std::vector<Point, std::allocator<Point> > >, _Compare = Comparator]’:
sortedpoints.cpp:51:   instantiated from here
/usr/include/c++/4.2.1/bits/stl_heap.h:203: error: cannot allocate an object of abstract type ‘Comparator’
sortedpoints.cpp:17: note:   since type ‘Comparator’ has pure virtual functions
/usr/include/c++/4.2.1/bits/stl_heap.h: In function ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point*, std::vector<Point, std::allocator<Point> > >, _Distance = long int, _Tp = Point]’:
/usr/include/c++/4.2.1/bits/stl_heap.h:238:   instantiated from ‘void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Tp) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point*, std::vector<Point, std::allocator<Point> > >, _Tp = Point]’
/usr/include/c++/4.2.1/bits/stl_heap.h:265:   instantiated from ‘void std::pop_heap(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point*, std::vector<Point, std::allocator<Point> > >]’
sortedpoints.cpp:58:   instantiated from here

完成这类任务的正确方法是什么？如果我的比较器继承策略不好，我也想知道:这只是我尝试的第一种方法。

Answer 1

如果您查看 push_heap 的文档，您会看到它按值获取比较器，因此它将尝试复制您的 Comparator目的。

template <class RandomAccessIterator, class Compare>
void push_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

而不是持有对 Comparator 的引用SortedPoints 中的对象, 你可以创建一个 std::function与 Comparator 匹配的对象函数签名并将其传递给 push_heap(如果你坚持使用 C++03，则传递给 boost::function)。

对于你的代码，你可以尝试这样的事情:

class SortedPoints
{
public:
  typedef std::function<bool (const Point& lhs, const Point& rhs)> MyComparator;  // <-- Add this typedef
  SortedPoints(MyComparator comp) : _comp(comp) {}  // <-- Use MyComparator instead of Comparator&

  void push(Point p) {
    _points.push_back(p);
    std::push_heap(_points.begin(), _points.end(), _comp);
  }

  bool pop(Point &p) {
    if (_points.empty()) {
      return false;
    } else {
      std::pop_heap(_points.begin(), _points.end());
      p = _points.front();
      _points.pop_back();
      return true;
    }
  }

private:
  typedef std::vector<Point> PointList;
  MyComparator _comp;  // <-- Use MyComparator instead of Comparator&
  PointList _points;
};