C ++ Двойная отправка для равных () - PullRequest
8 голосов
/ 13 сентября 2011

Представьте, что у меня есть абстрактный базовый класс Shape, с производными классами Circle и Rectangle.

class Shape {};
class Circle : public Shape {};
class Rectangle : public Shape {};

Мне нужно определить, равны ли две фигуры, предполагаяУ меня есть два Shape* указателя.(Это потому, что у меня есть два экземпляра vector<Shape*>, и я хочу посмотреть, имеют ли они одинаковые формы.)

Рекомендованный способ сделать это - двойная отправка .Я придумал вот что (здесь очень упрощено, так что формы равны всем другим фигурам того же типа):

class Shape {
public:
    virtual bool equals(Shape* other_shape) = 0;
protected:
    virtual bool is_equal(Circle& circle) { return false; };
    virtual bool is_equal(Rectangle& rect) { return false; };
    friend class Circle;    // so Rectangle::equals can access Circle::is_equal
    friend class Rectangle; // and vice versa
};

class Circle : public Shape {
public:
    virtual bool equals(Shape* other_shape) { return other_shape->is_equal(*this); };
protected:
    virtual bool is_equal(Circle& circle) { return true; };
};

class Rectangle : public Shape {
public:
    virtual bool equals(Shape* other_shape) { return other_shape->is_equal(*this); };
protected:
    virtual bool is_equal(Rectangle& circle) { return true; };
};

Это работает, но я должен добавить отдельный equals функция и friend объявление в Shape для каждого производного класса.Затем я должен скопировать и вставить точно такую ​​же equals функцию в каждый производный класс.Это ужасно много шаблонов, скажем, 10 различных форм!

Есть ли более простой способ сделать это?

dynamic_cast не может быть и речи;слишком медленно.(Да, я тестировал ее. Скорость имеет значение в моем приложении.)

Я пробовал это, но это не работает:

class Shape {
public:
    virtual bool equals(Shape* other_shape) = 0;
private:
    virtual bool is_equal(Shape& circle) { return false; };
};

class Circle : public Shape {
public:
    virtual bool equals(Shape* other_shape) { return other_shape->is_equal(*this); };
private:
    virtual bool is_equal(Circle& circle) { return true; };
};

class Rectangle : public Shape {
public:
    virtual bool equals(Shape* other_shape) { return other_shape->is_equal(*this); };
private:
    virtual bool is_equal(Rectangle& circle) { return true; };
};

equals() всегда возвращает false, даже на идентичных фигурах,Кажется, диспетчер всегда выбирает базовую функцию is_equal(Shape&), даже когда доступно «более конкретное» соответствие.Это, вероятно, имеет смысл, но я недостаточно хорошо понимаю диспетчеризацию C ++, чтобы понять, почему.

Ответы [ 6 ]

5 голосов
/ 13 сентября 2011

Двойная отправка хорошо изучена. Обобщение двойной диспетчеризации называется «мульти-методом».

Глава 11 Современный дизайн C ++ подробно рассматривает эту проблему. Подход с использованием dynamic_cast<>, который вы описали, находится в разделе 11.3 «Тип двойного включения: перебор». Автор даже описывает, как автоматизировать большую часть работы и автоматически генерировать симметричные перегрузки. Затем автор вводит логарифмическую диспетчеризацию на основе std::map<> и std::type_info. Наконец, раздел заканчивается «Мультиметодами с постоянным временем: необработанная скорость», которые (приблизительно) основаны на матрице функций обратного вызова.

Представленное решение включает в себя подробные пояснения по обработке функторов и приведений, чтобы избежать неприятных ошибок при множественном (и виртуальном) наследовании.

Если вы подумываете о реализации мульти-методов в C ++, я настоятельно рекомендую вам прочитать книгу и реализовать предложенное решение.

5 голосов
/ 13 сентября 2011

Когда вы создаете методы, подобные этому:

virtual bool is_equal(Shape& circle) { return false; };

А в подклассе

virtual bool is_equal(Circle& circle) { return true; };

Это не один и тот же метод. У вас есть два отдельных виртуальных метода, ни один из которых не переопределен (они перегружены , даже не перегружены, как отметил Бен Фойгт). Когда вы вызываете Shape::is_equal, существует только одна версия: Shape::is_equal(Shape&) ..., которая не переопределяется и всегда возвращает false.

Вы должны будете определить отдельные перегруженные методы в родительском классе, а затем переопределить их в дочернем классе. Например,

class Shape {
    // Choice between these two methods happens at compile time...
    virtual bool is_equal(Circle& circle) { return false; };
    virtual bool is_equal(Rectangle& circle) { return false; };
};

class Rectangle : Shape {
    // Choice between this and Shape::is_equal(Rectangle&) happens at runtime...
    virtual bool is_equal(Rectangle& circle) { return true; };
};

Однако, используя такие приемы, вы, вероятно, не приблизитесь к производительности или простоте способа, которым программист на С сделает это:

typedef enum {
    SHAPE_CIRCLE,
    SHAPE_RECTANGLE
} shape_type_t;

struct shape {
    shape_type_t type;
};

struct circle {
    shape_type_t type;
    ...
};

struct rectangle {
    shape_type_t type;
    ...
};

bool shape_equal(struct shape *x, struct shape *y)
{
    if (x->type != y->type)
        return false;
    switch (x->type) {
    case SHAPE_CIRCLE:
        return circle_equal((struct circle *) x, (struct circle *) y);
    case SHAPE_RECTANGLE:
        ...;
    }
}

Если перегрузка и виртуальные методы усложняют ваш код по сравнению с версией C, вы можете переосмыслить, решаете ли вы эту конкретную проблему с помощью перегрузки и виртуальных методов.

1 голос
/ 13 сентября 2011

Вы можете использовать перечисление типов и статическое приведение, если dynamic_cast слишком медленный ...

enum ShapeType
{
    SHAPE_TYPE_CIRCLE,
    SHAPE_TYPE_RECTANGLE
};

struct Shape
{
    virtual ShapeType GetShapeType() const = 0;
    virtual bool isEqual(const Shape& other) const = 0;
};

struct Circle : Shape
{
    virtual ShapeType GetShapeType() const { return SHAPE_TYPE_CIRCLE; }

    virtual bool isEqual(const Shape& other) const
    {
        if (other.GetShapeType() == SHAPE_TYPE_CIRCLE)
        {
            const Circle *circle = static_cast<const Circle*>(&other);

            // do some circle specific comparison
            return true;
        }
        return false;
    }
};
0 голосов
/ 13 сентября 2011

В моих проектах я перемещаю метод Shape::operator== в приватный, а не реализую его. Объем работы, чтобы правильно решить эту проблему, не стоит усилий.

Другими словами, заданный вектор Shape *:

std::vector<Shape *> my_shapes;

Я могу сделать следующее:

my_shapes.push_back(new Rectangle);
my_shapes.push_back(new Circle);

Проблема возникает при сравнении объектов:

Shape * p_shape_1 = my_shapes[0];
Shape * p_shape_2 = my_shapes[1];
if (*p_shape_1 == *p_shape_2) {...}

Выражение эквивалентно:

p_shape_1-> оператор == (* p_shape_2);

Если выполняется виртуальная или полиморфная операция, она становится такой:

Прямоугольник :: оператор == ( (* круг * тысяча двадцать-одна)); * +1022 * Другими словами, велика вероятность того, что Прямоугольник будет сравнивать себя с Кругом или другой Формой; неверное сравнение.

Итак, в моих проектах я запрещаю сравнения на равенство на основе указателей базового класса. Единственный материал, который можно сравнить с помощью указателей на базовые классы, - это контент в базовом классе.

0 голосов
/ 13 сентября 2011

Виртуальные функции могут легко заменить dynamic_cast Проверка типа RTTI, например: http://ideone.com/l7Jr5

struct Shape
{
    struct subtype { enum { Shape, Circle, Rectangle, ColoredCircle }; };

    virtual bool is_a( int type ) const { return type == subtype::Shape; }
    virtual bool is_equal(const Shape& s) const { return false; }
};

struct Rectangle : Shape
{
    virtual bool is_a( int type ) const { return type == subtype::Rectangle || Shape::is_a(type); }
    virtual bool is_equal(const Shape& s) const
    {
        if (!s.is_a(subtype::Rectangle)) return false;
        const Rectangle& r = static_cast<const Rectangle&>(s);
        return true; // or check width and height
    }
};

struct Circle : Shape
{
    virtual bool is_a( int type ) const { return type == subtype::Circle || Shape::is_a(type); }
    virtual bool is_equal(const Shape& s) const
    {
        if (!s.is_a(subtype::Circle)) return false;
        const Circle& c = static_cast<const Circle&>(s);
        return true; // or check radius
    }
};

struct ColoredCircle : Circle
{
    virtual bool is_a( int type ) const { return type == subtype::ColoredCircle || Circle::is_a(type); }
};

int main(void)
{
    Rectangle x;
    Shape y;
    return x.is_equal(y);
}

-

Почему существует 10 копий "точно такой же" функции? Разве Rectangle::is_equal(const Rectangle&) const не должен сравнивать специфичные для Rectangle члены?

Если все прямоугольники попадают в один класс эквивалентности, как в случае с кодом, который вы показали, тогда вы можете просто иметь одну виртуальную функцию, которая возвращает класс эквивалентности.

0 голосов
/ 13 сентября 2011

Я обычно ссылаюсь на dynamic_cast и виртуальные функции. Если компилятор не слишком глуп, динамическое приведение на один шаг не так уж отличается от выполнения двух переходов в виртуальной таблице.

class shape
{
protected:
   virtual bool is_equal(const shape* s) const=0;
   friend bool oeprator==(const shape& a, cost shape& b)
   { return a.is_equal(&b); }
};

class circle: public shape
{
    double radius;
    point<duouble> center;
protected:
    virtual bool is_equal(const shape* s) const
    {
        const circle* p = dynamic_cast<const circle*>(s);
        return p && p->radius==radius && p->center==center;
    }
};

То же самое для прямоугольника или любой другой формы. в основном, двойная диспетчеризация требует - если N - классы, N 2 функции. Таким образом, вам просто нужно N функций (по одной на класс).

Если вы чувствуете, что динамическое приведение слишком медленное, вы можете использовать enum, объявленный в базовом классе, и правильно инициализируется производными классами. Но для этого необходимо обновлять значения перечисления каждый раз, когда будет добавлен новый класс. Например: форма класса { защищенный: enum shape_type {no_shape, circle_shape, rectangle_shape}; shape_type my_type; виртуальный bool is_equal (const shape * s) const = 0; operator друга bool == (постоянная форма & a, форма стоимости & b) {return a.is_equal (& b); } shape (): my_type (no_shape) {} };

class circle: public shape
{
    double radius;
    point<duouble> center;
protected:
    virtual bool is_equal(const shape* s) const
    {
        const circle* p = static_cast<const circle*>(s);
        return my_type == s->my_type && p->radius==radius && p->center==center;
    }
public:
    circle() { my_type = circle_shape; }
};

В случае, если использование перечисления base_defined недопустимо (неизвестно количество возможных классов), вы можете полагаться на простое значение (например, целое число), которое может однозначно представлять тип с помощью трюка, подобного:

int int_generator()
{ static int x=0; return ++x; }

template<class T>
int  id_for_type()
{ static int z = int_generator(); return z; }

class shape
{
...
int my_type;
};


class circle
{
...
   circle() { my_type = id_for_type<circle>(); }
};
...