Podwójny polimorfizm i wizytatorzy
Programowanie obiektowe w klasycznej wersji opiera się na wybieraniu wirtualnych funkcji na podstawie dynamicznego typu (typu najbardziej pochodnej klasy) obiektu przy użyciu tylko wskaźnika lub referencji do interfejsu (klasy bazowej). W języku C++ takie wyszukiwanie w czasie wykonywania (zwane też wiązaniem dynamicznym) jest możliwe za każdym razem dla jednego typu. Pod tym względem język C++ przypomina języki Simula i Smalltalk, a także nowsze, takie jak Java i C#. Brak możliwości wybierania funkcji na podstawie dwóch dynamicznych typów może być poważnym ograniczeniem. Ponadto funkcja wirtualna musi być
składową. To oznacza, że aby dodać funkcję wirtualną do hierarchii klas, konieczne jest zmienienie klasy bazowej (lub klas bazowych) dostarczającej interfejs i wszystkich klas pochodnych, których ta zmiana może dotyczyć. To również może sprawiać duże problemy. W tym artykule znajduje się opis podstawowych sposobów radzenia sobie w takich sytuacjach:
- „Podwójny polimorfizm”: jak wybierać funkcje wirtualne na podstawie dwóch typów.
- „Wizytatorzy”: jak przy użyciu podwójnego polimorfizmu dodawać do hierarchii klas wiele funkcji, dodając tylko jedną funkcję wirtualną.
Najbardziej realistyczne przykłady zastosowania tych technik dotyczą pracy ze strukturami danych, jak wektory, grafy czy wskaźniki do obiektów typów polimorficznych. W strukturach tych prawdziwy typ obiektu (np. elementu wektora albo węzła grafu) można poznać tylko dynamicznie poprzez (jawne lub niejawne) zbadanie interfejsu udostępnianego przez klasę bazową.
Podwójny polimorfizm
Zastanówmy się, jak wybrać funkcję na podstawie dwóch argumentów. Na przykład:
{
if (s1.intersect(s2)) {
// te dwa kształty nakładają się
}
//...
}
Chcielibyśmy, aby ten kod działał dla dowolnych dwóch klas, np. Circle i Triangle, z hierarchii klas, której korzeniem jest klasa Shape. Najprościej w celu wybrania odpowiedniej funkcji dla obiektów s1 i s2 jest wykonać po jednym wywołaniu funkcji wirtualnej dla każdego z nich. Dla uproszczenia pomijam obliczenia sprawdzające, czy kształty rzeczywiście się nakładają, i przedstawiam tylko szkielet kodu wybierającego odpowiednie funkcje. Najpierw zdefiniujemy klasę Shape, która zawiera funkcję sprawdzającą, czy kształty się nakładają:
class Triangle;
class Shape {
public:
virtual bool intersect(const Shape&) const =0;
virtual bool intersect(const Circle&) const =0;
virtual bool intersect(const Triangle&) const =0;
};
Następnie musimy zdefiniować klasy Circle i Triangle oraz przesłonić w nich funkcje wirtualne z klasy Shape:
public:
bool intersect(const Shape&) const override;
virtual bool intersect(const Circle&) const override;
virtual bool intersect(const Triangle&) const override
};
class Triangle : public Shape {
public:
bool intersect(const Shape&) const override;
virtual bool intersect(const Circle&) const override;
virtual bool intersect(const Triangle&) const override;
};
Teraz każda z klas może obsłużyć wszystkie możliwe klasy w hierarchii Shape, a więc pozostało
nam już tylko zdecydować, co ma się dziać z każdą kombinacją:
bool Circle::intersect(const Circle&) const { cout <<"intersect(circle,circle) ";
- return true; }
bool Circle::intersect(const Triangle&) const { cout <<"intersect(circle,triangle) ";
- return true; }
bool Triangle::intersect(const Shape& s) const { return s.intersect(*this); }
bool Triangle::intersect(const Circle&) const { cout <<"intersect(triangle,circle) ";
- return true; }
bool Triangle::intersect(const Triangle&) const { cout <<"intersect(triangle,triangle) ";
- return true; }
Najbardziej interesujące w tym kodzie są funkcje Circle::intersect(const Shape&) i Triangle -::intersect(constShape&). Ich argumentem jest Shape&, ponieważ argument ten musi odnosić się do derywowanej klasy. Cała sztuka/technika polega na tym, by wykonać wywołanie wirtualne z argumentami w odwróconej kolejności. Po zrobieniu tego będziemy w jednej z czterech
funkcji, które mogą wykonać prawdziwe obliczenia dotyczące nakładania się kształtów.
Możemy to przetestować, tworząc wektor wszystkich par wartości Shape* i wywołując dla nich funkcję intersect():
{
vector> vs { {&t,&t}, {&t,&c}, {&c,&t}, {&c,&c} };
for (auto p : vs)
p.first−>intersect(*p.second);
}
Użycie Shape* gwarantuje, że typy będą wybierane w czasie wykonywania. Otrzymujemy:
intersect(triangle,circle)
intersect(circle,triangle)
intersect(circle,circle)
Jeśli uważasz, że to rozwiązanie jest eleganckie, to musisz popracować nad poziomem, chociaż trzeba przyznać, że zadanie zostało wykonane. W miarę rozrastania się hierarchii klas zapotrzebowanie na funkcje wirtualne rośnie w tempie wykładniczym. W większości przypadków jest to nie do zaakceptowania. Rozszerzenie przykładu do trzech lub więcej argumentów byłoby bardzo łatwe, ale i żmudne. A najgorsze jest to, że dodanie jakiejkolwiek operacji i derywowanej klasy pociąga za sobą konieczność zmodyfikowania wszystkich klas znajdujących się w hierarchii: ta technika podwójnego polimorfizmu jest bardzo intruzyjna. Wolałbym zdefiniować jedną nieskładową funkcję intersect(Shape&,Shape&) oraz dodać specjalne przesłaniające
ją wersje dla wybranych kombinacji kształtów. Jest to możliwe [Pirkelbauer 2009], ale nie w języku C++11.
Jednak niezgrabność podwójnego polimorfizmu nie sprawia, że problem, który próbuje się przy jego użyciu rozwiązać, staje się mniej palący. Dość często zdarzają się sytuacje, w których wykonanie jakiegoś działania, np. intersect(x,y), zależy od typu dwóch lub większej liczby argumentów. To przyczynia się do powstawania wielu różnych okrężnych rozwiązań. Na przykład znajdowanie przecięcia dwóch prostokątów to operacja łatwa i nie sprawiająca problemów pod względem wydajnościowym. Dlatego też wielu programistów definiuje tylko „obramowanie” każdego kształtu i oblicza przecięcie na podstawie powierzchni zajmowanej przez
to obramowanie. Na przykład:
public:
virtual Rectangle box() const = 0; // prostokąt otaczający kształt
//...
};
class Circle : public Shape {
public:
Rectangle box() const override;
//...
};
class Triangle : public Shape {
public:
Rectangle box() const override;
//...
};
bool intersect(const Rectangle&, const Rectangle&); // łatwe do obliczenia
bool intersect(const Shape& s1, const Shape& s2)
{
return intersect(s1.box(),s2.box());
}
Inną stosowaną techniką jest uprzednie wyliczenie tablicy wyszukiwania kombinacji typów [Stroustrup 1994]:
{
auto i = index(type_id(s1),type_id(s2));
return intersect_tbl[i](s1,s2);
}
Powszechnie wykorzystywane są różne wersje tej techniki. W niektórych wcześniej obliczone wartości zapisuje się w obiektach w celu przyspieszenia identyfikacji typów.
Wizytatorzy
Dobrym, choć niepełnym rozwiązaniem problemu z namnażaniem funkcji wirtualnych i ich przesłonięć oraz niepożądaną intruzyjnością nazbyt prostej techniki podwójnego polimorfizmu jest wzorzec wizytator [Gamma 1994].
Zastanówmy się, jak zastosować dwie lub więcej operacji do każdej klasy w hierarchii. Do tego celu wykorzystalibyśmy podwójny polimorfizm, tworząc hierarchię węzłów oraz hierarchię operacji do wyboru dla poszczególnych węzłów. Operacje te nazywają się wizytatorami (ang. visitor) i zdefiniujemy je w klasie Visitor. Węzły są hierarchią klas zawierających funkcję wirtualną accept() przyjmującą argument typu Vistitor&. Poniższy przykład przedstawia hierarchię węzłów (Node) reprezentujących konstrukcje językowe, jakie powszechnie spotyka się w narzędziach opartych na abstrakcyjnych drzewach składniowych (AST):
class Node {
public:
virtual void accept(Visitor&) = 0;
};
public:
void accept(Visitor&) override;
};
class Stmt : public Node {
public:
void accept(Visitor&) override;
};
Hierarchia Node dostarcza wirtualną funkcję accept() przyjmującą argument typu Visitor& reprezentujący operację, która ma zostać wykonana na węźle określonego typu. Nie użyłem słowa kluczowego const, bo generalnie operacja z wizytatora może zmodyfikować zarówno „odwiedzany” węzeł (Node), jak i samego „odwiedzającego” (Visitor). Teraz funkcja accept() z klasy Node realizuje podwójny polimorfizm, tzn. przekazuje obiekt klasy Node do funkcji accept() klasy Visitor:
void Stmt::accept(Visitor& v) { v.accept(*this); }
Klasa Visitor zawiera zestaw deklaracji operacji:
public:
virtual void accept(Expr&) = 0;
virtual void accept(Stmt&) = 0;
};
Mając to, możemy definiować zestawy operacji, tworząc klasy pochodne klasy Visitor i przesłaniając jej funkcje accept(). Na przykład:
void accept(Expr&) override { cout << "do1 do Expr "; }
void accept(Stmt&) override { cout << "do1 do Stmt "; }
};
struct Do2_visitor : public Visitor {
void accept(Expr&) override { cout << "do2 do Expr "; }
void accept(Stmt&) override { cout << "do2 do Stmt "; }
};
W ramach testu możemy utworzyć wektor par wskaźników, aby sprawdzić, czy stosowane jest rozstrzyganie w czasie wykonywania:
void test(Expr& e, Stmt& s)
{
vector> vn {&e,&do1}, {&s,&do1}, {&e,&do2}, {&s,&do2}};
for (auto p : vn)
p.first−>accept(*p.second);
}
Otrzymujemy:
do1 do Expr
do1 do Stmt
do2 do Expr
do2 do Stmt
W odróżnieniu od prostego podwójnego polimorfizmu wzorzec wizytator jest powszechnie wykorzystywany w realnych programach. Jego intruzyjność jest niewielka (dotyczy funkcji accept()) i powstało wiele różnych odmian. Niestety istnieje też wiele takich operacji na hierarchiach klas, które trudno jest wyrazić przy użyciu wizytatorów. Na przykład nie da się łatwo zaimplementować jako wizytatora operacji wymagającej dostępu do wielu węzłów różnego typu w grafie. Dlatego wzorzec wizytator uważam tylko za mało eleganckie obejście. Istnieją inne rozwiązania, jak opisane w [Solodkyy 2012], ale nie są one dostępne w czystym języku C++11. Większość stosowanych w języku C++ rozwiązań mających zastąpić wizytatora działa
w oparciu o iterację przez jakąś jednolitą strukturę danych (np. wektor albo graf węzłów zawierających wskaźniki do polimorficznych typów). Dla każdego elementu lub węzła wywołanie funkcji wirtualnej może spowodować wykonanie odpowiedniej operacji lub może zostać przeprowadzona optymalizacja na podstawie zapisanych danych.
Język C++. Kompendium wiedzy. Wydanie IV, Autor: Bjarne Stroustrup, Wydawnictwo: Helion
