Обхід графа успадкування в C + +, Різне, Програмування, статті

Введення


Напевно багато хто з вас під час проходження співбесіди, на тестуванні BrainBench або ще де-небудь зустрічалися з такою академічної завданням, як обхід графа успадкування. Звучить завдання простіше: у якій послідовності будуть викликатися конструктори в представленій ієрархії, і далі йде лістинг. Природно, вирішувати цю задачу треба без використання компілятора. Отже, тут я спробую виділити деякі правила щодо вирішення цього завдання. Домовимося малювати граф зліва направо, тобто якщо “A” успадковує “B”, а потім “C”, то стрілка “AB” буде лівіше стрілки “AC”. І ще … Перераховувати порядок виклику конструкторів ми будемо з кінця – так легше.


Невіртуальна спадкування


Розглянемо для початку приклади на невіртуальної спадкування.


Правило тут одне – найголовніше та гілка, яка розташована правіше


Лістинг 1





#include<iostream>
class A1
{
public:
A1(){std::cout << “A1 “;}
};
class A2
{
public:
A2(){std::cout << “A2 “;}
};
class B1: public A1
{
public:
B1(){std::cout << “B1 “;}
};
class B2: public A2
{
public:
B2(){std::cout << “B2 “;}
};
class C: public B1, public B2
{
public:
C(){std::cout << “C “;}
};
class E: public C
{
public:
E(){std::cout << “E “;}
};
void main()
{
E *e = new E();
}

На основі лістингу отримуємо наступний граф


 


Починаємо обхід, як я вже казав, з кінця. Спочатку слід “E”, потім у вузлі “C” застосовуємо наше правило. Дійшовши до кінця, повертаємося до вузла “C” (враховувати вдруге його не треба) і йдемо по лівій гілки. Вийшло “E C B2 A2 B1 A1”. Інвертуємо порядок – “A1 B1 A2 B2 CE”


Розглянемо інший приклад


Лістинг 2





#include<iostream>
class A1
{
public:
A1(){std::cout << “A1”;}
};
class A2
{
public:
A2(){std::cout << “A2”;}
};
class B1: public A1
{
public:
B1(){std::cout << “B1”;}
};
class B2: public A2
{
public:
B2(){std::cout << “B2”;}
};
class C: public B1, public B2
{
public:
C (){std::cout << “C”;}
};
class D1: public C
{
public:
D1(){std::cout << “D1”;}
};
class D2: public C
{
public:
D2(){std::cout << “D2”;}
};
class E: public D1, public D2
{
public:
E(){std::cout << “E”;}
};
void main()
{
E *e = new E();
}

Отримуємо наступний граф


 


Починаємо, як звичайно, з правого гілки – “E D2 C”. Дійшовши до “C”, бачимо чергове розгалуження. Застосовуємо правило – “B2 A2 B1 A1”. А тепер те ж саме, але по лівій гілки – “E” вже не враховуємо, “D1 C”. Дійшовши до розгалуження, застосовуємо правило – “B2 A2 B1 A1”. В результаті маємо – “E D2 C B2 A2 B1 A1 D1 C B2 A2 B1 A1”. Інвертуємо – “A1 B1 A2 B2 C D1 A1 B1 A2 B2 C D2 E”


Ще приклад:


Лістинг 3





#include<iostream>
class G
{
public:
G(){std::cout << “G”;}
};
class A1: public G
{
public:
A1(){std::cout << “A1”;}
};
class A2: public G
{
public:
A2(){std::cout << “A2”;}
};
class B1: public A1
{
public:
B1(){std::cout << “B1”;}
};
class B2: public A2
{
public:
B2(){std::cout << “B2”;}
};
class C1: public B1, public B2
{
public:
C1(){std::cout << “C1”;}
};
class D1: public C
{
public:
D1(){std::cout << “D1”;}
};
class D2: public C
{
public:
D2(){std::cout << “D2”;}
};
class E: public D1, public D2
{
public:
E(){std::cout << “E”;}
};
void main()
{
E *e = new E();
}


 


Тут все те ж саме, тільки закінчується на “G”. При обході будемо мати “E D2 C B2 A2 G B1 A1 G D1 C B2 A2 G B1 A1 G”. У підсумку, інвертувати, отримаємо “G A1 B1 G A2 B2 C D1 G A1 B1 G A2 B2 C D2 E”


А що буде, припустимо, якщо клас G успадкують класи B1 і B2, причому B1 успадкує клас G після успадкування класу A1, а B2 успадкує G до спадкування A2. Все просто. Нам потрібно буде писати “G” всякий раз, після того як ми обійдемо гілку “B2-> A2-> G”.


Ось так все просто, коли у нас присутня тільки лише одне невіртуальної спадкування. З віртуальним трохи складніше, але ненабагато.


Віртуальне успадкування


Я буду позначати віртуальне успадкування червоною стрілкою, а не віртуальне, як і раніше, чорної.


Тепер у нас додадуться ще правила для обходу графа. Відразу узагальнимо на випадок змішаного спадкування, тобто в якому є як віртуальне, так і невіртуальної.



  1. Серед невіртуальний гілок найголовніше та, що правіше.
  2. Серед віртуальних гілок найголовніше та, що правіше.
  3. Невіртуальна гілку найголовніше віртуальною.
  4. Клас успадковується тільки по одному віртуальному гілки, розташованої ліворуч від всіх і за всіма невіртуальний.
  5. При наявності невіртуальної альтернативи, обхід графа тимчасово припиняється за поточною гілки, якщо зустрілася віртуальна. Обхід продовжується після того, як будуть недоступні невіртуальний альтернативи.
  6. При наявності віртуальних альтернатив, вибирається сама права альтернатива, а за поточною гілки обхід переривається до тих пір, поки не будуть вичерпані всі альтернативи, що знаходяться правіше.

Правила 5 і 6 насправді можна об’єднати в одне. Пізніше ви в цьому переконаєтеся самі.


Думаю, ви зрозуміли принципи побудови графа відповідно до лістингами, і, так як зв’язок між графом і лістингом взаємно однозначна, далі я буду представляти тільки графи, щоб не захаращувати кодом статтю.


Отже, розглянемо перший приклад.


 


Тут, як зрозуміло з малюнка, “D” успадковує віртуально три класи – “A”, “B” і “C”. Відмінно! Застосовуємо друге правило і отримуємо “DCBA”, інвертуємо – отримуємо “ABCD”. Все тривіально.


Розглянемо трохи інший приклад.


 


Бачимо, що у нас змішане спадкування. З чого почати? А про це йдеться в п.3 – починаємо з невіртуальний гілок – “EDB”, і закінчуємо на віртуальних – “CA”. Звідси, остаточно інвертований, маємо “A C B D E”.


А як будемо чинити з цим?


 


Так, дійсно, спочатку вибираємо “AD” по п.3, але не поспішайте робити перехід по “DE”, а краще погляньте на п.4. Так, саме на п.4. Спадкування буде проходити по шляху “BE”, і тільки по ньому (!) Серед віртуальних гілок. Отже, ми маємо “AD”, потім “CE”, адже невіртуальний гілки не впливають на віртуальні, а після – “BE”. Інвертуємо порядок, отримуємо “EBECDA”. Простіше кажучи, якщо ми бачимо, що до одного класу підходять кілька віртуальних гілок, можемо сміливо прибирати все, крім крайньої лівої.


У наступному прикладі нас чекає одна тонкість.


 


Починаємо як завжди з головної (в даному випадку вона єдина) невіртуальної гілки – “GE”. Далі логічно зробити перехід на B, але нас повинно насторожити те, що гілка помінялася на віртуальну, а це означає, що слід “озирнутися” в пошуках інших невіртуальний гілок (п.5) або віртуальних гілок (п.6), які можуть мати більший пріоритет, ніж поточна. І правда, така є, це – “GF”, далі “C”, і не забуваємо про п.4, тому “H” не включаємо. Більше пріоритетних альтернатив немає, тому продовжимо обхід – “EB”, далі знову п.4, обхід “GDAH”. Якщо зібрати всі воєдино, то отримаємо наступний маршрут: “G E F C B D A H”. Інвертуємо: “H A D B C F E G”


Приклад використання п.5 представлений нижче.


 


Почали – “GE”, зустріли віртуальну гілку, знайшли альтернативу “D”, “A”. Далі маємо ще одну віртуальну альтернативу (тому правіше) “F”, “G”. Закінчуємо переходом на “B”. Отримуємо “G E D A F C B”. Підсумок – “B C F A D E G”.


І, наостанок, розглянемо такий екзотичний приклад. Згідно п.4, можна спростити граф, прибравши гілки “DE”, “CE” і “DC”. Починаємо обхід: “AD”, зустрівши віртуальну гілка після невіртуальної, шукаємо альтернативу: “BGE”, повертаємося до незакінченої гілки на “H”, “E”. Залишилася віртуальна гілку “AC”, далі “B”, “G”, “E” і ще раз E по віртуальній гілки BE (дійсно “E” може повторюватися, адже це не вузол, в відміну від “G”). Маємо “A D B G E H E C B G E E”. Інвертуємо, отримаємо “EEGBCEHEGBDA”.


 

 


Підсумок


Ось ми і розглянули, мабуть, всі прості випадки і деякі екзотичні. Чесно зізнатися, не знаю, де може застосовуватися таке спадкування, як в останньому прикладі, але, знову ж таки, підкреслю академічний характер завдання. Та й непогано отримати звання “Ходячий компілятор”.

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*