Графы на C++: иерархия классов

[cupuyc]

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

2kuraga

Цитата:

У нас в учебнике это тоже RTTI

Странно, static_cast<MarkedVertice*>(*i) это (почти) тоже самое, что и (MarkedVertice*)(*i), но безопаснее. Может быть в учебнике просто предупреждали о принципиально возможном run-time оверхеде при преобразовании типов?

Я бы сказал, что (MarkedVertice*)(*i) - C style cast, которого в плюсных прогах вообще быть не должно, но, что поделать, стандарт не запрещает. Так что static_cast - это никакой не RTTI, а стандартный оператор языка C++. RTTI, кстати, насколько мне помнится, к стандарту не относится вообще.

Что касается RTTI - почитайте хотя бы педивикию http://en.wikipedia.org/wiki/Run-time_type_information. Нужно сказать, что информация о классах помещается в бинарник только при использовании динамического преобразования типов. Так что static_cast const_cast reinterpret_cast можно смело использовать. А вот перед тем как использовать dynamic_cast нужно тыщу раз подумать - а нужно ли?

[Circiter]

(cupuyc)

cupuyc писал(а):

Что касается RTTI - почитайте хотя бы педивикию

Надеюсь, это вы не мне советовали, а к топикстартеру обращались (я то некоторые представления имею). :)

[cupuyc]

(Оффтоп)

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

(cupuyc)

cupuyc писал(а):

Что касается RTTI - почитайте хотя бы педивикию

Надеюсь, это вы не мне советовали, а к топикстартеру обращались (я то некоторые представления имею). :)

Да, разумеется.

[kuraga]

Изящно, изящно... Что ж, всегда можно найти то, чего не знаешь, я не прав?

У меня еще используется виртуальное наследование от класса Object (функция получения уникального id объекта), а, насколько я понял, тогда static_cast не применим. Как правильно поступить?

[cupuyc]

kuraga, Во-первых, Вы ошибаетесь. Во-вторых, Вы придумали какую-то жутко кривую архитектуру. Зачем-то наследование от какого-то Object'а.. Никогда этого не понимал - зачем связывать все объекты одним родителем? Это потянет за собой множественное наследование, усложнение архитектуры и пр. На борланде что-ли пишите?

[kuraga]

cupuyc
Лично я - чтобы у всех объектов был уникальный id. А зачем это делают разработчики? И отсутствие этого считается минусом... Для чего делаю Я, я написал.
В чем ошибаюсь? Может, но сделал наследование невиртуальным и заработало.
А про Борланд улыбнуло :) Знаете, под ДОСом писал на Борланде, на Майкрософте компилить прикажите?
P.S. Причем достаточно, чтобы только последнее наследование было невиртуальным. Если я правильно вижу...

[cupuyc]

kuraga в сообщении #424896 писал(а):

Лично я - чтобы у всех объектов был уникальный id. А зачем это делают разработчики? И отсутствие этого считается минусом... Для чего делаю Я, я написал.

Кто делает? Лично я не делаю. И в реальных проектов такого никогда не встречал: зачем объекту уникальный идентификатор во всём множестве созданных объектов? Совершенно непонятно.

kuraga в сообщении #424896 писал(а):

В чем ошибаюсь? Может, но сделал наследование невиртуальным и заработало.А про Борланд улыбнуло :) Знаете, под ДОСом писал на Борланде, на Майкрософте компилить прикажите?P.S. Причем достаточно, чтобы только последнее наследование было невиртуальным. Если я правильно вижу...

Ну, Visual Studio один из лучших компиляторов С++, если судить по качеству генерируемого кода. А вообще, хороший код должен компилиться на чём угодно. Хоть на gcc, хоть на борланде. Так что привязывать свой код к какому-нибудь Object я бы не стал хотя бы потому что это не стандарт. Нужны id-шники - заведите мембер в базовом классе BaseGraph или в BaseVertice.

[Circiter]

2cupuyc

Цитата:

И в реальных проектов такого никогда не встречал: зачем объекту уникальный идентификатор во всём множестве созданных объектов?

Будете смеяться, но такие ситуации действительно возникают; по крайней мере у меня возникала такая необходимость. Но я решил эту проблему очень просто -- в качестве уникального идентификатора объекта сгодился его адрес в памяти! :)

[cupuyc]

Circiter, просто ради интереса - зачем такое понадобилось? Кроме того, Вы говорите несколько о другом. Адрес, вообще говоря, не является глобальным идентификатором объекта. Вот, скажем, есть такой код

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

class A { ... };

void f()
{
  A a;
}

void g()
{
  f();
  f();
} 

В результате будет создано 2 объекта класса A с одним и тем же адресом. Когда же мы говорим о глобальном идентификаторе, то подразумевается, что все созданные ранее и созданные в настоящее время объекты имеют различные идентификаторы.
Мало того, можно придумать такой код, в котором объекты с одинаковыми идентификаторами будут сосуществовать одновременно:

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

class A
{
  int x;
};
class B
{
  A a;
};

void f()
{
  B b;
}
 

В функции создастся объект b класса B. А в нём создастся объект a класса A. Оба эти объекта будут иметь одинаковые адреса.

[worm2]

Я так понимаю, коль скоро в программах появляется такой абстрактный объект, как граф, недалёк тот час, когда потребуются абстрактные алгоритмы на этих самых графах. Которые хочется один раз реализовать для всех графов (и для "обычных", и для "маркированных" и для бог весть ещё каких).
И вот как такую вещь сделать без шаблонов, я плохо представляю.

[cupuyc]

worm2, я бы сказал, что вообще ничего делать не надо. Всё уже сделано давным давно. Сделан уже миллион ошибок и большая часть из них даже исправлена. Стоит ли велосипед изобретать с кривыми колёсами?

[kuraga]

Шо ж вы меня все позорите? Задание у меня такое. И мы не должны задумываться, велосипед ли...

[Circiter]

2cupuyc

Цитата:

Адрес, вообще говоря, не является глобальным идентификатором объекта.

Ну вот, я же говорил "будете смеяться". :) Да, действительно, адрес в качестве uid'а не годится, но это в общем случае. Например, если бы этот хак использовался в серьезном, и тем более коммерческом проекте, то я первый бы придрался к такому трюку. Но программка писалась для себя и была экспериментальной, хотя я ей уже третий год пользуюсь. :)

Почему я тогда поленился и не завел нормальный счетчик, например, просто не подмешав подходящий mixin или не поручив это дело фабрике? Да все просто -- мне нужно было тупо искать объект по идентификатору, но делать это нужно было на критичном по скорости участке. А Type &Lookup(Type *Object) {return *Object;}, очевидно, реализует самый быстрый $\mathcal{O}(1)$ поиск. :)

[OZH]

cupuyc в сообщении #425900 писал(а):

worm2, я бы сказал, что вообще ничего делать не надо. Всё уже сделано давным давно. Сделан уже миллион ошибок и большая часть из них даже исправлена. Стоит ли велосипед изобретать с кривыми колёсами?

И что? Ничего не делать своими руками? А как же познавать? Всегда же интересно придумать что-то самому. Главное придумать, а не что-то новое.

Мне другое интересно. А как предлагается изображать графы? Я понимаю, что об этом уже подумали. Тем не менее.

Было бы, конечно, удобнее, иметь готовый редактор, куда можно закладывать алгоритмы на графах и получать результаты. Тогда это было бы встроено в операционную систему.

-- Ср мар 30, 2011 16:42:45 --

А как это, вообще, должно выглядеть?

СОЗДАТЬ Граф.
ДОБАВИТЬ Вершина(1)
...
ДОБАВИТЬ Вершина(N)
ДОБАВИТЬ Ребро(Вершина1,Вершина2)
...

Или на вход подавать матрицу инцидентности/смежности?

И что потом?

НАЙТИ ОстовГрафа?
НАЙТИ Цикл?
ПЕРЕЧИСЛИТЬ Поддеревья?

[kuraga]

OZH
У меня это выглядит именно так... Просто я еще не особо понимаю, как я буду этим графом пользоваться. Мы будем писать с их помощью интерпретатор :) . В методических указаниях наверняка написано, но нам пока сказано их не читать

P.S. Я реализовал и полиморфную, и шаблонную модели маркированного графа. Пока что вторая удобнее и короче...