C ++: Leash Pattern

The other day, a colleague threw such a problem:

“There are two types of objects - Human and Dog . Human may own a dog (or may not own it). Dog may have some owner (or may not have). It is clear that if some object of type Human owns some object of type Dog , then for this object of type Dog exactly this object of type Human is the owner and only he. And Dog must know who his Human , and vice versa. How would you do this? ”

It would seem that everything is simple - we will get two pointers on each other from the classes Human and Dog and it's in the bag. But the implementation of this venture led me to the idea, I think, of a new design pattern.

And if not a template, then at least C ++ idioms, which allow using bi-directional links in the program with static type control and a couple of useful "buns".
')
Note: the term “link” is used in the article in the meaning of “link”, and not in the meaning of “C ++ link” .

First, let's see what the first idea with pointers is wrong with?

Lead v.1 ("in the forehead")

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; } } 

This implementation allows you to solve the task, as they say, “head on”:

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

However, it has several obvious flaws:

1. You can forget to set the reciprocal link: d->SetLink(h) .
2. You can mistakenly set a reverse link to another object: d->SetLink(h2) .
3. After the destruction of one of the related objects, another object will refer to the deleted object.

Getting rid of these shortcomings is easy enough:

Lead v.2 (automatics)

 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; } } 

What changed?

First, the SetLink() methods became more complicated. Now, when setting the link in one direction, the method automatically sets the link in the other direction. Forget to install one of the links is impossible. Exactly as it is impossible to establish an incorrect back link:

 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) 

Secondly, destructors appeared, which, when destroying an object, automatically remove the link from the associated object, if any. Thus, by GetLink() you can always expect either a valid pointer or NULL.

Well, now, it would seem, all the flaws are eliminated and can be used. However, an attentive reader will note that the implementation of the classes Human and Dog is identical and differs only in the types used. And then I thought: “it is necessary to remake it into templates!” It is said - done.

Lead v.3 (templates)

A template implies parameterization by one or several types. In our case, there are two types: M (My) and L (Link), and the template itself is respectively written as O <M, L> . An instance of the specialization of such a template is able to store a pointer to an object of type L , that is, it organizes a relationship M -> L. To create a two-way communication between classes A and B , two symmetric specializations are used: O <A, B> and O <B, A> .

Thus, the type M shows the type of the inner end of the link and is needed in order to correctly cast the this pointer, and the type L shows the type of the outer end of the link:

 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; } }; 

Using this template class is very simple:

 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); 

Fine! We recorded our classes two times shorter!

A nice feature of this implementation of bidirectional links is that the compiler will be able to determine some logical errors for us.

For example, the absence of a class that is the response of the link. That is, if there is a class in the code that can contain the Human -> Dog link, but there is no class that can contain the Dog -> Human link, then such code will not compile:

 template<class M, class L> class O { ... }; class Human; class Dog; class Human: public O<Human, Dog> {}; class Dog {}; 

Of course, it is allowed to link objects of the same type:

 template<class M, class L> class O { ... }; class Human: public O<Human, Human> {}; Human *h1, *h2; ... h1->SetLink(h2); 

You can even set a link to yourself. If this is unacceptable, it is easy to fix the SetLink() method SetLink() .

It seems now quite good! And what if Human 'u, in addition to the reference to the Dog object, is required to have a reference to the Cat object?

Lead v.4 (multiple links)

This can also be easily done using multiple inheritance and a slightly modified class 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> {}; 

The explicit resolution of the namespace O <L, M> was SetLink in order to SetLink function from the correct base class. The attentive reader will notice that the compiler could choose the correct SetLink() function according to the type of the parameter passed to it, as is done in the case of overloaded functions. However, if these functions are in different classes (in our case, in different parent classes), then according to the C ++ standard, overloading does not work [1].

The same changes will affect users of our classes:

 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(); //,   

This can be simplified by slightly modifying the Human class. Add in it SetLink() implementations of the own SetLink() and GetLink() methods, which will call the corresponding method of one or another parent class depending on the type:

 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); } }; 

Now everything is almost as simple as in the case of single connections:

 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 

What happened?

It turned out a convenient (in my opinion) template class, which allows you to establish bidirectional connections between objects of strictly defined types with automatic ensuring their integrity .

Yes, do not ask me why I called the template class letter O. Best of all he would have come up with the name Leash (a leash).

Written was tested using gcc 4.4.3.

Links

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

Ps. If someone knows the online version of the current C ++ standard, share the link - I would like to refer to the original source.

Pps. While this topic was languishing on a slow fire in the Sandbox, I had an idea how to simplify the use of O in the case of multiple references, and using C ++ 0x. Stay tuned.