наследование в C++

[malin]

Здравствуйте, товарищи!
Дали задание написать красно-черные деревья двоичного поиска.

Вначале я написал просто дерево бинарного поиска с кучей методов(вставка, повороты, удаление, поиск, обход и т.д....)
Класс выглядит таким образом:

template <class T>
class CTree
{
  public:
    T value;
    CTree<T>* Parent;   //элементами деревьев являются деревья,
    CTree<T>* Left;     //своеобразная рекурсия, но есть ньюанс:
    CTree<T>* Right;    //создавая новое дерево, надо создавать указатель!
.........

Далее хотел бы написать красно-черное дерево с помощью наследования. Напомню, что красно-черное дерево отличается от обычного наличием дополнительного поля класса - цвета узла.(опустим пока балансировку)

И тут возникли проблемы следующего характера:
Дело в том, что если попытаться наследовать базовый класс CTRee:

template <class T>
class CRBTree : public CTree<T>
.........

то полями нового нового класса CRBTree будут являться указатели Parent,Left,Right на базовый класс CTRee.(А хочется, чтобы были указатели на производный класс).
Вопрос к крутым программистам: "Как быть? Неужели придется переписывать класс заново?"

[venco]

Может, положить цвет узла в тип - параметр CTree<>?

template <class T>
class CRBTreeElement
{
    int color;
    T data;
};

template <class T>
class CRBTree : public CTree< CRBTreeElement<T> >

[malin]

Спасибо за вариант, но в таком случае нет смысла в наследовании вообще. Если мы имеем цвет в базовом классе, зачем же наследование?

Я тут перечитал шилдта, вспомнил, что указатели на экземпляры базового класса могут указывать на экземпляры производного класса, и можно тут что-то сделать...
Но это уже за гранью моего сознания - указатели выносят мозг...

[arseniiv]

1. Мне почему-то кажется, что наследовать тут ой нельзя вообще.
2. Как правило, класс (обычно не класс, а struct) для структуры данных помещают внутрь класса с методами для её обработки. Инкапсуляция тут кстати — лучше, чтобы нкиаким, кроме определённых способов, изменить дерево было нельзя, иначе это будет иметь плохие последствия (допустим, вы отбалансировали дерево, а потом какая-то процедура нечайно удалила левое поддерево). Т. е. переписать стоит вот как:

Используется синтаксис C++

template <class T>
class CTree {
private:
  struct Node {
    Node<T> *L, *R;
    T value;
    Node(T aValue): value(aValue) {} // для удобства в алгоритмах
  } *top;
  // метод балансировки лучше описать здесь, потому что его используют только методы CTree, остальным это делать излишне
public:
  // методы, доступные извне
}
 

(И все ваши «ньюансы» ушли внутрь, и никому о них, кроме CTree, знать не надо.)

Кстати, зачем у вас был указатель Parent? Можно обойтись и без него.

-- Вс окт 17, 2010 15:59:09 --

malin в сообщении #362866 писал(а):

Но это уже за гранью моего сознания - указатели выносят мозг...

Конечно, если их использовать неправильно.

[malin]

Цитата:

Как правило, класс (обычно не класс, а struct) для структуры данных помещают внутрь класса с методами для её обработки.

Это совсем другой вопрос, изначально причина была такая:"О! прикольно, элементами дерева являются деревья!!!"
Но потом стало понятно, что так очень удобно работать с поддеревьями - все методы, доступные для дерева, доступны и для любого его поддерева. Это просто Супер_Удобно!

Цитата:

Кстати, зачем у вас был указатель Parent? Можно обойтись и без него.

Можно, но так сложнее писать вставку и удаление в красно - черное дерево. Более того, если мы знаем родителя, вставка-удаление в RBдерево производится намного быстрее(нам надо знать родителя, дядю и брата узла)

[arseniiv]

malin в сообщении #362873 писал(а):

Это совсем другой вопрос, изначально причина была такая:"О! прикольно, элементами дерева являются деревья!!!"
Но потом стало понятно, что так очень удобно работать с поддеревьями - все методы, доступные для дерева, доступны и для любого его поддерева. Это просто Супер_Удобно!

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

[Circiter]

Позвольте немного переформулировать задачу тописктартера: как в классе узнать свой собственный тип? :) Что-то вроде typeof(*this). :)

[EtCetera]

Circiter в сообщении #365924 писал(а):

как в классе узнать свой собственный тип?

RTTI (run-time type information).
Оператор typeid и класс typeinfo, сконцентрированные в typeinfo.h, осуществляют подобный трюк.
Хотя всегда можно и самому что-то подобное написать...

[Postrelyonysh]

malin в сообщении #362837 писал(а):

Далее хотел бы написать красно-черное дерево с помощью наследования. Напомню, что красно-черное дерево отличается от обычного наличием дополнительного поля класса - цвета узла.(опустим пока балансировку)

Наследование нужно лишь для проектирования, т.е., говоря проще, для придания коду гибкости с целью предусмотрения возможных изменений в ТЗ. Для заведомо однозначных, давно проработанных мат.моделей (таких как деревья) в этом нет ни малейшего смысла, и ни всякое там наследование классов, ни какие более высокоуровневые механизмы не нужны - можно и на Фортране написать.

Так что лучше напиши на Си, и, если очень хочется, оберни в класс как в синтаксический сахар. Не порть код наследованием - его потом незабайндишь никуда.

Если же ты хочешь изучать методологии проектирования, то худший контекст, в котором их можно познавать и отрабатывать - это как раз язык уродливый язык Algol with Classes (к числу диалектов которого принадлежит и С++) - так что не советую углубляться в этом направлении. Одно дело - трахаться с ним из-за legacy code, и совсем другое - полагать, что именно это и представляет собой объективную сложность программирования. В последнем случае за несколько лет опыта формируется ничем не исправимый алголовский формат мышления, несчастные инвалиды умственного труда так везде по-алголовски и пишут.

-- Пн окт 25, 2010 10:20:29 --

Circiter в сообщении #365924 писал(а):

как в классе узнать свой собственный тип?

Проще сразу отказаться от С++ как от заведомо ущербной технологии и взять язык с другой семантикой - там таких вопросов просто не возникнет. А если это будет ещё и язык динамический, то можно будет не то, что программно прочитать тип, а даже изменить его в рантайме.

В принципе, есть методы героического преодоления самостоятельно созданных себе трудностей - они называются пафосным термином "паттерны проектирования", но опять же, прежде чем калечить себе формат мышления подобными вещами, лучше разобраться хорошенько в программировании, разложить всё по причинно-следственным связям - тогда сразу станут ясны не только все подводные камни, об которые можно поранить ноги при использовании в подобных ситуациях С++, но и более-менее вменяемые способы эти камни обходить.

-- Пн окт 25, 2010 10:55:49 --

arseniiv в сообщении #362894 писал(а):

malin в сообщении #362873 писал(а):

Это совсем другой вопрос, изначально причина была такая:"О! прикольно, элементами дерева являются деревья!!!"
Но потом стало понятно, что так очень удобно работать с поддеревьями - все методы, доступные для дерева, доступны и для любого его поддерева. Это просто Супер_Удобно!

А так же издевательство над принципами ООП.

Деревья к ООП не имеют ни малейшего отношения - это типичный ADT. Деревья можно реализовывать на ОО-языках, но от того, что ты обернёшь не-объектную модель в объект, ты ООП как таковое не получишь. Программа на Си, обёрнутая целиком в один-единственный класс - это ещё не С++-программа, и уж тем более не объектное моделирование.

[Circiter]

2EtCetera

Цитата:

RTTI

Ну вы меня слишком буквально поняли. :) Я пытался переформулировать задачу malin'а дабы абстрагироваться от всяких там серо-буро-малиновых деревьев, т.е. подразумевалось узнавание типа в статике, в compile-time. :)

Другими словами, как обобщить такую вещь:

    class MyClass
    {
        ...
        MyClass *Instance;
     };

Ну не препроцессором же такие объявления создавать. Хотя... :)

Я так понял у автора затеи именно чисто спортивный интерес, ему нужно именно наследование и все тут.

[Circiter]

2malin

Цитата:

вспомнил, что указатели на экземпляры базового класса могут указывать на экземпляры производного класса

А, ну да, обычный полиморфизм. Вот только не совсем понятно как создавать такие экземпляры и как ими потом нормально пользоваться (вкрапления приведений типов слишком много шума создаст).

Кстати, а как вы сейчас создаете собственные экземпляры не входя в рекурсию?

[EtCetera]

Circiter

Circiter в сообщении #366359 писал(а):

Ну вы меня слишком буквально поняли. :)

Извиняюсь. Зацепился только за Вашу последнюю фразу и оказался вне контекста.
Прочитал тему с начала. Почему-то вспомнилась комедия Грибоедова (не в обиду ТС ).

Circiter в сообщении #366525 писал(а):

Вот только не совсем понятно как создавать такие экземпляры и как ими потом нормально пользоваться (вкрапления приведений типов слишком много шума создаст).

С созданием, конечно, определенная заминочка будет. Хотя всегда можно определить виртуальную функцию (обозвав ее, например, Create), которая будет возвращать указатель на базовый класс, а на самом деле передавать в этот указатель адрес свежесозданного объекта дочернего класса. А вот приведения типов... А, по-хорошему, где они появятся? Я как-то не соображу...

[Circiter]

2EtCetera

Цитата:

А вот приведения типов... А, по-хорошему, где они появятся? Я как-то не соображу...

Ну допустим, что в производном классе появились новые методы, которых не было в базовом. Чтобы их вызывать придется делать что-то вроде (DerivedClass*)Node->NewMethod().

Это не проблема и такие ситуации будут возникать только в производном классе, но что-то здесь не так. Возможно это как-то гладко обходится, но я тоже сообразить не могу... :)

[Postrelyonysh]

Circiter в сообщении #366627 писал(а):

Ну допустим, что в производном классе появились новые методы, которых не было в базовом. Чтобы их вызывать придется делать что-то вроде (DerivedClass*)Node->NewMethod().

Так делать совершенно недопустимо. Взывания к специфике дочернего класса "извне" напрямую, минуя базовый,- это нарушение принципа абстракции. Подобные проектные решения сильно повышают вероятность того, что новая редакция ТЗ поставит раком весь код и заставит переделывать 99% работы.

Соответственно, и вопросы вроде:

Circiter в сообщении #365924 писал(а):

как в классе узнать свой собственный тип? :) Что-то вроде typeof(*this). :)

- туда же. Здесь явно стоит попытка перейти от потомка к предку, нарушая все причинно-следственные связи в модели предметной области. Сам класс о себе знает, а к своим потомкам он должен обращаться через виртуальные методы.

Скорее всего, задача такова, что ни С++, ни ООП, ни та пародия на ООП, что реализована в С++,- для неё не являются адекватными инструментами - нужна совсем другая мат.модель предметной области.

[Circiter]

2Postrelyonysh

Цитата:

Взывания к специфике дочернего класса "извне" напрямую, минуя базовый,- это нарушение принципа абстракции

Подразумевалось, что такой прием будет использоваться только самим производным классом... Ведь наследование в ООП используется не только чтобы подправить с помощью механизма виртуальных методов функциональность, взятую из базового класса, но и чтобы добавить совершенно новую, т.е. и новые методы и новые поля... Опасности здесь никакой нет (или я её просто не вижу). Иначе говоря, этот сомнительный прием предлагался просто как способ договориться с системой типов.

Более того, это же был аргумент "против", а не "за". :)

Возможно, что я просто вас не понял. Вот например, в некоторых языках не поддерживающих множественное наследование объектные библиотеки используют иерархию с общим суперклассом, что-то вроде TObject'а из object pascal'я. Это же не значит, что работа со всеми классами должны происходить исключительно через средства, предоставляемые TObject'ом.

Цитата:

Скорее всего, задача такова, что ни С++, ни ООП, ни та пародия на ООП, что реализована в С++,- для неё не являются адекватными инструментами

По-сути, у автора темы проблема была с необходимостью переписывания кода. Фактически, это задача для метапрограммирования. В C++ для этих целей служат шаблоны, и я уверен, что если на этом форуме появлялись всякие там Страуструпы, Александреску и прочие, то удовлетворительный ответ был бы давно уже дан, причем в рамках чистого C++'а. :)

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