Pull to refresh

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

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

«Есть два типа объектов — 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);


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

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

Поводок 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.
Tags:c++шаблоны
Hubs: C++
Total votes 54: ↑51 and ↓3 +48
Views4.7K

Popular right now

Разработчик C++
from 290,000 to 300,000 ₽ВГТМосква
C++
from 100,000 to 300,000 ₽OvisionСанкт-Петербург
Senior C++ / JS Developer
from 200,000 to 300,000 ₽ZennoLabRemote job
Gameplay UE4 C++ Developer
from 200,000 ₽Omniverse GamesСанкт-Петербург
Python / C++ разработчик
from 150,000 to 230,000 ₽Wunder FundRemote job

Top of the last 24 hours