STL堆由比较器参数化

Question

我想编写一个围绕STL堆的包装器类，允许用户提供自己的比较器。我希望比较器是函子，这样它们就可以在某些状态上闭合。

例如，考虑维护一个2D点的排序列表。排序标准是到给定点的距离。我想提供一个默认的比较器，它根据与原点的距离进行排序，但也为用户提供了基于与任意点的距离进行比较的选项。

我的问题是:我不知道如何正确地构造函数继承，以使它以灵活的方式工作。下面是排序点的例子来说明我想要的:

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,%dn", 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,%dn", 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

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

Answer 1

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

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

代替在SortedPoints中持有Comparator对象的引用，您可以创建一个与Comparator函数签名匹配的std::function对象并将其传递到push_heap(或boost::函数，如果您停留在c++ 03)。

对于您的代码，您可以尝试这样做:

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

Answer 2

我找到了一种使用常规OOP范例来做我想做的事情的方法。使用@pzed建议的c++ 11功能特性是一个好主意，但是我的代码库的其余部分不是c++ 11，我想坚持使用一致的范例。

策略是使基类Comparator靠近子类实例，并简单地将比较传递给子类。

例如，上面的三个类变成:

class Comparator {
public:
  Comparator(Comparator &c) : _comparator(c) {}
  virtual bool operator()(const Point& lhs, const Point& rhs) {
    return _comparator(lhs, rhs);
  }
private:
  Comparator& _comparator;
};
// Sorts Points according to distance from the origin.
class DefaultComparator : public Comparator {
public:
  DefaultComparator() : Comparator(*this) {}
  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) : Comparator(*this), _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;
};

其余代码保持不变，例如我们现在可以这样做:

RelativeComparator relativeComp(Point(100,100));
SortedPoints list1 = SortedPoints(relativeComp);

和之前一样，它可以工作。

Answer 3

我做了3个改变，让这个工作:

1. 删除多态性，支持模板
2. 将比较器添加到pop_heap调用中。
3. 为操作符()添加const

我得到这个:

// Sorts Points according to distance from the origin.
class DefaultComparator {
public:
    virtual bool operator()(const Point& lhs, const Point& rhs) const {
        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:
    RelativeComparator(Point p) : _point(p) {}
    virtual bool operator()(const Point& lhs, const Point& rhs) const {
        const float dl = Point::dist(_point, lhs), dr = Point::dist(_point, rhs);
        return dl < dr;
    }
private:
    const Point _point;
};
template <class C>
class SortedPoints
{
public:
    SortedPoints(C &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.front();
            _points.pop_back();
            return true;
        }
    }
private:
    typedef std::vector<Point> PointList;
    C &_comp;
    PointList _points;
};
int main()
{
    DefaultComparator defaultComp;
    RelativeComparator relativeComp(Point(100, 100));
    SortedPoints<DefaultComparator> list1 = SortedPoints<DefaultComparator>(defaultComp);
    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,%dn", p.x, p.y);
    }
    SortedPoints<RelativeComparator> list2 = SortedPoints<RelativeComparator>(relativeComp);
    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,%dn", p.x, p.y);
    }
    return 0;
}