Полиморфизм для классов кучи в C ++ - PullRequest
Новая
       14

Полиморфизм для классов кучи в C ++

2 голосов
/ 15 января 2012

Допустим, у меня есть класс 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 ++, поэтому мне нужна ваша помощь.

Ответы [ 3 ]

3 голосов
/ 15 января 2012

Поскольку comp является указателем на функцию-член, его нельзя вызвать без передачи this.Вам необходимо привязать this к нему: 

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

std::bind можно найти в заголовке <functional> в C ++ 11, а также доступно как std::tr1::bind в <tr1/functional> с использованием TR1,Если вы не можете использовать TR1 или C ++ 11, для этого есть библиотека Boost .

Демо: http://ideone.com/5zhmg

2 голосов
/ 16 января 2012

Помимо связывания, другое решение состоит в том, чтобы просто запросить указатель на функцию для передачи конструктору 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

Хотя ... это, вероятно, немного излишне;)

1 голос
/ 15 января 2012

Вы передаете функцию-член.Функции-члены имеют указатель 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

The 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 .

...