C++ 中堆类的多态性；

Question

假设我有一个像这样的 Rectangle 类：

class Rectangle {
public:
    double width;
    double height;
}

现在我希望将两个可能不同的 Rectangles 列表存储为堆，但第一个堆应该基于 宽度，第二个高度。另外，我希望使用stl的make_heap函数来堆化。理想情况下，我应该能够在堆上调用 .heapify() ，并且根据它所属的类，相关堆应该通过将正确的比较函数传递给 来堆化自身make_heap，也许使用动态调度。我所拥有的是以下内容：

class Heap {
public:
    vector<Rectangle> data;
    virtual bool comp(Rectangle a, Rectangle b);
    void heapify() { make_heap(data.begin(), data.end(), comp); }
    // other methods that make use of comp directly
}

class WidthHeap : public Heap {
    bool comp(Rectangle a, Rectangle b); // compares by width
}

class HeightHeap : public Heap {
    bool comp(Rectangle a, Rectangle b); // compares by height
}

这都是错误的，因为我想我只是不理解 C++ 中的函数，这就是为什么我需要你的帮助。

Answer 1

因为comp是一个成员函数指针，所以如果不传递this就不能调用它。您需要将 this 绑定到它：

std::make_heap(data.begin(), data.end(), std::bind(&Heap::comp, this, _1, _2));

std::bind 可以在 C++11 的 标头中找到，并且也可以使用 TR1 在 中作为 std::tr1::bind 使用。如果您无法使用 TR1 或 C++11，可以使用 Boost 库。

演示：http://ideone.com/5zhmg

Answer 2

除了绑定之外，另一种解决方案是简单地要求将函数指针传递给Heap 的构造函数。

// C++03
typedef bool (*CompType)(Rectangle const&, Rectangle const&);

// C++11 (to allow for lambdas and predicates)
typedef std::function<bool(Rectangle const&, Rectangle const&)> CompType;

然后：

class Heap {
public:
  explicit Heap(CompType cmp): cmp(cmp) {}

  void heapify() {
    std::make_heap(data.begin(), data.end(), cmp);
  }

private:
  CompType cmp;
  std::vector<Rectangle> data;
}; // class Heap

有趣的是，您甚至可以更进一步，只需一点想象力，实际上可以同时保留两个订单。

class Heap {
public:
  Heap():
    byLength([](Rectangle const& l, Rectangle const& r) {
      return l.length < r.length; }),
    byWidth[](Rectangle const& l, Rectangle const& r) {
      return l.width < r.width; }),
  {}

  void heapify() {
    std::make_heap(data.begin(), data.end(), byLength);
    std::make_heap(ref.begin(), ref.end(),
      [](Rectangle const* l, Rectangle const* r) {
        return byWidth(*l, *r);
      });
  }

private:
  CompType byLength;
  CompType byWidth;
  std::vector<Rectangle> data;
  std::vector<Rectangle*> ref;
}; // class Heap

虽然……这可能有点过分了;)

Answer 3

您正在传递一个成员函数。成员函数有一个 this 指针。 make_heap 函数应该从哪里获取它？

具体来说，使用以下语法调用指向成员函数的指针（对于发明的类 X）：

X* obj_ptr; // initialize somewhere
typedef void (X::*mem_ptr)();
mem_ptr mem_fun = &X::some_invented_function;
(obj_ptr->*mem_fun)(); // extra parens needed

obj_ptr 就是 make_heap 函数丢失的。您需要以某种方式提供它，最简单的方法可能是通过 C++11 中的 lambda：

std::make_heap(data.begin(), data.end(),
    [this](Rectangle r1, Rectangle r2){
      return comp(r1,r2);
    });

或者甚至可能是 std::bind：

#include <functional>

using std::placeholders;
std::make_heap(data.begin(), data.end(), std::bind(&X::comp, this, _1, _2));

如果您无权访问这些 C++11功能，请使用 Boost.Bind。