Обхождане на графа на наследяване в C - Софтуерни продукти

Със сигурност много от вас по време на интервюто, при тестването на BrainBench или някъде другаде са се сблъскали с такава академична задача като заобикаляне на графиката на наследяване. Задачата звучи по-просто: в каква последователност ще бъдат извикани конструкторите в представената йерархия и след това следва списъкът. Естествено, този проблем трябва да се реши без използване на компилатор. И така, тук ще се опитам да подчертая някои правила за решаване на този проблем. Нека се съгласим да начертаем графиката отляво надясно, т.е. ако "A" наследи "B" и след това "C", тогава стрелката "AB" ще бъде отляво на стрелката "AC". И още нещо ... Ще изброим реда на извикване на конструктори от края - така е по-лесно.

Невиртуално наследяване

Нека започнем с примери за невиртуално наследяване.

Има само едно правило - по-важен е клонът, който е разположен вдясно

Въз основа на листинга получаваме следната графика

Започваме да заобикаляме, както казах, от края. Първо идва "E", след това във възел "C" прилагаме нашето правило. След като стигнем до края, се връщаме към възел "C" (не е необходимо да го вземаме предвид втори път) и тръгваме по левия клон. Оказа се "E C B2 A2 B1 A1". Обърнете реда - "A1 B1 A2 B2 C 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"

Тук всичко е същото, само че завършва на "G". При преминаване ще имаме "E D2 C B2 A2 G B1 A1 G D1 C B2 A2 G B1 A1G". В резултат на обръщане получаваме "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". Страхотен! Прилагаме второто правило и получаваме "D C B A", обръщаме - получаваме "A B C D". Всичко е тривиално.

Нека разгледаме малко по-различен пример.

Виждаме, че имаме смесено наследство. Откъде да започна? И това е споменато в параграф 3 - започваме с невиртуални разклонения - "E D B", и завършваме с виртуални - "C A". Следователно, накрая обръщайки, имаме "A C B D E".

Как ще се справим с това?

Да, наистина, първо избираме „AD“ според параграф 3, но не бързайте да направите прехода към „DE“, а по-скоро погледнете параграф 4. Да точно по точка 4. Наследяването ще върви по пътя "BE" и само по него (!) сред виртуални клонове. И така, имаме "AD", след това "CE", тъй като невиртуалните разклонения не засягат виртуалните, и след това - "BE". Като обърнем реда, получаваме "E B E C D A". Просто казано, ако видим, че няколко виртуални клона отговарят на един и същи клас, можем безопасно да премахнем всичко, освен най-левия.

В следващия пример ни очаква една тънкост.

Започваме както обикновено с основния (в случая това е единственият) невиртуален клон - "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". Завършваме с прехода към "Б". Получаваме "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"). Имаме "AD B G E H E C B G E E". Обръщайки се, получаваме "E E G B C E H E G B D A".

Така че разгледахме може би всички прости случаи и някои екзотични. Честно казано, не знам къде може да се приложи такова наследяване, както в последния пример, но отново ще подчертая академичния характер на проблема. И не е зле да получиш титлата "Ходещ компилатор".

---