С++: шаблон «поводок» / Habr

Намедни коллега подкинул такую задачку:

«Есть два типа объектов — Human и Dog. Human может владеть некоторой собакой (а может и не владеть). Dog может иметь некоторого хозяина (а может и не иметь). Понятно, что если некоторый объект типа Human владеет некоторым объектом типа Dog, то для данного объекта типа Dog именно данный объект типа Human является хозяином и только он. Причем Dog должен знать, кто его Human, и наоборот. Как бы ты это реализовал?»

Казалось бы, всё просто — заведём два указателя друг на друга у классов Human и Dog и дело в шляпе. Но реализация данной затеи привела меня к идее, как мне кажется, нового шаблона проектирования.

А если и не шаблона, то, по крайней мере, C++ идиомы, позволяющей использовать в программе двунаправленные ссылки со статическим контролем типов и парой полезных «плюшек».

Примечание: понятие «ссылка» используется в статье в значении «связь», а не в значении «C++ ссылка».

Во-первых, давайте разберёмся, чем плоха первая идея с указателями?

Поводок v.1 («в лоб»)

class Dog;
class Human;

class Dog {
    Human* link;
public:
    Dog(): link(NULL) {}
    void SetLink(Human* l) {
        link = l;
    }
    const Human* GetLink() const {
        return link;
    }
}

class Human {
    Dog* link;
public:
    Human(): link(NULL) {}
    void SetLink(Dog* l) {
        link = l;
    }
    const Dog* GetLink() const {
        return link;
    }
}

Такая реализация позволяет решить поставленную задачу, что называется, «в лоб»:

Human *h = new Human();
Dog *d = new Dog();
h->SetLink(d);
d->SetLink(h);

Однако, у неё есть несколько очевидных недостатков:

Можно забыть установить обратную ссылку: d->SetLink(h).
Можно по ошибке установить обратную ссылку на другой объект: d->SetLink(h2).
После уничтожения одного из связанных объектов, другой объект будет ссылаться на уничтоженный объект.

Избавиться от этих недостатков достаточно легко:

Поводок v.2 (автоматика)

class Dog;
class Human;

class Dog {
    Human* link;
public:
    Dog(): link(NULL) {}
    ~Dog() {
        if (link)
            link->SetLink(NULL);
    }
    void SetLink(Human* l) {
        if (link == l)
            return;
        Human* oldlink = link;
        link = NULL;
        if (oldlink)
            oldlink->SetLink(NULL);
        link = l;
        if (link)
            link->SetLink(this);
    }
    const Human* GetLink() const {
        return link;
    }
}

class Human {
    Dog* link;
public:
    Human(): link(NULL) {}
    ~Human() {
        if (link)
            link->SetLink(NULL);
    }
    void SetLink(Dog* l) {
        if (link == l)
            return;
        Dog* oldlink = link;
        link = NULL;
        if (oldlink)
            oldlink->SetLink(NULL);
        link = l;
        if (link)
            link->SetLink(this);
    }
    const Dog* GetLink() const {
        return link;
    }
}

Что изменилось?

Во-первых, усложнились методы SetLink(). Теперь, при установке ссылки в одном направлении, метод автоматически устанавливает ссылку и в другом направлении. Забыть установить одну из ссылок невозможно. Ровно как и нельзя установить неправильную обратную ссылку:

Human *h1, *h2;
h1 = new Human();
h2 = new Human();
Dog *d = new Dog();
h1->SetLink(d);
assert(h1->GetLink()->GetLink() == h1); //passed (d автоматически привязался к h1)
d->SetLink(h2);
assert(d->GetLink()->GetLink() == d); //passed (h2 автоматически привязался к d)
assert(h1->GetLink() == NULL); //passed (h1 автоматически отвязался от d)

Во-вторых, появились деструкторы, которые при уничтожении объекта автоматически убир��ют ссылку со связанного объекта, если таковой имелся. Таким образом, по GetLink() можно всегда ожидать либо валидный указатель либо NULL.

Отлично, теперь, казалось бы, все недостатки устранены и можно пользоваться. Однако, внимательный читатель заметит, что реализация классов Human и Dog идентична и отличается только используемыми типами. И тут мне подумалось: «надо это переделать на шаблоны!» Сказано — сделано.

Поводок v.3 (шаблоны)

Шаблон подразумевает параметризацию одним или несколькими типами. В нашем случае таких типов два: M (My) и L (Link), а сам шаблон соответственно запишется как O<M,L>. Экземпляр специализации такого шаблона способен хранить указатель на объект типа L, то есть организует связь M -> L. Для создания двусторонней связи между классами A и B используется две симметричные специализации: O<A,B> и O<B,A>.

Таким образом, тип M показывает тип внутреннего конца ссылки и нужен, чтобы правильно привести указатель this, а тип L показывает тип внешнего конца ссылки:

template<class M, class L>
class O
{
    L* link;

public:
    O(): link(NULL) {}
    ~O() {
        if (link)
            link->SetLink(NULL);
    }
    void SetLink(L* l) {
        if (link == l)
            return;
        L* oldlink = link;
        link = NULL;
        if (oldlink)
            oldlink->SetLink(NULL);
        link = l;
        if (link)
            link->SetLink(static_cast<M*>(this));
    }
    const L* GetLink() const {
        return link;
    }
};

Использовать этот шаблонный класс очень просто:

class Human;
class Dog;

class Human: public O<Human, Dog> {};
class Dog: public O<Dog, Human> {};

Human* h = new Human();
Dog* d = new Dog();
h->SetLink(d);

Отлично! Мы записали наши классы в два раза короче!

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

Например, отсутствие класса, являющегося ответной стороной ссылки. То есть, если в коде есть класс, который может содержать ссылку Human -> Dog, но нет класса, который может содержать ссылку Dog -> Human, то такой код не скомпилируется:

template<class M, class L> class O { ... };

class Human;
class Dog;

class Human: public O<Human, Dog> {};
class Dog {};

Разумеется, разрешается связывать объекты одного и того же типа:

template<class M, class L> class O { ... };

class Human: public O<Human, Human> {};

Human *h1, *h2;
...
h1->SetLink(h2);

Можно даже устанавливать ссылку на самого себя. Если это недопустимо, несложно исправить соответствующим образом метод SetLink().

Вроде теперь совсем хорошо! А что если Human'у вдобавок к ссылке на объект Dog требуется иметь ссылку на объект Cat?

Поводок v.4 (множественные ссылки)

Это тоже можно легко устроить с использованием множественного наследования и немного доработанного класса O:

template<class M, class L>
class O
{
    L* link;

public:
    O(): link(NULL) {}
    ~O() {
        if (link)
            link->O<L,M>::SetLink(NULL);
    }
    void SetLink(L* l) {
        if (link == l)
            return;
        L* oldlink = link;
        link = NULL;
        if (oldlink)
            oldlink->O<L,M>::SetLink(NULL);
        link = l;
        if (link)
            link->O<L,M>::SetLink(static_cast<M*>(this));
    }
    const L* GetLink() const {
        return link;
    }
};

class Human;
class Dog;
class Cat;

class Human: public O<Human, Dog>, public O<Human, Cat> {};
class Dog: public O<Dog, Human> {};
class Cat: public O<Cat, Human> {};

Добавилось явное разрешение пространства имён O<L,M> для того, чтобы вызывалась функция SetLink от правильного базового класса. Внимательный читатель заметит, что компилятор и так мог бы выбрать правильную функцию SetLink() по типу передаваемого ей параметра, как это делается в случае перегружаемых функций. Однако, если эти функции находятся в разных классах (в нашем случае — в разных родительских классах), то согласно стандарту C++ перегрузка не работает [1].

Те же изменения коснутся и пользователей наших классов:

Human* h;
Dog* d;
Cat* c;
...

// h->SetLink(d); //так нельзя, неоднозначность
h->O<Human, Dog>::SetLink(d); //работает, но громоздко
h->O<Human, Cat>::SetLink(c); //то же самое и с кошкой

//аналогично и с GetLink()
// h->GetLink(); //не��онятно, какой Link мы хотим - на кошку или на собаку
h->O<Human, Dog>::GetLink(); //работает, но громоздко

Это можно упростить, немного доработав класс Human. Добавим в него шаблонные реализации собственных методов SetLink() и GetLink(), которые будут вызывать соответствующий метод того или иного родительского класса в зависимости от типа:

class Human: public O<Human, Dog>, public O<Human, Cat>
{
public:
    template<class T>
    const T* GetLink() const {
        return O<Human,T>::GetLink();
    }
    
    template<class T>
    void SetLink(T* l) {
        O<Human,T>::SetLink(l);
    }
};

Теперь всё почти так же просто, как и в случае одиночных связей:

Human* h;
Dog* d;
Cat* c;
...

h->SetLink<Dog>(d);
h->SetLink<Cat>(c);

//а можно и так, если нет других неоднозначностей
h->SetLink(d);
h->SetLink(c);

h->GetLink<Dog>(); //ссылка на Dog
h->GetLink<Cat>(); //ссылка на Cat

Что же получилось?

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

Да, не спрашивайте меня, почему я назвал шаблонный класс буквой O. Лучше всего ему бы подошло имя Leash (поводок).

Написанное тестировалось с использованием gcc 4.4.3.

Ссылки

[1] bytes.com/topic/c/answers/137040-multiple-inheritance-ambiguity

PS. Если кто-нибудь знает онлайн-версию действующего стандарта C++, поделитесь ссылкой — хочется сослаться именно на первоисточник.

PPS. Пока этот топик томился на медленном огне в Песочнице, у меня созрела идея как можно ещё упростить использование O в случае множественных ссылок, причем с использованием C++0x. Stay tuned.