多态性在C堆类++

Question

比方说，我有一个Rectangle类，像这样：

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

现在我想两个可能不同的Rectangles列表存储为堆，但第一个堆，应根据width第二个是height。另外，我希望使用stl的make_heap函数来heapify。理想情况下，我应该可以在堆上调用.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的<functional>头中找到，也可作为std::tr1::bind在<tr1/functional>使用TR1。如果你不能使用TR1或C++ 11，那么它就有一个Boost library。

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

Answer 2

你传递一个成员函数。成员函数有一个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拉姆达：

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。

Answer 3

除了绑定，另一种解决方案是简单地要求一个指向函数的指针传递给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 

尽管...它可能有点矫枉过正;）