Russian Qt Forum

Программирование => Общий => Тема начата: Igors от Декабрь 16, 2018, 10:58



Название: Деревянный айтем
Отправлено: Igors от Декабрь 16, 2018, 10:58
Добрый день

Банальная структурка
Код
C++ (Qt)
struct CTreeItem {
 QString m_name;     // имя
 ...                           // .. еще данные айтема
 QVector<CTreeItem> m_child; // чайлдво
 
 CTreeItem * m_parent;   // ???
};
 
Вот этот m_parent - иметь его хочется, это делает айтем "самодостаточным" для многих операций.  Но получаем проблемы с копированием. Конечно их можно пережить, но нет ли лучшего решения?

Спасибо


Название: Re: Деревянный айтем
Отправлено: ssoft от Декабрь 17, 2018, 07:59
Тама то многажды раз здесь изъезженная))  ???

На пальцах:
У класса есть данные (свойства - Property) и ссылки на другие классы (концы ассоциативных связей - AssociationEnd).
Обычно, данные копируются, а ссылки - нет. Это не всегда так, но опустим эти случаи из рассмотрения.

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

Когда концы ассоциативных связей являются частью класса, имеет смысл разделить его на две функциональные части:
1. Часть для работы с ассоциациями.
2. Часть для работы с данными.

Код
C++ (Qt)
struct Data
{
    // bla bla bla
};
 
class Item
{
   Parent m_parent;      // например, Parent = Item *
   Children m_children; // например, Children = QVector< Item * >
   Data m_data;
 
    // bla bla bla
}
 

Как таковые Item'ы не копируются, а создаются на основе данных другого, с указанием новых ассоциативных связей.


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 17, 2018, 09:47
Тама то многажды раз здесь изъезженная))  ???
Наверное "тема", но все равно - впервые слышу :)

Когда концы ассоциативных связей являются частью класса, имеет смысл разделить его на две функциональные части:
1. Часть для работы с ассоциациями.
2. Часть для работы с данными.

Код
C++ (Qt)
struct Data
{
    // bla bla bla
};
 
class Item
{
   Parent m_parent;      // например, Parent = Item *
   Children m_children; // например, Children = QVector< Item * >
   Data m_data;
 
    // bla bla bla
}
 

Как таковые Item'ы не копируются, а создаются на основе данных другого, с указанием новых ассоциативных связей.
Ну выделять/подчеркивать "ассоциативные связи" - на мой взгляд скорее косметика. А делать-то что, т.е. как организовать копирование? Неплохо хoтя бы так
Код:
void CTreeItem::CopyFrom( const CTreeItem & other, CTreeItem * parent );
Но сделать приватным конструктор/оператор копирования я не могу - сразу же вякнет контейнер m_children. Выходит если m_parent хранится в классе - остается латать каждое копирование руками, типа
Код
C++ (Qt)
*theTargetItem  = *theSourceItem;
theTargetItem->m_parent = newParent;  
 

Ну хорошо, допустим есть "менеджер связей" (кстати необходимость в нем упорно вылазит там и сям). И что? Понятно что для такого простого случае он наверняка будет избыточным, но интересует "в прынцыпе"


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 17, 2018, 12:56
Igors
ssoft говорит вам о том, что мухи - отдельно, котлеты  отдельно.
Отдельно данные, отдельно дерево.
Если надо копировать дерево, то сделайте копирование дерева.
Если надо копировать данные, сделайте копирование данных.
В целом, операция копирования подветки - самостоятельная операция, она же "выделение поддерева". Это нормально, что после копирования ветка будет без родителя (откуда ей, собствнно, знать, что вы хотите с подветкой делать дальше?).
Если уж так не хочется делать две строки
Код:
auto subtree = item->clone(); 
parent->addItem(subtree);
ну сделайе опциональный парметр нового родителя, если уж паттерн такой частый
Код:
auto subtree = item->clone(newParent);

Но я бы шел по пути вумных укзателей и назначал родителя руками, ибо нагляднее:
Код:
std::unique_ptr<Item> subtree = item->clone(); 
parent->addItem(std::move(subtree));

Но это синтаксический сахар и вкусовщина, способ выше с newParent ничем не плох.


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 17, 2018, 12:59
А, ну и самое главное - старое доброе дерево таки лучше реализовывать на указателях, по старинке. Не надо сюда приплетать с++ и копирование просто потому что "ну это же с++". Просто не надо.


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 17, 2018, 13:38
А, ну и самое главное - старое доброе дерево таки лучше реализовывать на указателях, по старинке. Не надо сюда приплетать с++ и копирование просто потому что "ну это же с++". Просто не надо.
Не очень понял что имеется ввиду под "старым добрым". Отказаться от контейнера и добавить члены m_prev/m_next, что ли?

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


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 17, 2018, 13:53
Не очень понял что имеется ввиду под "старым добрым". Отказаться от контейнера и добавить члены m_prev/m_next, что ли?
m_prev/m_next это уже список=)
нет, контейнер как раз норм, только лучше хранить в нем указатели, а не значение. Потому что если вы хотите хранить значение, то возникает вопрос "а как копировать"? И вы сами себе выдумываете проблемы. А никак не копировать. Запретить копирование, оставить разве что мув. Использовать явный метод слон(родитель).

Я знаю что неплох и вообще понимаю что для такого простого случая проще чуть потерпеть чем что-то городить. Но как только я приведу хоть какой-то реальный пример - все моментально свалится в "надо знать задачу". Поэтому будем "тренироваться на кошках" - проблемы в принципе те же, но все макс упрощено
Все сваливается в "надо знать задачу" потому что вам предложишь решение - оно вам не подходит потому что ВНЕЗАПНО появляется новое условие, которого не было в исходной задаче. Учтешь условие, предложишь новое решение - появится новое условие и так до бесконечности.


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 18, 2018, 18:14
Чот быстро заглохло=)


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 19, 2018, 10:28
нет, контейнер как раз норм, только лучше хранить в нем указатели, а не значение. Потому что если вы хотите хранить значение, то возникает вопрос "а как копировать"? И вы сами себе выдумываете проблемы. А никак не копировать. Запретить копирование, оставить разве что мув. Использовать явный метод слон(родитель).
Ну хорошо, попробуем сделать выводы:

- если хотим ссылаться на CTreeItem, то он должен быть неперемещаемым. Поэтому QVector<CTreeItem> (стартовый пост) просто не годится

- если CTreeItem ссылается на кого-то (здесь на др CTreeItem), то придется расстаться с конструктором/оператором копирования и, увы, с дефаулт конструктором. Т.е. все операции требующие установки ссылки должны получать ее явно, как аргумент метода. А если необходимость в копировании все-таки возникает, то обеспечить ее отдельным методом (напр Clone) с аргументом pаrent. Итого
Код
C++ (Qt)
struct CTreeItem {
 CTreeItem( CTreeItem * parent );
 virtual ~CTreeItem( void ) ;    // qDeleteAll(m_child)
 
 CTreeItem * Clone( CTreeItem * parent ) const;
 
// data
 CTreeItem *  m_parent;
 QVector<CTreeItem *>  m_child;
 QString m_name;
 int m_flags;
 ... // more data
 
private:
 CTreeItem( const CTreeItem & );
 CTreeItem & operator = ( const CTreeItem & );
};
Само по себе это вполне норм, но... как резко все изменилось всего лишь из-за одного члена m_parent. Не много ли?

Хорошо, а если все-таки попробовать сделать эту ссылку внешней? Что из этого выйдет?


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 19, 2018, 12:32
Ну хорошо, попробуем сделать выводы:

- если хотим ссылаться на CTreeItem, то он должен быть неперемещаемым. Поэтому QVector<CTreeItem> (стартовый пост) просто не годится
Вывод неверный=)


- если CTreeItem ссылается на кого-то (здесь на др CTreeItem), то придется расстаться с конструктором/оператором копирования
Увы.

и, увы, с дефаулт конструктором.
Не обязательно

Т.е. все операции требующие установки ссылки должны получать ее явно, как аргумент метода. А если необходимость в копировании все-таки возникает, то обеспечить ее отдельным методом (напр Clone) с аргументом pаrent.
Хмммм, нам надо как-то передавать нового парента, блин, как же это сделать, не передавая нового парента?

Итого
Само по себе это вполне норм, но... как резко все изменилось всего лишь из-за одного члена m_parent. Не много ли?

Начнем издалека. Дерево всю жизнь реализовывалось на указателях. Не потому что какие-то ограничения, а потому что симметрия - это красиво, если вы храните указатель на парента то красиво (симметрично) к нему хранить указатели на детей. Удобно, красиво, но не обязательно. Если хотите сделать дерево на value-based классе - вперед, будет домашнее задание=) Можно даже от указателя уйти и хранить std::ref. Удачи правда в обновлении парента у детей при ресайзе вектора, но о5 же, всё в ваших руках=) QList упростит задачу.
То есть, зафиксируем - мы меняем vector<Item> на vector<std::unique_ptr<Item>> просто ради симметрии и удобства (ну и стабильности указателей на парента).
Далее, вы, вероятно, читали опус (https://wiki.qt.io/ValueBasedAndPointerBasedTypes) про value-based классы. Деревянный айтем не может иметь конструктора копирования ровно как не может его иметь виджет или std::thread (что должна делать копия треда? запускать функтор заново? продолжать в том же месте?). Причина очень проста - после "копирования" вы не получите копию. Например, если у айтема есть "пропертя" int row, то она будет отличаться даже если парент остался тот же. В самом деле, не могут же два айтема лежать в одной ячейке вектора? В вашем случае, вы хотите менять парента, что противоречит идее "копирования". Копия должна быть идентична оригиналу. Именно потому, что вы хотите получать "похожий" объект (но не копию!) конутруктор копирования нужно запретить (иначе будет очередной std::auto_ptr с сайд-эффектами). И тут не важно, используете вы value или pointer-based, метод clone() делать придётся (ибо клон похож на оригинал но отличается от него).

Итого, изменений два по двум причинам:
-указатели ибо красота и стабильность парентов
-clone, ибо копия не имеет смысла

На данном этапе есть вопросы?

Хорошо, а если все-таки попробовать сделать эту ссылку внешней? Что из этого выйдет?
Что значит "внешней"?


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 20, 2018, 09:43
Если хотите сделать дерево на value-based классе - вперед, будет домашнее задание=)
Ну такого я сделать не смогу, поэтому, учитель, покажите мне как это делается  :) Спасибо

Ну а если серьезно, то почему бы не ответить просто и без затей, напр:
Цитировать
лучшей возможности чем просто "голый указатель" здесь нет, (мелкие) проблемы с копированием можно решить (тем более что clone != copy). Какие-то альтернативы выглядят безумно сложно "зато" не дающими никаких выгод. Как впрочем и новомодные цацки что вы лепите везде (unique_ptr, std::move и.т.п). Простецкая реализация (в духе С) здесь видимо и является лучшей.

Что значит "внешней"?
А отот "граф" что давеча упоминался. Тогда не нужно хранить m_parent, да и контейнер m_child не нужен, ведь он автоматом хранится в графе.


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 20, 2018, 12:57
Цитировать
Какие-то альтернативы выглядят безумно сложно "зато" не дающими никаких выгод. Как впрочем и новомодные цацки что вы лепите везде (unique_ptr, std::move и.т.п). Простецкая реализация (в духе С) здесь видимо и является лучшей.
Как раз таки все эти новомодные цацки нужны чтобы код был читаемый а не как ваша каша с непонятным владением.
Мув явно говорит - владение передали дереву. метод слон(парент) - плохой, негодный метод. Я лично напишу две строки - выделить поддерево (слон без параметров) и вставить в поддерево в новое место (item->append/item->insert).
юник_птр избавляет от богомерзких qDeleteAll, по это то же самое, что "vector<Item>"
Все ваши проблемы что вы не можете разобраться кто чем владеет.

А отот "граф" что давеча упоминался. Тогда не нужно хранить m_parent, да и контейнер m_child не нужен, ведь он автоматом хранится в графе.

А ничо что граф и дерево - разные структуры, ммм?
Если вам не хватает дерева (хотя судя по всему хватает), ну давайте обсудим, как реализовать граф.
Ну и о5 же каша. У вас есть данные. Данные отдельно. Их можно положить в дерево. Их можно положить в граф. Зависит от того, что надо сделать. Нужны множественные связи к паренту? Юзайте граф. Не нужны - юзайте дерево.
Да, дерево - частный случай графа, но зачем мудрить, если дерева хватает?


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 21, 2018, 12:10
.. а не как ваша каша с непонятным владением.
...
Все ваши проблемы что вы не можете разобраться кто чем владеет.
??? :) Да как же "непонятным" если члены называются "m_parent" и "m_child"? Куда уж понятнее? И что толку здесь от unique_ptr - ведь обращаться к чайлду все равно как-то надо. И зачем затевать котовасию с move если можно просто извлечь указатель из одного контейнера и поместить в другой? (для того и делаем вектор указателей)

Кстати, а кто такой "слон"? Звучит хорошо, выразительно, но я не в курсе что это значит, поясните.

А ничо что граф и дерево - разные структуры, ммм?
Если вам не хватает дерева (хотя судя по всему хватает), ну давайте обсудим, как реализовать граф.
Ну и о5 же каша. У вас есть данные. Данные отдельно. Их можно положить в дерево. Их можно положить в граф. Зависит от того, что надо сделать. Нужны множественные связи к паренту? Юзайте граф. Не нужны - юзайте дерево.
Да, дерево - частный случай графа, но зачем мудрить, если дерева хватает?
Не везде мне его хватает, и таких случаев достаточно много. Тащить контейнеры parent/child в каждый из (нуждающихся в них) классов явно не хочется. Вот обдумываю общий класс/ф-ционал. Использовать его для существующих деревьев - таких планов нет, они и так делают все что надо. А вот для проверки/отработки "концепции" (не побоюсь этого слова) дерево очень даже подходит, на нем все тоже должно работать. Ну пока неясно как должны выглядеть базовые операции удаления/копирования/IO. Да и вообще какие планы строить, напр можно ограничиться простой задачей "найти (или уметь находить) ссылающихся", или же размахнуться поширше...


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 21, 2018, 12:29
??? :) Да как же "непонятным" если члены называются "m_parent" и "m_child"? Куда уж понятнее? И что толку здесь от unique_ptr - ведь обращаться к чайлду все равно как-то надо. И зачем затевать котовасию с move если можно просто извлечь указатель из одного контейнера и поместить в другой? (для того и делаем вектор указателей)
КОТоВасия с мувом нужна для того, чтобы было видно, кто кем владеет. В вашем исходном примере с value-based таки каша. С одной стороны, айтем владеет детьми. С другой, корневой айтем "сам по себе", но не совсем - им владеет тот, кто его хранит. При этом все айтемы могут ссылаться на парентов. Вот мы копируем айтем это что же, у всех детей надо паренты менять?

Зайдем с другой стороны.
Вот есть сишный код
Код:
TreeItem *item = getItem();
Это дерево? Или одиночный элемент дерева? Могу я удалить айтем? С одной стороны, QObject учит что можно. С другой, не посмотрев в код айтема (ну что там автор намудрил) не разберешься.

А теперь следите за руками
Код:
std::unique_ptr<TreeItem> tree = getTree();
ВНЕЗАПНО, unique_ptr на айтем становится самотоятельным объектом ДЕРЕВА а не отдельным элементом (айтемом)
Код:
ObserverPointer<TreeItem> node = getNode();
ВНЕЗАПНО, ObserverPointer на айтем становится элементом дерева, а не деревом! Типа псевдо-"итератор".

Где же магия? Как же так вышло, мы заюзали какую-то "вумность" и внезапно образовались абстракции - и сущность "дерево" появилась и "элемент дерева".

Кстати, а кто такой "слон"? Звучит хорошо, выразительно, но я не в курсе что это значит, поясните.
clone - слоне, слон.

Не везде мне его хватает, и таких случаев достаточно много. Тащить контейнеры parent/child в каждый из (нуждающихся в них) классов явно не хочется. Вот обдумываю общий класс/ф-ционал.
Ну сделайте шаблонное и\или виртуальное дерево, в чем проблема? Ах, проблема в том, что элемент дерева и дата у вас в голове - одно и то же и представлелы одним классом.

Использовать его для существующих деревьев - таких планов нет, они и так делают все что надо. А вот для проверки/отработки "концепции" (не побоюсь этого слова) дерево очень даже подходит, на нем все тоже должно работать. Ну пока неясно как должны выглядеть базовые операции удаления/копирования/IO. Да и вообще какие планы строить, напр можно ограничиться простой задачей "найти (или уметь находить) ссылающихся", или же размахнуться поширше...
Тогда зачем создавать тему про дерево, если вы хотите реализовать граф?? ВНЕЗАПНО у вас задача меняется.


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 21, 2018, 16:11
А теперь следите за руками
Код:
std::unique_ptr<TreeItem> tree = getTree();
ВНЕЗАПНО, unique_ptr на айтем становится самотоятельным объектом ДЕРЕВА а не отдельным элементом (айтемом)
Код:
ObserverPointer<TreeItem> node = getNode();
ВНЕЗАПНО, ObserverPointer на айтем становится элементом дерева, а не деревом! Типа псевдо-"итератор".

Где же магия? Как же так вышло, мы заюзали какую-то "вумность" и внезапно образовались абстракции - и сущность "дерево" появилась и "элемент дерева".
Вот для членов класса подчеркнуть (дать понять) владение - дело хорошее. Но для всего-всего - думается перегиб. Для возвращаемого значения смысл  может быть довольно расплывчатым. Напр в первом случае (возврат unique_ptr) вроде бы утверждается что слон уничтожится при выходе из области видимости - но вполне вероятно мы захотим передать его вызывающему. Во втором вроде бы "нет-нет, только наблюдать!" - но мы можем его и просто грохнуть.

Ну и мы уже знаем что "утверждать сущности" легко и приятно, а вот поиметь с них важный ф-ционал - не очень :) А на одних утверждениях далеко не уехать.

Тогда зачем создавать тему про дерево, если вы хотите реализовать граф?? ВНЕЗАПНО у вас задача меняется.
Что меняется-то? Разве были какие-то ограничения на способ хранения parent/child ? Это читателю букваря/std необходимо чтобы все укладывалось в прочитанные рамки, а если нет - все, "плохая задача!!". Зачем Вы повторяете эти глупости?  :'(




Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 21, 2018, 17:23
Вот для членов класса подчеркнуть (дать понять) владение - дело хорошее. Но для всего-всего - думается перегиб. Для возвращаемого значения смысл  может быть довольно расплывчатым. Напр в первом случае (возврат unique_ptr) вроде бы утверждается что слон уничтожится при выходе из области видимости - но вполне вероятно мы захотим передать его вызывающему. Во втором вроде бы "нет-нет, только наблюдать!" - но мы можем его и просто грохнуть.

Вообще-то unique_ptr на то и unique что он НЕ scoped_ptr и его можно (и нужно) передавать вызывающему:
Код:
std_unique_ptr<TreeItem> subTree = item->clone();
parent->addChild(std::move(subTree)); // всё, теперь subTree стало дитем парента
Да, это не для "эстетов", которым лучше бы написать одну строчку, покороче, но зато с десятком сайдэффектов.
Впрочем, для эстетов тоже можно:
Код:
auto item = parent->addChild(item->clone()); // всё, теперь subTree стало дитем парента

Это почти ничем не отличается от
Код:
auto item = item->clone(parent);

Тогда зачем создавать тему про дерево, если вы хотите реализовать граф?? ВНЕЗАПНО у вас задача меняется.
Что меняется-то? Разве были какие-то ограничения на способ хранения parent/child ? Это читателю букваря/std необходимо чтобы все укладывалось в прочитанные рамки, а если нет - все, "плохая задача!!". Зачем Вы повторяете эти глупости?  :'(
[/quote]

Ну давайте теперь прот граф поговорим. Итак, графы бывают направленные, ненаправленные. Ребра графа бываю взвешенные и невзвешенные (или как они там называются, крч, когда есть веса и когда нет весов). Вам каких отсыпать?
Далее, есть разные реализации. Можно "на айтемах" (видимо, вы это подразумеваете) - каждая нода хранит ссылки на соседние ноды. Эта структура сложнее, чем дерево, так как из-за циклических ссылок нодами владеть должен объект графа, а не сама нода - придется делать обертку, в ней хранить "хардлинки" на вершины (ака юник_птр).
А не хотите граф на матрицах или списках? Например, невзвешенный неориентированный граф очень красиво делается через вектор булок (ака QBitArray) - делаем "матрицу" N*N где N - кол-во вершин, в ячейке i,j булка говорящая о том, есть ли такое ребро. Этот граф оч хорошо жмется по памяти - в 1м байте хранятся аж 8 ребер.
В случае, если есть веса, булкой не обойтись - придется хранить вес. Размер матрицы увеличиваетсяв 8-16-32-64 раза (в зависимости от размерности весов).
У обоих матричных решений есть минус - если ребер мало, а вершин много, то много места пропадает на хранение false (или нулей).
Это можно решить "списками" - хранить массив вершин а в нем список (или другой массив) вершин, до которых можно дойти напрямую. Тут сложнее удаление ребер, кроме того, больше аллокаций (и, возможно, менее кэш-френдли).

Чуете, да? "Универсальный" граф вы не напишите - если надо искать путь в графе, то вам подойдет одно решение, если надо проверять наличие ребра, то другое.


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 23, 2018, 10:46
Вообще-то unique_ptr на то и unique что он НЕ scoped_ptr и его можно (и нужно) передавать вызывающему:
Код:
std_unique_ptr<TreeItem> subTree = item->clone();
parent->addChild(std::move(subTree)); // всё, теперь subTree стало дитем парента
Да, это не для "эстетов", которым лучше бы написать одну строчку, покороче, но зато с десятком сайдэффектов.
Впрочем, для эстетов тоже можно:
Код:
auto item = parent->addChild(item->clone()); // всё, теперь subTree стало дитем парента
Не суть конечно, но первый вариант мне кажется искусственным. Надо уповать что TreeItem имеет конструктор перемещения (а он все-таки не бесплатный). В то же время прототип addChild ясно показывает что аргумент - указатель, стало быть вызывающий отвечает за его создание, а парент "takes ownership", др вариантов не видно. Также имя "clone" ясно показывает что это созданная копия. И чего было калечить простой и совершенно нормальный код?  :)


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 23, 2018, 11:20
Ну давайте теперь прот граф поговорим. Итак, графы бывают ..
Меня удивляет что ситуация которая у меня встречается на каждом шагу, для Вас выглядит совершенно незнакомой. Ну хорошо, рассмотрим пример из моей практики

Два 3D объекта (A и B) могут быть связаны разнообразными "constraint(s)". Это значит что какие-то трансформы объекта A (обычно позиция и поворот) вычисляются автоматычно на основании взаимного положения A и B. Напр задан "AutoLook" constraint, значит A должен "смотреть на B", т.е. автоматычно поворачиваться к нему лицом (ось Z направлена на центр B). Напр юзер передвинул B, и А повернулся к нему.

Это "отношение" не уникально. Объект A может иметь сколько угодно других constraint напр с объектами C и D и даже с тем же B, и тип может быть тем же AutoLook. Хотя практически число связей редко превышает 2-3. Отношение имеет параметры, часто "вес" чтобы комбинироваться с другими. Объект A может быть парентом B или его чайлдом, могут быть и любые другие отношения между теми же A и B.

Можно решать это в лоб - хранить в A указатель на B и наоборот. Точнее вектора указателей, т.к. связей может быть > 1. Ну дальше надо по меньшей мере разрывать эти связи при удалении A или B. Также consraint - всего лишь один из возможных связей.

Предложите общую конструкцию которая здесь (давно) назрела


 


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 23, 2018, 12:13
В то же время прототип addChild ясно показывает что аргумент - указатель, стало быть вызывающий отвечает за его создание, а парент "takes ownership", др вариантов не видно. Также имя "clone" ясно показывает что это созданная копия. И чего было калечить простой и совершенно нормальный код?  :)

Т.е. Вы по имени функции можете определить, берёт она владение или нет :). Хорошо, какой из следующих методов забирает владение объектом, а какой нет:

1. void QTreeWidgetItem::addChild(QTreeWidgetItem *child)
2. void QTreeWidgetItem::insertChild(int index, QTreeWidgetItem *child)
3. void QWidget::addAction(QAction *action)
4. void QWidget::insertAction(QAction *before, QAction *action)
5. void Car::addWheel(Wheel *wheel)
6. void Car::addKey(Key *key)


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 23, 2018, 12:23
Т.е. Вы по имени функции можете определить, берёт она владение или нет :).
В общем случае - нет, в конкретном случае выше - да. Как-то Вы зациклились исключительно на "владении" как будто других дел нет  :)


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 23, 2018, 12:35
В общем случае - нет, в конкретном случае выше - да. Как-то Вы зациклились исключительно на "владении" как будто других дел нет  :)

В том-то и дело, что других дел полно. Вы хотите дополнительно к ним ещё тратить время на розыскную деятельность по поводу владения? Я - нет :). Умные указатели и семантика move в этом и помогают.


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 23, 2018, 17:39
Меня удивляет что ситуация которая у меня встречается на каждом шагу, для Вас выглядит совершенно незнакомой. Ну хорошо, рассмотрим пример из моей практики
 

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


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 24, 2018, 12:24
Если бы все вокруг решали вашу задачу..
Программист без предметной части - просто ноль без палочки. Если он не умеет даже повернуть объект, то любые познания в итераторах, мувах и прочей лабуде уже не имеют никакой ценности. О них лучше даже не упоминать, это вызовет нездоровый смех.

Более того, не просили ничего поворачивать, нужно разработать структуру данных, т.е. работа чисто программистская, такая задача может возникнуть в любой предметной области. Подробности приводились просто для примера т.к. любая абстракция где-то применяется - иначе нафиг она нужна. А Вы сразу "лапки кверху", мол, "ваша задача, я таким не занимаюсь". Это конечно Ваше право, но такой подход совершенно бесперспективен. "Заказывать музыку" (и получать бабульки) будет тот кто залезет на предметную часть. И можно долго охать и ахать как примитивен его код, но это ничего не изменит. А кто предметной частью заниматься не хочет - получает огрызки (хорошо еще UI). Так было и будет, "чистого программирования" в природе не существует.

Я достаточно часто меняю конторы
Я догадываюсь почему


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 24, 2018, 13:14
Более того, не просили ничего поворачивать, нужно разработать структуру данных, т.е. работа чисто программистская, такая задача может возникнуть в любой предметной области. Подробности приводились просто для примера т.к. любая абстракция где-то применяется - иначе нафиг она нужна. А Вы сразу "лапки кверху", мол, "ваша задача, я таким не занимаюсь". Это конечно Ваше право, но такой подход совершенно бесперспективен. "Заказывать музыку" (и получать бабульки) будет тот кто залезет на предметную часть. И можно долго охать и ахать как примитивен его код, но это ничего не изменит. А кто предметной частью заниматься не хочет - получает огрызки (хорошо еще UI). Так было и будет, "чистого программирования" в природе не существует.

Ставки повышаются :).

Два 3D объекта (A и B) могут быть связаны разнообразными "constraint(s)". Это значит что какие-то трансформы объекта A (обычно позиция и поворот) вычисляются автоматычно на основании взаимного положения A и B. Напр задан "AutoLook" constraint, значит A должен "смотреть на B", т.е. автоматычно поворачиваться к нему лицом (ось Z направлена на центр B). Напр юзер передвинул B, и А повернулся к нему.

Это "отношение" не уникально. Объект A может иметь сколько угодно других constraint напр с объектами C и D и даже с тем же B, и тип может быть тем же AutoLook. Хотя практически число связей редко превышает 2-3. Отношение имеет параметры, часто "вес" чтобы комбинироваться с другими. Объект A может быть парентом B или его чайлдом, могут быть и любые другие отношения между теми же A и B.

Можно решать это в лоб - хранить в A указатель на B и наоборот. Точнее вектора указателей, т.к. связей может быть > 1. Ну дальше надо по меньшей мере разрывать эти связи при удалении A или B. Также consraint - всего лишь один из возможных связей.

Мне одному кажется, что уже в первом предложении было описано решение? :)


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 24, 2018, 14:46
Программист без предметной части - просто ноль без палочки. Если он не умеет даже повернуть объект, то любые познания в итераторах, мувах и прочей лабуде уже не имеют никакой ценности. О них лучше даже не упоминать, это вызовет нездоровый смех.
Прикиньте, да, далеко не все работают с 3д графикой. Более скажу - я никогда не работал с 3д графикой. У меня никогда не было задачи "повернуть объект". Серьезно, пока вы перемножали матрицы поворота, я решал другие задачи. Совершенно другие.
И пусть вас не смущают мои вопросы в разделе 3д графики, это для самообразования.

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

такая задача может возникнуть в любой предметной области.
Какая "такая"? Граф? Дайте подумать... Итак, поиск пути (игры?), обход соседних вершин графа (ваш случай?). Что еще? Вот у меня приложение рисует лог данных в таблице, даже не знаю, куда бы граф прикрутить?

Подробности приводились просто для примера т.к. любая абстракция где-то применяется - иначе нафиг она нужна. А Вы сразу "лапки кверху", мол, "ваша задача, я таким не занимаюсь". Это конечно Ваше право, но такой подход совершенно бесперспективен. "Заказывать музыку" (и получать бабульки) будет тот кто залезет на предметную часть. И можно долго охать и ахать как примитивен его код, но это ничего не изменит. А кто предметной частью заниматься не хочет - получает огрызки (хорошо еще UI). Так было и будет, "чистого программирования" в природе не существует.
Я вообще-то вам тоже самое и сказал. Привел пяток реализаций графа и спросил - вам какой? Вы не ответили. Даже не заметили судя по всему, так как уперлись в свою реализацию на указателях.

Я догадываюсь почему
[/quote]
Так больше зарабатываешь. А вы думали почему?


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 25, 2018, 10:54
Прикиньте, да, далеко не все работают с 3д графикой.
Что такое "графика" - не знаю, но до 3d там еще далеко, это простая математика в рамках общей культуры инженера

Привел пяток реализаций графа и спросил - вам какой? Вы не ответили. Даже не заметили судя по всему,
Что отвечать-то если Вы начали молотить не в тему?
Ну давайте теперь прот граф поговорим
...
Чуете, да? "Универсальный" граф вы не напишите - если надо искать путь в графе, то вам подойдет одно решение, если надо проверять наличие ребра, то другое.
Задача та же самая (деревянный айтем), никак она не менялась - ни внезапно ни постепенно. Цель - построить структуру для доступа к данным, парент знает своих чайлдов и наоборот. Традиционно это делается членами класса. А в общем случае это граф. Напрашивается напр такое
Код
C++ (Qt)
struct  CTreeItem : public CGraphNode {
 CTreeItem( CTreeItem * parent );
 virtual ~CTreeItem( CTreeItem * parent );
 
// обертки базовых вызовов CGraphNode
 CTreeItem * GetParent( void );
 int GetChildCount( void );
 CTreeItem * GetChild( int index );
 ...
// data
 QString m_name;
 int m_flags;
 ...
};
 
Теперь базовый класс возьмет на себя заботу о хранении парента и чайлдва. Как он должен выглядеть? Попробуем пойти по пути наименьшего сопротивления
Код
C++ (Qt)
struct CGraphNode {
// data
 QVector<CGraphNode *> mArcInp;  // входные ребра (чайлды CTreeItem)
 QVector<CGraphNode *> mArcOut;  // выходные ребра (парент CTreeItem)
};
Реализовать это не составляет труда. НО мы взялись делать "в общем виде", стало быть должны хранить всякие-разные зависимости (не только деревянные). По этой же причине "матрица графа" не катит.  Возможно будет создано еще ребро(а) никак не связанные с деревом (см пример с consraints). Как тогда мы будем искать парент/чайлд для нашего айтема?

Как видите тут есть о чем поговорить - было бы желание


Название: Re: Деревянный айтем
Отправлено: Авварон от Декабрь 25, 2018, 12:43
Еще раз - вам надо несколько графов.
Для простоты - у вас есть графиксцена (дерево). Это дерево управляет временем жизни. И только временем жизни!
Возможно, нужно не дерево (ибо зачем?), а тупой массив.
Теперь мы хотим сделать чтобы айтем А бы "связан" с айтемом Б (допустим, "смотрел" на него). Делаем граф "связей" в котором одно ребро - из А в Б. Это граф отвечает только за "направление" (но так как айтем не может смотреть больше чем на 1 другой айтем то тут тоже достаточно (внезапно!) массива)

ЗЫ: нафига вам писать, если вы не читаете что вам пишут?


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 25, 2018, 14:30
Еще раз - вам надо несколько графов.
Для простоты - у вас есть графиксцена (дерево). Это дерево управляет временем жизни. И только временем жизни!
Здесь не идет речь ни о каком "управлении" или "владении". Мне нужна структура данных для хранения связей которые могут быть очень разнообразны. Необходимость управлять, шарить, проверять на цикличность и.т.п. возможна, но вот это как раз та самая "другая задача".

(но так как айтем не может смотреть больше чем на 1 другой айтем то тут тоже достаточно (внезапно!) массива)

ЗЫ: нафига вам писать, если вы не читаете что вам пишут?
А Вы читаете? :) Выше я писал что объект может быть повернут лицом к N др объектов которые даже могут повторяться, и это дает разумные рез-ты.


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 25, 2018, 15:25
Мне нужна структура данных для хранения связей которые могут быть очень разнообразны.

Вы все объекты хотите в одно дерево/граф засунуть? Ну получится граф из void */std::any/BaseObject, сильно это Вам поможет?

Два 3D объекта (A и B) могут быть связаны разнообразными "constraint(s)".

Есть Object3D (A и B) и Сonstraint, который связывает A и B(C, D и т.п.). Т.е. в Сonstraint есть поля типа Object3D (какого-то "ссылочного" типа). При изменении свойств А или В, это Сonstraint что-то пересчитывает и перемещает объекты. В такой постановке задачи нужны ли ссылки на Сonstraint в Object3D? На мой взгляд особо не нужны. При чём тут тогда дерево/граф и "Можно решать это в лоб - хранить в A указатель на B и наоборот."? И нужно ли объекты типов Object3D и Сonstraint пихать в одно дерево? Что у них общего?

Мы тут ещё немного попереписываемся, но, скорей всего, в конечном итоге всё вернётся на круги своя (http://www.prog.org.ru/index.php?topic=31554.msg233512#msg233512) :). С таким же результатом.


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 26, 2018, 12:00
Есть Object3D (A и B) и Сonstraint, который связывает A и B(C, D и т.п.). Т.е. в Сonstraint есть поля типа Object3D (какого-то "ссылочного" типа). При изменении свойств А или В, это Сonstraint что-то пересчитывает и перемещает объекты. В такой постановке задачи нужны ли ссылки на Сonstraint в Object3D? На мой взгляд особо не нужны. При чём тут тогда дерево/граф и "Можно решать это в лоб - хранить в A указатель на B и наоборот."?
Если "ничего не нужно" и " все ни при чем" - то как тогда пересчитывать-то? Да, мы можем хранить указатели на объекты в экземпляре AutoLook - но как к нему достучаться если юзер двигает A и/или B ? И как удалить AutoLook  если удаляется A или B? И.т.п.

И нужно ли объекты типов Object3D и Сonstraint пихать в одно дерево? Что у них общего?
Сonstraint сам по себе - не 3D объект, а действие между парой таких объектов. Пихать сам экземпляр AutoLook в дерево - пока об этом разговора не было, но это не лишено смысла. Почему бы не хранить не только "факт связи" между A и B но и параметры этой связи (в данном случае указатель на AutiLook)?

Мы тут ещё немного попереписываемся, но, скорей всего, в конечном итоге всё вернётся на круги своя (http://www.prog.org.ru/index.php?topic=31554.msg233512#msg233512) :). С таким же результатом.
Ну это я тоже знаю :) Потом неожиданно выяснится что Вы "что-то предлагали", а я никак не смогу вспомнить а что же?  :)


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 26, 2018, 13:10
Ну это я тоже знаю :) Потом неожиданно выяснится что Вы "что-то предлагали", а я никак не смогу вспомнить а что же?  :)

Я предлагал использовать объектно-ориентированный подход, вместо такого "Си с классами":

Цель - построить структуру для доступа к данным, парент знает своих чайлдов и наоборот. Традиционно это делается членами класса. А в общем случае это граф. Напрашивается напр такое
Код
C++ (Qt)
struct  CTreeItem : public CGraphNode {
 CTreeItem( CTreeItem * parent );
 virtual ~CTreeItem( CTreeItem * parent );
 
 CTreeItem * GetParent( void );
 int GetChildCount( void );
 CTreeItem * GetChild( int index );
 ...
// data
 QString m_name;
 int m_flags;
 ...
};
 
Теперь базовый класс возьмет на себя заботу о хранении парента и чайлдва. Как он должен выглядеть? Попробуем пойти по пути наименьшего сопротивления
Код
C++ (Qt)
struct CGraphNode {
// data
 QVector<CGraphNode *> mArcInp;
 QVector<CGraphNode *> mArcOut;
};
Реализовать это не составляет труда. НО мы взялись делать "в общем виде", стало быть должны хранить всякие-разные зависимости (не только деревянные). По этой же причине "матрица графа" не катит.  Возможно будет создано еще ребро(а) никак не связанные с деревом (см пример с consraints). Как тогда мы будем искать парент/чайлд для нашего айтема?

Но закончится это опять вот так (http://www.prog.org.ru/index.php?topic=31554.msg233668#msg233668). Так что можно этот этап оптимизировать и не ходить кругами :).


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 26, 2018, 13:35
Я предлагал использовать объектно-ориентированный подход,
Ну вот опять Вы как-то "предлагали" так что никаких концов не найти  :)

...вместо такого "Си с классами":
Вы бегло глянули псевдокод и не увидели в нем никакой красивой "семантики". Ни std::forward ни даже std::move! А значит это просто "С с классами", и хорошим этот код быть не может! Увы, такой подход сейчас весьма популярен. Это называется добрым старым словом "пижон"  :)


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 26, 2018, 13:50
Ну вот опять Вы как-то "предлагали" так что никаких концов не найти  :)

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

Вы бегло глянули псевдокод и не увидели в нем никакой красивой "семантики". Ни std::forward ни даже std::move! А значит это просто "С с классами", и хорошим этот код быть не может! Увы, такой подход сейчас весьма популярен. Это называется добрым старым словом "пижон"  :)

Интерфейсов я там не увидел. Разделения функциональности не увидел. Зато увидел, как всё в одну кучу валится. Нравится Вам такой подход - на здоровье :).


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 26, 2018, 15:35
В прошлый раз я пытался детально разжевать, толку от этого было ноль. Зачем мне сейчас такой же безумный подвиг совершать :).
Ну давайте посмотрим что было "в прошлый раз"

В своём примере я не рассматривал методы типа AddKey, DelNthKey и им подобные потому что полагаю, что им не место в том классе, который сейчас называется Curve. На мой взгляд, единственная значимая функциональность "кривой" Curve, которая мелькала в теме - это метод "InterpolateValue( double t )". На основании этого предполагаю, что эта "кривая" нужна для генерации "точки кривой" в заданный момент времени (множества точек в заданный интервал времени с заданным шагом). С этой точки зрения, это уже не кривая, а "генератор" "кривых"/"точек кривых". Как и на основе чего он будет генерировать эти точки - глубоко его личные проблемы и пользователей этого генератора особо волновать не должно. В контексте данной темы получается, что "точки кривой" генерируются на основе "ключевых точек" по заданному правилу (типу сплайна). Опять же, если смотреть с точки зрения функциональной значимости, то есть "интерполятор", который генерирует/интерполирует "точки кривой" в окрестностях "ключевых точек"/"сегменте"/"сегментах". При этом получается, что одна из реализаций "генератора" состоит из набора "интерполяторов".

Далее следует резонный вопрос: и как создавать/изменять все эти "генераторы", "интерполяторы", и самое главное, как туда ключевые точки с параметрами сплайна пихать, особенно если они разного типа могут быть? Это требуется в run-time, поэтому: интерфейс/базовый класс -> реализация и свитч или dynamic_cast до значимого интерфейса/реализации.

Вот эти Curve, о которых в теме говорили, в вашей программе как создаются, заполняются значениями и изменяются? Всё вручную в коде жёстко забито? Или загружаются/сохраняются в файлах, а для редактирования используются какие-то GUI редакторы?
Ну при всем желании никаких конкретных "предложений" я здесь как не видел так и не вижу. Есть какой-то (весьма субъективный, скажем так) взгляд на архитектуру классов, а главное - неуемное (и столь же неуместное) желание разрывать все больше и больше подробностей большого проекта (совершенно гиблый путь).

Впрочем Вы не одиноки. "Привел с пяток реализаций.." недавно звучало. А дальше начинает работать шаблон (или template, не к ночи будь помянут)
Цитировать
Вам сразу ответили..
Ему что ни предложи - все плохо!
Да он просто троллит благосклонно ответивших! (да-да, было и такое)
и.т.п.
Зачем? :) Ведь Вы же прекрасно понимаете что по существу НИЧЕГО предложено-то не было. Я же никого не обвиняю что мне "не дали правельный ответ", и в свои темы никого на аркане не тяну. Поэтому не надо строить из себя "благодетеля", а из меня "неблагодарную свинью". Это не совсем так  :)


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 26, 2018, 16:36
Ведь Вы же прекрасно понимаете что по существу НИЧЕГО предложено-то не было. Я же никого не обвиняю что мне "не дали правельный ответ", и в свои темы никого на аркане не тяну. Поэтому не надо строить из себя "благодетеля", а из меня "неблагодарную свинью". Это не совсем так  :)

А какой "правельный ответ" по существу Вы хотите получить с такой постановкой задачи:
Банальная структурка
Код
C++ (Qt)
struct CTreeItem {
 QString m_name;
 ...
 QVector<CTreeItem> m_child;
 
 CTreeItem * m_parent;
};
 
Вот этот m_parent - иметь его хочется, это делает айтем "самодостаточным" для многих операций.  Но получаем проблемы с копированием. Конечно их можно пережить, но нет ли лучшего решения?

потом что-то про графы, потом вообще трансформируется в:

Два 3D объекта (A и B) могут быть связаны разнообразными "constraint(s)". Это значит что какие-то трансформы объекта A (обычно позиция и поворот) вычисляются автоматычно на основании взаимного положения A и B. Напр задан "AutoLook" constraint, значит A должен "смотреть на B", т.е. автоматычно поворачиваться к нему лицом (ось Z направлена на центр B). Напр юзер передвинул B, и А повернулся к нему.

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

В общем: какой вопрос, такой и ответ :).


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 27, 2018, 10:48
А какой "правельный ответ" по существу Вы хотите получить с такой постановкой задачи:
Прекрасная постановка. В общем случае есть некоторое "отношение" между объектами, причем очень разных классов. Это может сопровождаться "владением" но совершенно необязательно. Часто это отношение выражается очень стандартными структурами данных (стартовый пост), но часто и нет (пример с constraint). Вот что делать когда таких отношений/связок становится достаточно много? (как у меня). Есть ли смысл это обобщить? Я думаю что да, тогда как? Мне кажется это интересным и достойным обсуждения.

Вам так не кажется? Это Ваше право, и Вы даже можете сказать "да это все фигня!". Хорошо, но не надо повторять это раз за разом, все уже поняли  :)

Или ждёте, когда Вам на блюдечке с голубой каёмочкой преподнесут код,
Чужой код = то чего надо избегать (а не иметь). Интересно думали ли люди об этом, не исключено что есть и что-то стандартное (какие-то намеки есть в дусте), ведь задача очень общая.

Ну пока дубль-пусто  :)


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 27, 2018, 12:01
Прекрасная постановка.

Ну да, прекрасная :). Давайте ещё раз. Было:

Банальная структурка
Код
C++ (Qt)
struct CTreeItem {
 QString m_name;
 ...
 QVector<CTreeItem> m_child;
 
 CTreeItem * m_parent;
};
 
Вот этот m_parent - иметь его хочется, это делает айтем "самодостаточным" для многих операций.  Но получаем проблемы с копированием. Конечно их можно пережить, но нет ли лучшего решения?
стало:
В общем случае есть некоторое "отношение" между объектами, причем очень разных классов. Это может сопровождаться "владением" но совершенно необязательно. Часто это отношение выражается очень стандартными структурами данных (стартовый пост), но часто и нет (пример с constraint). Вот что делать когда таких отношений/связок становится достаточно много? (как у меня). Есть ли смысл это обобщить? Я думаю что да, тогда как? Мне кажется это интересным и достойным обсуждения.

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

Чужой код = то чего надо избегать (а не иметь).

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


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 27, 2018, 12:24
Кто сможет из "было" вывести "стало", тот, похоже, Вам и поможет, т.к. будет на одной волне :). Я не из их числа, телепатические способности у меня так сильно не развиты.
Ну думать о более общем решении программисту приходится частенько, и телепатия здесь ни при чем. Ну если конечно он программист, а не так, "читатель std"

Зачем на форуме что-то спрашивать, если всё равно к этому не прислушиваетесь?
Да к чему "этому"-то? Вы же, пардон, пургу несете  :)

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


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 27, 2018, 12:42
Да к чему "этому"-то? Вы же, пардон, пургу несете  :)
...
Да Вы ни одной структуры/класса еще не нарисовали, а уже бегаете с владением и интерфейсами :)

В этой теме и другие Вам отвечали, не только я. ssoft в своём первом ответе структуры нарисовал, потом Авварон разжевал так, что подробней уже некуда. Зачем мне повторять их? Сколько людей должны Вам что-то объяснять, чтоб Вы это начали воспринимать? 2, 3, 5, 10? :)


Название: Re: Деревянный айтем
Отправлено: Igors от Декабрь 28, 2018, 10:49
Сколько людей должны Вам что-то объяснять, чтоб Вы это начали воспринимать?
Ой-ей-ей!  :) Скажите еще
Цитировать
Я свое время тратил !!!
А потом (с обидой в голосе)
Цитировать
А ты этого не ценишь  :'(

Вот давеча там чего-то было про r/lvalue, std::forward и.т.п. Я же не лезу к людям типа "мужики, кончали бы вы херней заниматься!" (хотя я так и думаю, но оставлю свое мнение при себе). И уж тем более не пытаюсь закрыть кому-то рот типа "Вам уже все объяснили, сколько можно..". Пожалуйста и Вы ведите себя цивильно - не поняли тему или она Вам просто не по вкусу - не лезьте, не липните как банный лист, это просто  "не Ваше", вот и все. Спасибо за понимание


Название: Re: Деревянный айтем
Отправлено: ViTech от Декабрь 28, 2018, 12:02
Ой-ей-ей!  :) Скажите еще
Цитировать
Я свое время тратил !!!
А потом (с обидой в голосе)
Цитировать
А ты этого не ценишь  :'(

Ого, уже фантазии пошли с моим участием. Что-то мне не по себе становится... :) Лучше направьте своё воображение в другое русло.

Пожалуйста и Вы ведите себя цивильно - не поняли тему или она Вам просто не по вкусу - не лезьте, не липните как банный лист, это просто  "не Ваше", вот и все. Спасибо за понимание

Вы в очередной раз вывели меня на чистую воду. Тема же не про "хухры-мухры", а про цельный деревянный айтем! Чтоб работать с такой предметной областью нужна учёная степень не ниже докторской. Куда мне это понять... На том и порешим :).


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 04, 2019, 07:38
Код
C++ (Qt)
struct CGraphNode {
// data
 QVector<CGraphNode *> mArcInp;  // входные ребра (чайлды CTreeItem)
 QVector<CGraphNode *> mArcOut;  // выходные ребра (парент CTreeItem)
};
Реализовать это не составляет труда. НО мы взялись делать "в общем виде", стало быть должны хранить всякие-разные зависимости (не только деревянные). По этой же причине "матрица графа" не катит.  Возможно будет создано еще ребро(а) никак не связанные с деревом (см пример с consraints). Как тогда мы будем искать парент/чайлд для нашего айтема?
Ну если зависимости "не уникальны" (а всякие-разные), то очевидно нужно их как-то идентифицировать, напр
Код
C++ (Qt)
// (Q)Pair не подходит, второй ключ не нужен
struct CGraphArc {
 ...
 bool operatpr < ( const CGraphArc & other ) const { return m_type  < other.m_type; }
 
// data
 TArcType m_type;
 CGraphNode * m_node;
};
 
struct CGraphNode {
// примеры геттеров
 CGraphNode * GetInpNode( TArcType type, int index = 0 ) const;  // возвращает чайлда
 CGraphNode * GetOutNode( TArcType type, int index = 0 ) const;  // возвращает парента
 
// data
 QVector<CGraphArc> m_ArcInp;  // входные ребра (чайлды CTreeItem)
 QVector<CGraphArc> m_ArcOut;  // выходные ребра (парент CTreeItem)
};
 
Думаю ассоциативные контейнеры (вместо векторов) здесь будет жирновато, да и вставляют они не так как надо, поэтому храним сортированные вектора с вставкой по upper_bound. Да, каждое ребро хранится дважды, ну в этом есть и плюсы (самопроверка). Небольшой недостаток - для связок разных типов невозможно узнать порядок их добавления, ну такой необходимости не видно. Какой ф-ционал обобщается:

1) Разрыв связок при удалении одного их объектов. Тут все хорошо, деструктор CGraphNode вычеркивает ребра

2) Запись связок для undo - возни больше (наверное придется писать индексы m_ArcInp/Out), но вроде тоже ложится

3) I/O - тоже вполне, может даже лучше хранить вектора (данные CGraphNode) отдельно в хеше.

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

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


Название: Re: Деревянный айтем
Отправлено: Авварон от Январь 04, 2019, 13:08
На первой странице предлагали...


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 06, 2019, 09:40
На первой странице предлагали...
Ну считайте что тупой и не понял - лучше чем тратить время на бесполезные пререкания  :)

4) (злосчастное) копирование/клонирование. Здесь общего решения не вижу. Смутное соображение - вот если бы как-то создать/заполучить "мапу копирования" (т.е. какой объект скопировался в какой), то можно пробежаться по связкам и заменить.
Поразмышлял над этим - в общем виде все не так просто. Для разных зависимостей могут потребоваться разные стили копирования.

1) Объекты A и B копируются в A1 и B1, копии должны иметь те же зависимости (но уже между A1 и B1). Возможный случай но не единственный

2) Связки вообще не копируются.

3) Копируются лишь некоторые связки

Пример: зависимости master-slave, объект slave использует некоторые параметры объекта master'а. Slave(ов) может быть сколько угодно, но каждый ссылается лишь на одного master'а. Фактически "еще одна" иерархия. При копировании slave копия ссылается на того же master'а. А вот при копировании мастера ссылки на него не копируются. Хотя при копировании обоих вариант 1 выглядит разумнее.

Похоже ни к какому "автоматычному" копированию стремиться не следует, сделать по умолчанию "никакие связки не копируются", а потом разбираться имея на руках контейнеры оригиналов и копий. Есть др мнения? А если согласны - то как техничнее оформить разборку?

Да, и если уже "пердлагали" - плиз "ткните носиком" где :)  Спасибо


Название: Re: Деревянный айтем
Отправлено: Авварон от Январь 07, 2019, 15:07
Еще раз - вам надо несколько графов.


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 11, 2019, 07:42
Еще раз - вам надо несколько графов.
Ну как-то я не оценил (концептуальной) глубины этого совета :) В самом деле, что из этого следует? Вот есть некая зависимость, что с ней делать? Давайте в классе заведем указатель "на кого ссылаемся". А на др стороне вероятно массив "тех кто на меня ссылается". И будем отслеживать это там и сям (список выше). А еще зависимость - повторить. Ну оно сейчас так примерно и сделано, и это изрядно загрязняет рабочие классы и undo. Или я чего-то не понял?

Написал неск тестов, пока проблем не испытал. Обдумываю как это "ляжет". Вот (пока) один случай где нужно больше ф-ционала: связка содержит данные (контейнер). Напрашивается добавить это в класс дуги, напр
Код
C++ (Qt)
struct CGraphArc {
 ...
 TArcType m_type;            // тип зависимости
 CGraphNode * m_node;   // второй нод (первый - владелец этой CGraphArc)
 CArcData * m_data;        // ??? данные дуги/связки
};
 
Чем это плохо/чревато? Какие есть еще возможности ?


Название: Re: Деревянный айтем
Отправлено: Racheengel от Январь 15, 2019, 14:06
Для копирования можно решить задачу через ID.
В скопированной структуре все ID копий дополняем суффиксом "_Copy" (например), попутно запоняя мапу <ID : pointer>.
Затем пробегаемся по ним ещё раз и подставляем соответствующие новым ID значения указателей.

ЗЫ. "я так делал, оно работаеть" :)


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 16, 2019, 13:46
Для копирования можно решить задачу через ID.
В скопированной структуре все ID копий дополняем суффиксом "_Copy" (например), попутно запоняя мапу <ID : pointer>.
Затем пробегаемся по ним ещё раз и подставляем соответствующие новым ID значения указателей.

ЗЫ. "я так делал, оно работаеть" :)
Не очень понял причем здесь ID. Ладно, попробую еще раз направить обсуждение в нужное русло (куда оно идти упорно не хочет  :))

Вот есть структура стартового поста (там правда маленько насвистел, правильно QList вместо QVector, айтемы должны быть не перемещаемы). Нужен член m_parent (хотя бы для удаления айтем). Выясняется что каких-то чудесных средств для автоматычной поддержки члена m_parent нема - лучше всего запретить копирование и передавать указатель как аргумент во все методы требующие его установки. В этом нет ничего плохого.

Хорошо, теперь возникает простая мысль - а не сделать ли это в общем виде, напр базовый класс хранящий 2 контейнера (связки "на кого ссылаюсь я" и "кто ссылается на меня"). Тогда структура "дерево"(по сути айтем дерева) просто не нужна - она покрывается базовым классом. А если идентифицировать связки, то один айтем (содержательные данные) могут храниться в N различных деревьях. А по жизни часто собсно "дерева" и нет как такового - зависимость часто вырождается в примитивное "объект A зависит от объекта B" - но это тоже надо поддерживать, и это не так уж дешево.

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

- если скопировался и парент и чайлд - создаем новую связку
- если скопировался только чайлд - связываем его со старым парентом

Вот все, прошу излагать свои мысли


Название: Re: Деревянный айтем
Отправлено: Racheengel от Январь 16, 2019, 15:31
Я что имею в виду: например у нас есть объекты А, B, C. Пусть B и C - дети А, тогда имеем такой псевдо-код:

A{name = "Item.A", m_parent = NULL, childs = {B,C} };
B{name = "Item.B", m_parent = &A, childs = {B,C} };
C{name = "Item.C", m_parent = &A, childs = {NULL} };

Теперь мы скопипастили наш А (допустим), после вставки у нас стало:

// это оригиналы:
A{name = "Item.A", m_parent = NULL, childs = {B,C} };
B{name = "Item.B", m_parent = &A, childs = {B,C} };
C{name = "Item.C", m_parent = &A, childs = {NULL} };

// а это копии:
A1 {name = "Item.A", m_parent = NULL, childs = {B,C} };
B1 {name = "Item.B", m_parent = &A, childs = {B,C} };
C1 {name = "Item.C", m_parent = &A, childs = {NULL} };

То есть копии до сих пор ссылаются на оригиналы, тем самым херя всю иерархию. И надо бы это сделать "правильно", в этом задача?


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 17, 2019, 11:39
То есть копии до сих пор ссылаются на оригиналы, тем самым херя всю иерархию. И надо бы это сделать "правильно", в этом задача?
Да, точнее "и в этом тоже" (обсуждение др аспектов общей конструкции тоже приветствуется). Ладно, поехали с копированием. Наверное Вы имели ввиду
Код:
// а это копии:
A1 {name = "Item.A", m_parent = NULL, childs = {&B,&C} };
B1 {name = "Item.B", m_parent = &A, childs = {NULL} };
C1 {name = "Item.C", m_parent = &A, childs = {NULL} };
Напрашивается такое решение: создать мапу/хеш "кто в кого скопировался", т.е.
Код:
{ { A, A1 }, { B, B1 }, { C, C1 } }
Паренты и чайлды копий изначально пустые. Теперь пробегаемся по хешу, псевдокод
Код
C++ (Qt)
void SetLinks( const Hash & hash )
{
  for (iter it = hash.begin(); it != hash.end(); ++it) {
    Node * src = it.key();
    Node * dst = it.value();
    dst->m_parent = hash.value(src->m_parent);   // пробуем установить копию парента
    if (!dst->m_parent)
      dst->m_parent = src->m_parent;   // иначе копия получает того же парента что и оригинал
 
    if (dst->m_parent)
      dst->m_parent->AddChild(dst);      // добавляем чайлда
  }
}
 
Выглядит разумно и просто, но тут 2 момента

1) Явная ошибка: копии могут получать новых чайлдов в другом порядке, напр
Цитировать
A1 {name = "Item.A", m_parent = NULL, childs = {&С1,&B1} };
(прекрасная мелкая пакость  :))

2) Не совсем ясно а как же заполучить хеш - вероятно придется создавать вектор всех копируемых и создавать копии/клоны эл-т за эл-том. Это не так уж страшно, но
Код
C++ (Qt)
СTreeItem * dst = src->Clone(parent);
Интуитивно (или стандартно) ожидается что будет скопирована вся ветка дерева (рекурсивный вызов Clone). Но тогда в какой момент пробегаться по хешу (и как его накопить) ?

Мда, все не так уж просто  :)


Название: Re: Деревянный айтем
Отправлено: Racheengel от Январь 17, 2019, 12:42
Если рекурсия, то еще проще можно.
Поскольку в метод клонирования передается новый родитель, сразу назначаем его "детям".
Соответстенно родитель знает, каких детей он склонировал, он же должен занести их в свой список "детей" и так по цепочке :)


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 18, 2019, 11:09
Если рекурсия, то еще проще можно.
Поскольку в метод клонирования передается новый родитель, сразу назначаем его "детям".
Соответстенно родитель знает, каких детей он склонировал, он же должен занести их в свой список "детей" и так по цепочке :)
Все так, но здесь протаскивается предположение что "парент владеет чайлдами" (значит и отвечает за их клонирование). А вот более общий случай

- сами айтемы помещены в контейнер (напр QList) который ими и владеет. Но айтемы еще и связаны в дерево (а может и не одно). Юзеру выбирает "вьюху" (как здесь говорят) где айтемы показаны или по порядку в контейнере (flat) или в виде дерева (hierarchy) или еще как. Вот какие-то айтемы выбраны и жмется бубочка "duplicate". Наши действия?


Название: Re: Деревянный айтем
Отправлено: Авварон от Январь 18, 2019, 11:59
Наши действия?

Ну все как обычно, вы недоговоариваете. Для простоты возьмем один айтем (А). Им владеет айтем Б. И он "смотрит" на айтем В.
Копируем айтем А1. Что должно произойти?


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 18, 2019, 12:47
Для простоты возьмем один айтем (А). Им владеет айтем Б. И он "смотрит" на айтем В.
Копируем айтем А1. Что должно произойти?
Пусть копируется только A->A1. Тогда копия должна ссылаться на имеющиеся Б и В. Если же и они копировались, то копия должна ссылаться на Б1 и/или В1. К этому можно придраться, но другого разумного поведения я не вижу.

Как уже не раз говорилось, "владение" здесь ни при чем. Оно всего лишь означает что разрыв связи должен сопровождаться удалением ссылающегося. Что кстати не уникально, напр айтемы связаны в 2 или более деревьев, любое может удалять, почему нет?


Название: Re: Деревянный айтем
Отправлено: ssoft от Январь 18, 2019, 16:37
Как уже не раз говорилось, "владение" здесь ни при чем. Оно всего лишь означает что разрыв связи должен сопровождаться удалением ссылающегося. Что кстати не уникально, напр айтемы связаны в 2 или более деревьев, любое может удалять, почему нет?

Вы все время смешиваете два вида сущностей в одно целое.

Есть данные D1, D2, D3, временем жизни которых что-то управляет (или другими словами владеет). Это может быть общий менеджер данных или узлы контейнера (списка, дерева или др.).

Узлами контейнера N1, N2 и т.п. уникально владеет (управляет временем жизни) сам контейнер. Узлы одного контейнера не являются одновременно узлами другого.
Что касается данных D, то реализуется связь [1..1], то есть одному элементу данных Di всегда соответствует один узел Ni.
Если предполагается, что узлы управляют временем жизни данных (владеют), то можно говорить о композиции (уникальной агрегации) данных узлами.
Если предполагается, что узлы не управляют временем жизни данных (данными владеет некий внешний менеджер), то можно говорить об ассоциации данных узлам.
Но, и в том и другом случае при копировании узлов, данные тоже копируются.

Что-такое данные и какими свойствами они обладают - обобщенные (shared), неявно обобщенные (copy-on-write), единичные или в виде контейнера (мультипликативность) и т.п. решается в контексте конкретной задачи.

Например, есть данные MyStruct
- если не требуется обобщение данных, то в качестве D используем MyStruct, ::std::unique_ptr<MyStruct> или др.
- если требуется обобщение данных, то в качестве D используем SharedWrapper<MyStruct>, QSharedPointer<MyStruct>, ::std::shared_ptr<MyStruct> или др.
- если требуется неявное обобщение данных, то в качестве D используем ImplicitSharedWrapper<MyStruct> или др.

Второе, не следует смешивать две совершенно разных вещи - контейнер Tree и отношение Parent-Child.

Отношение Parent-Child подразумевает, что Parent управляет временем жизни (владеет) Child, при этом Child композитно агрегируется в Parent (уникально владеет).
Parent может содержать 0, 1 .. N элементов Child в любом представлении (упорядоченно/не упорядочено, в виде отображения или еще чего нибудь).
Обычно подразумевается, что Child имеет ассоциативную связь с Parent, хотя это не обязательно.
Удаление Parent влечет за собой удаление всех Child. Копирование Parent - копирование всех Child.

Отношение Parent-Child может быть реализовано без всякого обобщающего контейнера Tree.

В случае наличия контейнера Tree, он полностью владеет своими узлами, и, как частный случай возможной реализации, отношение узлов N в контейнере Tree может быть реализовано в виде отношения Parent-Child.
При этом сам контейнер композитно агрегирует корневой Parent (обычно называют root).


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 19, 2019, 09:17
Второе, не следует смешивать две совершенно разных вещи - контейнер Tree и отношение Parent-Child.
Ну "совершенно разные" - явный перегиб, "дерево" по существу и есть утверждение зависимости парент-чайлд. Но согласен что это "не одно и то же", чайлды необязательно удаляются/копируются вместе с парентом (как это часто подразумевается).

Это злосчастное "владение" все время уводит в сторону. Предлагаю считать что "владелец" - просто контейнер всех объектов (напр QList) в порядке их создания, и хранятся указатели т.е. объекты неперемещаемы.

Например, есть данные MyStruct
- если не требуется обобщение данных, то в качестве D используем MyStruct, ::std::unique_ptr<MyStruct> или др.
- если требуется обобщение данных, то в качестве D используем SharedWrapper<MyStruct>, QSharedPointer<MyStruct>, ::std::shared_ptr<MyStruct> или др.
- если требуется неявное обобщение данных, то в качестве D используем ImplicitSharedWrapper<MyStruct> или др.
Не понял о каком (неявном) обобщении Вы говорите? Вот пользователю предъявлен список объектов в режиме "by hierarchy", т.е. он может линковать один объект к другому. Теперь он переключился напр в режим "by master material", тоже иерархия/дерево но никак не связанная с предыдущим, т.е. объекты те же но зависимости между ними совсем другие. Что предлагаете? Рисовать структуры для каждого случая (навскидку насчитаю десяток). Или все-таки попробовать как-то обобщить? И ничего я не "путаю"


Название: Re: Деревянный айтем
Отправлено: ssoft от Январь 19, 2019, 22:10
Ну "совершенно разные" - явный перегиб, "дерево" по существу и есть утверждение зависимости парент-чайлд. Но согласен что это "не одно и то же", чайлды необязательно удаляются/копируются вместе с парентом (как это часто подразумевается).

Конкретная реализация "дерева" не обязательно построена на зависимости "парент-чайлд".
Можно, например, "дерево" внутри реализовать с помощью обычного отображения {key, value}, где в качестве ключа использовать пару {номер уровня, номер позиции на уровне}. Внешний интерфейс при этом ни чем не будет отличаться от "дерева", реализованного с помощью "парент-чайлд".

Это злосчастное "владение" все время уводит в сторону. Предлагаю считать что "владелец" - просто контейнер всех объектов (напр QList) в порядке их создания, и хранятся указатели т.е. объекты неперемещаемы.

"Владение" в рамках объектно ориентированной модели правильнее называть ассоциативной связью агрегации. Если в объектной модели не определить кто-кого-каким способом агрегирует (другими словами, кто-кем-как владеет), с учетом правил непротиворечивости самой модели, то никогда не получится корректное программное решение.

Для отношения "парент-чайлд" общепринятая объектная модель определена однозначно, как описано мной ранее.
Цитировать
Отношение Parent-Child подразумевает, что Parent управляет временем жизни (владеет) Child, при этом Child композитно агрегируется в Parent (уникально владеет).
Это, можно сказать, определение этого отношения. Другая модель уже не реализует отношение "парент-чайлд", а реализует что-то ещё.

Не понял о каком (неявном) обобщении Вы говорите?

Неявное обобщение (implicit-shared) используется в частности для реализации механизма copy-on-write, когда фактическое копирование данных происходит в момент обращения к ним для изменения. То есть фактически используется обобщение данных, но реализуется поведение уникального владения (композитного агрегирования).

Вот пользователю предъявлен список объектов в режиме "by hierarchy", т.е. он может линковать один объект к другому. Теперь он переключился напр в режим "by master material", тоже иерархия/дерево но никак не связанная с предыдущим, т.е. объекты те же но зависимости между ними совсем другие. Что предлагаете? Рисовать структуры для каждого случая (навскидку насчитаю десяток). Или все-таки попробовать как-то обобщить? И ничего я не "путаю"

В этом описании реализуемая модель может выглядеть так:
- Существует общий менеджер ресурсов в виде неупорядоченного их множества. Именно этот менеджер "уникально владеет" (композитно агрегирует) ресурсами.
- Существует набор деревьев "by hierarchy", "by master material" и т.п., содержащий в узлах данные с ассоциативным связями (ссылками или не владеющими указателями) на ресурсы.

Либо без общего менеджера ресурсов:
- Существует набор деревьев "by hierarchy", "by master material" и т.п., содержащий в узлах данные, которые "совместно владеют" (обобщенно агрегируют) ресурсы.

То есть в деревья складываются не сами ресурсы, а данные, которые определяют вид ассоциативных связей с ресурсами.
При этом и в том и другом случае данные могут обладать еще и дополнительными уникальными атрибутами, если это необходимо.
Само понятие "дерева" следует реализовать в виде шаблона, узлы которого композитно агрегируют (уникально владеют) данными. Тип данных является параметром шаблона.


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 20, 2019, 13:47
"Владение" в рамках объектно ориентированной модели правильнее называть ассоциативной связью агрегации. Если в объектной модели не определить кто-кого-каким способом агрегирует (другими словами, кто-кем-как владеет), с учетом правил непротиворечивости самой модели, то никогда не получится корректное программное решение.
Ну ладно, давайте о владении (толку все равно нет).

Вот есть 3D сцена в которую юзверь добавляет 3D объекты, напр модели, камеры, источники света и.т.п. Кто "владеет" этими объектами? Наверное академически правильно сказать: класс "сцена", но можно и по-простому: "контейнер объектов". Отношения между объектами  могут быть самыми разнообразными и выражаться самым разным ф-ционалом, как раз проблема в том что этих отношений очень много. Но с "владением" они никак не связаны - объект либо существует в сцене - либо нет, и значит он сам удален. Вот и все

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

Как видите, вопрос "владения" для объектов верхнего уровня не стоит выеденного яйца. С ним давным-давно все ясно (объектами владеет сцена), и постоянно скатываясь во "владение" мы только толчем воду в ступе.

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

Дерево предполагает что нод имеет одного (и только одного) парента. Это так в подавляющем большинстве случаев, но все же не всегда. Пример: объекты типа Bone (кости, по-простому отрезок или точка) управляют полигонной моделью, как правило к модели линкуется 100 и более костей. Но никто не мешает прилинковать ту же кость(и) к др модели(ям). "Только один парент" здесь никак не выходит. Поэтому все-таки граф (не пойму чем это совершенно безобидное слово так ранит любителей std  :))

Само понятие "дерева" следует реализовать в виде шаблона, узлы которого композитно агрегируют (уникально владеют) данными. Тип данных является параметром шаблона.
Понял так что, мол, template - это признак грамотности, давайте совать его везде. Но не вижу как (или чем) он здесь поможет. Все 3D объекты унаследованы от базового класса, напрашивается добавить менеджер ссылок к нему. Но меня почему-то упорно тянет сделать этот менеджер внешним классом (хешем), напр
Код:
QHash<BaseClass *, CGraphNode> theReferenceHash;
Все-таки пробежка по всем ссылкам (хотя бы их дебаг печать и I/O) - ценная возможность, да и далеко не каждый объект имеет ссылки/связи. Или даже вот так, вызывающе
Код:
QHash<void *, CGraphNode> theReferenceHash;  // ой как некрасиво :-)
Т.е. кто угодно может иметь связи, нужно только в деструкторе вычеркнуть себя из хеша. Зато не морочить голову с навязчивым множ наследованием, подкладкой базового клааса и.т.п. Не, я конечно понимаю что так "низзя", но заманчиво... :)



Название: Re: Деревянный айтем
Отправлено: ssoft от Январь 21, 2019, 09:33
Отношения между объектами  могут быть самыми разнообразными и выражаться самым разным ф-ционалом, как раз проблема в том что этих отношений очень много. Но с "владением" они никак не связаны - объект либо существует в сцене - либо нет, и значит он сам удален. Вот и все

Понятие отношений (ассоциаций) в объектно-ориентированном моделировании имеют четкие определения, в том числе и агрегация (https://www.uml-diagrams.org/aggregation.html?context=class-diagrams), как частный случай. Это отношение показывает кто-кого-когда-как удаляет. Требование к непротиворечивости модели определяет, могут ли определенные отношения сосуществовать вместе.

Для решения одной и той же задачи можно построить несколько непротиворечивых моделей отношений. Выбрать одну из них по каким-либо критериям - задача программиста. Именно поэтому возникает столько вопросов по нюансам каждой из задачи.

Тот же пример: отношение "иерархия" (парент-чайлд) визуализировано в виде дерева. Да, удаление/копирование парента применяется ко всем его чайлдам, но это же вовсе не значит что "парент владеет чайлдом" - просто он может (или имеет право) удалять/копировать объекты сцены.

Как легко Вы смешиваете несмешиваемое :D.

Визуализация в виде дерева не является каким либо отношением, это всего лишь удобное представление. Можно реализовать 100500 разных представлений для одной и той же модели данных. Представление является только отражением модели данных, даже если данные агрегировали внутрь конкретного представления. Данные первичны, представление вторично.

Да, удаление/копирование парента применяется ко всем его чайлдам, и в рамках понятий объектно ориентированной модели - это обязательно означает, что "парент владеет чайлдом".

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

Вот есть 3D сцена в которую юзверь добавляет 3D объекты, напр модели, камеры, источники света и.т.п. Кто "владеет" этими объектами? Наверное академически правильно сказать: класс "сцена", но можно и по-простому: "контейнер объектов".
...
Как видите, вопрос "владения" для объектов верхнего уровня не стоит выеденного яйца. С ним давным-давно все ясно (объектами владеет сцена), и постоянно скатываясь во "владение" мы только толчем воду в ступе.

Случай, когда объектами владеет сцена, является частным (могут быт и другие решения). И конкретно в данном случае, действительно сцена является контейнером (агрегатором) объектов сцены. Именно через API класса сцены происходит добавление/удаление и т.п., другими словами - управление временем жизни объектов сцены. Сцена реально "владеет" своими объектами. Удаление объекта из сцены сделает все ссылки на него невалидными, поэтому требуется писать дополнительный по управлению этими ссылками (удаление из деревьев и т.п.). Напротив, удаление ссылки никаким образом не влияет на сам объект.

Дерево предполагает что нод имеет одного (и только одного) парента. Это так в подавляющем большинстве случаев, но все же не всегда. Пример: объекты типа Bone (кости, по-простому отрезок или точка) управляют полигонной моделью, как правило к модели линкуется 100 и более костей. Но никто не мешает прилинковать ту же кость(и) к др модели(ям). "Только один парент" здесь никак не выходит. Поэтому все-таки граф (не пойму чем это совершенно безобидное слово так ранит любителей std  :))

Если экземпляром объекта типа Bone "кость" владеет сцена, то помещайте в деревья экземпляры объектов типа LinkToBone, с линком к Bone. Не хотите, чтобы сцена владела "костями", помещайте в деревья экземпляры объектов типа SharedBone.

Поэтому все-таки граф (не пойму чем это совершенно безобидное слово так ранит любителей std  :))

Граф - это очень емкое понятие. Любые отношения образуют граф. Способов реализации - миллион. Оптимальной реализации на все случаи жизни - нет.
Частных случаев под определенный класс задач - масса. Наиболее известные простые - односвязный и двухсвязный список.
Более сложные из темы 3D - отношения между вершинами/ребрами/гранями/объемами. Различных реализаций тоже много.
Запихнуть все в единую реализацию графа - не очень здравая мысль. Как минимум, получится не оптимально.

Само понятие "дерева" следует реализовать в виде шаблона, узлы которого композитно агрегируют (уникально владеют) данными. Тип данных является параметром шаблона.
Понял так что, мол, template - это признак грамотности, давайте совать его везде. Но не вижу как (или чем) он здесь поможет.

 ;D Грамотность тут ни при чем. Дерево, по своей сути, тоже является контейнером (агрегатором) общего назначения подобно ::std::list, ::std::map и др. Просто видов деревьев достаточно много, поэтому они не входят в std.
Вам нужна конкретная реализация дерева, но для разных случаев "by hierarchy", "by master material" и т.п. Поэтому template самое оно  ;).

Любой из контейнеров можно легко реализовать без шаблонов, прямо на void*. Но чтобы так не делать, собственно, и разработали язык шаблонов.

Все 3D объекты унаследованы от базового класса, напрашивается добавить менеджер ссылок к нему. Но меня почему-то упорно тянет сделать этот менеджер внешним классом (хешем), напр
Код:
QHash<BaseClass *, CGraphNode> theReferenceHash;
Все-таки пробежка по всем ссылкам (хотя бы их дебаг печать и I/O) - ценная возможность, да и далеко не каждый объект имеет ссылки/связи. Или даже вот так, вызывающе
Код:
QHash<void *, CGraphNode> theReferenceHash;  // ой как некрасиво :-)
Т.е. кто угодно может иметь связи, нужно только в деструкторе вычеркнуть себя из хеша. Зато не морочить голову с навязчивым множ наследованием, подкладкой базового клааса и.т.п. Не, я конечно понимаю что так "низзя", но заманчиво... :)

Так тоже будет работать), только медленнее. Если вдруг многопоточка - конкурентный доступ к theReferenceHash. Любой поиск связи - обращение к QHash. В 3D, где важны микросекунды - это может быть существенно.
Что будет в качестве ключа BaseClass *, void *, Handle не важно, если не используется reinterpret_cast или static_cast. Красиво/не красиво - дело вкуса. Главное, чтобы работало как нужно и удовлетворяло требованиям по производительности и др.


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 21, 2019, 11:50
Как легко Вы смешиваете несмешиваемое :D.
...
Можно реализовать 100500 разных представлений для одной и той же модели данных. Представление является только отражением модели данных, даже если данные агрегировали внутрь конкретного представления. Данные первичны, представление вторично.
Почему люди (даже хорошие) повторяют эту песню model-view хотя ее несуразность очевидна и лезет из всех щелей? :) Ну спрятались за термин "представление", что это меняет? "Только отражение" возможно лишь в простейшем случае. Чтобы отобразить flat контейнер в виде дерева - уже нужно как минимум создать связи и где-то их хранить (хотя бы m_parent). Тогда в чем "вторичность представления" если оно рулит данными о которых оригинальная модель (flat контейнер) понятия не имеет? Эти данные чем-то неполноценны и отношением считаться не могут? Чем же?

Визуализация в виде дерева не является каким либо отношением, это всего лишь удобное представление.
...
В представленном конкретном случае, сами объекты сцены не участвуют ни в каких отношениях "парент-чайл", хотя Вы упорно пытаетесь их заставить  :D
...
Напротив, удаление ссылки никаким образом не влияет на сам объект.
То же отношение "иерархия" (если хотите "представление"). Линковка одного объекта к другому обычно выполняется с целью наследования трансформов парента (т.е. чайлд двигается (и/или врашается, скалится, деформируется и.т.п.) вместе с парентом, т.е. логика та же - операции над парентом применяются к его чайлдам. Если чайлд имеет свои анимации, то они должны быть пересчитаны так чтобы на момент линковки были дефаултами. Аналогично при отлинковке. Поэтому говорить о том что, мол, "никаких отношений между объектами нет" явно неуместно, да и просто противоречит здравому смыслу. Отношение "иерархия" налицо, подтверждается и визуально, и опциями, и как угодно. А что оно не вписывается в каноны model-view - так в этом я не виноват  :)

В представленном конкретном случае, сами объекты сцены не участвуют ни в каких отношениях "парент-чайл",
...
В отношениях участвуют промежуточные данные, содержащие ассоциативные связи с этими объектами, а не сами объекты.
Из чего сие следует? Только из того что способ хранения объектов в сцене выбран flat? Стало быть, никаких "отношений" быть не может. Вот был бы способ хранения "дерево" - тогда было бы отношение "иерархия" (и только оно, а там только для UI надо пяток). Вам не кажется такой подход, мягко говоря,  "формальным"? Мы что, не можем наладить связи для организации любого числа структур? Какая разница где храним? Ну хорошо, пусть будут "представления" если религия не позволяет "отношения" :)

Вам нужна конкретная реализация дерева, но для разных случаев "by hierarchy", "by master material" и т.п. Поэтому template самое оно  Подмигивающий.

Любой из контейнеров можно легко реализовать без шаблонов, прямо на void*. Но чтобы так не делать, собственно, и разработали язык шаблонов.
Ну давайте копнем какое там "оно" :)  Вот набросок на базовом (god) классе Node
Код
C++ (Qt)
struct CGraphArc {
...
  TArcType mType;
  Node * mNode;
};
 
struct Node {
...
 QVector<CGraphArc> mInput, mOutput;  
};
Вполне норм, ну может базовый класс обременяется 2-мя контейнерам, но это уровне ощущений. Ваш вариант на template ? 


Название: Re: Деревянный айтем
Отправлено: ssoft от Январь 21, 2019, 12:49
Почему люди (даже хорошие) повторяют эту песню model-view хотя ее несуразность очевидна и лезет из всех щелей? :)

Про model-view специально ничего не писал).
На совсем базом уровне вся функциональность может быть представлена в виде цепочки преобразований

[data1]--transform1-->[data2] --transform3-->... -->[dataN]

data1 по отношению к data2 первичны. Так и исходные данные по отношению к способу их отображения первичны, даже если данные агрегированы в структуры GUI.

Но это не по теме).

То же отношение "иерархия" (если хотите "представление"). Линковка одного объекта к другому обычно выполняется с целью наследования трансформов парента (т.е. чайлд двигается (и/или врашается, скалится, деформируется и.т.п.) вместе с парентом, т.е. логика та же - операции над парентом применяются к его чайлдам. Если чайлд имеет свои анимации, то они должны быть пересчитаны так чтобы на момент линковки были дефаултами. Аналогично при отлинковке. Поэтому говорить о том что, мол, "никаких отношений между объектами нет" явно неуместно, да и просто противоречит здравому смыслу. Отношение "иерархия" налицо, подтверждается и визуально, и опциями, и как угодно. А что оно не вписывается в каноны model-view - так в этом я не виноват  Улыбающийся

Тема 3D мне очень хорошо понятна). Пользователь выполняет операции и строит зависимости в своих терминах и определениях, не обязательно имеется прямое соответствие между действиями пользователя и происходящим на программном уровне.
Например, пользователь выполнил операцию удаления объекта, а программа должна поддерживать Undo, тогда фактического удаления объекта в программе может и не быть.

Линковка одного графического объекта к другому может выполняться для разных нужд - применение каких-то свойств (трансформации, анимации, эффектов), порядок отображения, компоновка (layouting) и для многого другого.
Может существовать сразу несколько вариантов упорядочивания одних и тех же графических объектов для решения этих разных задач. Способ упорядочивания list, map, tree, custom определяет наличие отношений определенного вида между элементами контейнера.  Элемент контейнера может быть связан с графическими объектами какими-либо с отношениями. Вопросы о том, кто владеет графическими объектами раскрывают только виды отношений между элементами контейнера и графическими объектами. Виды отношений контейнеров и эх элементов предопределены в самих реализациях контейнеров.

Мы что, не можем наладить связи для организации любого числа структур? Какая разница где храним

Конечно, можем. Другой вопрос - зачем? Так как разница всё же есть - в эффективности.
Если требуется наибыстрейший перебор всех элементов, то нужно использовать vector; если при этом частые удаления/вставки, то list; если ..., то ...; если требуется дерево, то нужно использовать дерево; если другой граф, то нужно использовать другой.
Каждая из структур имеет свои сильные и слабые стороны. Решение в общем виде всегда будет проигрывать в конкретных частных случаях.

Вы часто ставите вопрос в общем виде, подразумевая свой конкретный частный случай).
Проект с template выложу попозже).


Название: Re: Деревянный айтем
Отправлено: Igors от Январь 22, 2019, 16:00
Конечно, можем. Другой вопрос - зачем?
Просто потому что объект имеет (или может иметь) 2 и более отношений/связей с другими. Строить свою структуру для каждого типа отношений.. ну иногда может и так, но не блеск. Вот хотя бы простейший случай: объект удаляется - и вычистить его из всех структур не так уж просто. В большинстве случаев выгоднее "агрегировать данные структуры в сам объект" (я верно выражаюсь?  :))

Вы часто ставите вопрос в общем виде, подразумевая свой конкретный частный случай).
Углубление в конкретику пагубно для обсуждения  :) Пример с трансформами выше - вряд ли Вам он чем-то помог, Вы и так это знали. Просто хотел напомнить что каждое отношение создается не так себе, а имеет совершенно конкретный ф-ционал/смысл который обязан поддерживаться. Можно рассказать и про упомянутый "by master matrial" но это не внесет ровным счетом ничего нового, все то же: чайлд (по сути "клиент") юзает парента (сервер). Установка/разрыв связи практически всегда сильно влияет на чайлда, но почти никогда на парента (хотя исключения все же есть). А вот что там и как меняется - чисто подробности конкретной задачи и отношения к обсуждению не имеют.

Проект с template выложу попозже).
Не вопрос. Собсно данную тему можно рассматривать чисто как "дело/вопрос техники". Допустим мы хотим связывать наши структуры в 2 независимых (непротиворечивых !?) дерева. Да просто так, без раздумий
Код:
struct CTreeItem {
  QString m_name;   // какие-то свои/содержательные данные структуры
  ...
 // Данные для связки в первое дерево
  CTreeItem * m_parent;
  QVector< CTreeItem *> m_child;

 // Данные для связки во второе дерево
  CTreeItem * m_parent2;
  QVector< CTreeItem *> m_child2;
...
};
И можно с полным правом заявить что наша модель поддерживает "multiply hierarchy(ies)"  :) Однако работать с этим будет не очень удобно. Заведя конкретные поля для каждого типа отношения/зависимости мы лишаемся возможности "пробежаться по всем", и вынуждены расписывать/повторять каждое действие напр для m_child, m_child2 и.т.п.

Как здесь воткнуть шаблоны - ума не приложу, интересно посмотреть (но "торопыться нэ надо"  :))


Название: Re: Деревянный айтем
Отправлено: ssoft от Январь 25, 2019, 14:31
Как и обещал, запилил одну из возможных реализаций Tree (https://gitlab.com/ssoft-sandbox/prog.org.ru/tree-example).

Дерево Tree содержит узлы Tree::Node  в виде композитной иерархии с использованием ::std::list.
Параметрами шаблона дерева являются:
 - тип хранимого в узлах значения
 - тип наблюдателя за деревом (ниже подробнее)
 - тип аллокатора для узлов Node (по умолчанию ::std::allocator)

Тип наблюдателя за деревом Observer необходим для сбора и хранения дополнительной информации об элементах дерева:
 - подсчету статистики (общей и по каждому из узлов);
 - индексации и/или упорядочивания узлов по любым критериям;
 - и др.

Конкретная реализация Observer должна содержать:
 - определение типа NodeInfo, значение которого встраивается в узел Node (доступно по методу info())
 - реализацию методов:
     --  void afterInsert ( NodeIdent ident );
     --  void beforeErase ( NodeIdent ident );
   позволяющую наблюдателю что-то считать и/или индексировать и/или делать что-то ещё.

Узел дерева Node содержит
 - ассоциацию с самим деревом
 - ассоциацию с вышестоящим узлом
 - значение Value
 - информацию наблюдателя Info
 - двусвязный список нижестоящих узлов

В примере представлено:
 - Scene - класс сцены, которая хранит (композитно агрегирует) какие-то ресурсы в ассоциативном контейнере;
 - TransformValue - содержит ассоциативную связь с ресурсом (в виде ссылки) и дополнительный атрибут bool m_use_parent_transform;
 - TransformObserver - реализация наблюдателя, который обеспечивает быстрый поиск узла дерева по ссылке на ресурс сцены;
 - TransformTree - дерево элементов TransformValue с наблюдателем TransformObserver.

В методе main показано:
 - заполнение/удаление дерева;
 - перебор узлов по иерархии;
 - произвольный доступ к узлам с использованием функциональности наблюдателя;
 - полный линейный перебор узлов с использованием функциональности наблюдателя;
 - подсчет количества всех узлов с использованием функциональности наблюдателя;
 - удаление узлов дерева с использованием функциональности наблюдателя.


Название: Re: Деревянный айтем
Отправлено: Igors от Февраль 05, 2019, 07:59
Как и обещал, запилил одну из возможных реализаций Tree
С удовольствием поизучал, много всяких интересных штучек которые (пока) в мой арсенал не входят. Спасибо. Все-таки... ну а стоит ли так "наворачивать"? Не, ну если маленько посидеть, потыкать браузером IDE и прочесть примечания - конечно ничего сложного нет, но первое впечатление пугающее  :) Заметил что Вы стремитесь к полному истреблению "голых указателей".  Два момента по ф-ционалу

1) Допустим в дереве (но не в сцене) есть такая иерархия

A
  B
    C

Сцена удаляет "A". Будет ли она затем удалять "B" и/или "С" - сугубо ее (сцены) личное дело, в момент удаления "A" дереву об этом ничего не известно. Поэтому чайлд "B" должен быть отлинкован, и связка B-C сохранена. Не вижу такой возможности с композитной агрегацией. Также более идейно автоматом удалять ноды дерева не имеющие никаких связок. Напр удаляется "B". Тогда если нод дерева "A" не имеет парента то он тоже должен быть удален, аналогично "С" если у него нет чайлдов

2) Ну хорошо, вот шаблоны созданы, и теперь "легким движением руки" (ну почти) мы можем создавать любые деревья. Но толку от этого мало
Отношения между объектами  могут быть самыми разнообразными и выражаться самым разным ф-ционалом, как раз проблема в том что этих отношений очень много.
Ключевое слово "много". Конкретно сейчас их уже 29. Ну и что я должен делать?
Код
C++ (Qt)
struct Scene {
 ...
 Tree<params1> TransformTree;
 Tree<params2> MaterialTree;
 ...
 Tree<params29> LastTree;
};
И на каждой операции (напр удаление нода сцены) перебирать 29 деревьев (причем даже не в цикле а "по одному")? Это нестерпимо, поэтому напрашивается так
Код
C++ (Qt)
struct Scene {
 ...
 QList<Tree<params_x>> trees;
 ...
};
Очевидно что это неоптимально (поиск в 29 хешах), а если хотим инстанциировать разные деревья разными аргументами шаблона - придется еще городить немалую городушку. В принципе это реализация мечты Карслона "8 тортов с 1 свечой", а хотелось бы наоборот.

Обсерверы - да, так или иначе что-то делать придется, но отделаться простыми методами вряд ли удастся. Здесь пока "не созрело", сначала надо присмотреться какие проблемы полезут.


Название: Re: Деревянный айтем
Отправлено: ssoft от Февраль 05, 2019, 09:10
1) Допустим в дереве (но не в сцене) есть такая иерархия

A
  B
    C

Сцена удаляет "A". Будет ли она затем удалять "B" и/или "С" - сугубо ее (сцены) личное дело, в момент удаления "A" дереву об этом ничего не известно. Поэтому чайлд "B" должен быть отлинкован, и связка B-C сохранена. Не вижу такой возможности с композитной агрегацией.

Да, в представленной реализации узлы могут перемещаться только в пределах одного дерева. Как раз решаю данное затруднение ) ... Правда похоже, что будет еще больше "наворотов".

Также более идейно автоматом удалять ноды дерева не имеющие никаких связок. Напр удаляется "B". Тогда если нод дерева "A" не имеет парента то он тоже должен быть удален, аналогично "С" если у него нет чайлдов
Здесь можно получить неожиданное поведение (предсказуемое, но не очевидное).

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

Как минимум не нужно специально 29 разных деревьев реализовывать.  :o ;D

Отношения между объектами  могут быть самыми разнообразными и выражаться самым разным ф-ционалом, как раз проблема в том что этих отношений очень много.
Ключевое слово "много". Конкретно сейчас их уже 29. Ну и что я должен делать?
И на каждой операции (напр удаление нода сцены) перебирать 29 деревьев (причем даже не в цикле а "по одному")? Это нестерпимо ...
...
реализация мечты Карслона "8 тортов с 1 свечой", а хотелось бы наоборот.

Во-первых, для деревьев можно использовать гетерогенный контейнер и и хранить их в виде списка, мапы, хеша или в любом другом виде, аля List< AnyTree >.
Во-вторых, можно в сцене завести вспомогательное отображение, которое по ключу выдаст перечень {дерево, итератор в дереве}, и будет 1 свечка на 29 тортов).


Название: Re: Деревянный айтем
Отправлено: ssoft от Февраль 05, 2019, 09:20
Заметил что Вы стремитесь к полному истреблению "голых указателей".

Так и есть. "Голый указатель" ничего толкового о себе не скажет, какая это взаимосвязь - ассоциация (ссылка), агрегация (владение общее/совместное), предполагается ли использование наследования?
Чтобы это понять, приходится изучать практически весь код, где используется голый указатель. Со специальными (умными или переопределенными через using/typedef) намного понятнее, что имеется в виду.


Название: Re: Деревянный айтем
Отправлено: Igors от Февраль 05, 2019, 15:28
Так и есть. "Голый указатель" ничего толкового о себе не скажет, какая это взаимосвязь - ассоциация (ссылка), агрегация (владение общее/совместное), предполагается ли использование наследования?
Чтобы это понять, приходится изучать практически весь код, где используется голый указатель. Со специальными (умными или переопределенными через using/typedef) намного понятнее, что имеется в виду.
Никогда не был борцом за "идейную чистоту", но все-таки "указатель" - это свое, родное, ведь все начиналось как альтернатива ассемблеру. Да, безликость/неопределенность указателя часто доставляет проблемы (особенно с пониманием), но с др стороны попытки любой ценой использовать только ссылки или итераторы, на мой взгляд, часто не очень органичны/естественны. Напр понять к чему итератор никак не дешевле чем роль указателя. Впрочем это дело вкуса


Название: Re: Деревянный айтем
Отправлено: Авварон от Февраль 05, 2019, 16:46
Igors
Ну итератор и есть логически указатель на элемент. Заметьте не "вумный" указатель, а обычный. Их делали, чтобы все контейнеры были похожи на сишные массивы со всеми вытекающими. Вообще, это изначально была плохая абстракция. Ждем Ranges=)


Название: Re: Деревянный айтем
Отправлено: Igors от Февраль 06, 2019, 08:39
Ну итератор и есть логически указатель на элемент. Заметьте не "вумный" указатель, а обычный. Их делали, чтобы все контейнеры были похожи на сишные массивы со всеми вытекающими.
Ну не со всеми, напр ассоциативный контейнер не будет иметь доступа по индексу.
Вообще, это изначально была плохая абстракция.
Ну может и не такая уж плохая (напр для того же ассоциативного выбора нет), но что ею (массово) злоупотребляют - это точно.

Ждем Ranges=)
А шо это ??? Киньте ссылочку если не затруднит. Спасибо


Название: Re: Деревянный айтем
Отправлено: Igors от Февраль 06, 2019, 09:15
Во-первых, для деревьев можно использовать гетерогенный контейнер и и хранить их в виде списка, мапы, хеша или в любом другом виде, аля List< AnyTree >.
Во-вторых, можно в сцене завести вспомогательное отображение, которое по ключу выдаст перечень {дерево, итератор в дереве}, и будет 1 свечка на 29 тортов).
Попробую сделать некоторые выводы. По существу мы хотим спроектировать manager ссылок/связей (с деревьями или как - это все-таки вторично/реализация). Этот manager ОДИН объект (во всяком случае с точки зрения использования), напр член класса "сцена".
Код
C++ (Qt)
struct Scene {
...
CReferenceManager mRefMan;
...
};
Поскольку он один а типов ссылок десятки, то выходит что практически каждое обращение к manager'у должно быть идентифицировано каким-то ключом (какие ссылки мы хотим читать/писать). Пусть этот ключ - просто enum, напр
Код
C++ (Qt)
enum TArcType {
 ARC_TYPE_ANY  = 0,
 ARC_TYPE_HIERARCHY  = 1,
 ARC_TYPE_MATERIAL  = 2,
 ARC_TYPE_SKIN  = 3,
 ...
 ARC_TYPE_SOMETHING  = 29,
};
Теперь нужно набросать методы этого manager'а, т.е. что мы от него хотим. Обход дерева и.т.п. - да, есть и такие задачи, но далеко не первые.  В первую очередь для каждого нода/элемента сцены нужно знать "кто ссылается на него" и "на кого ссылается он". Заметим что интересны только ссылки, сами по себе внутренние структуры типа "ноды дерева" бесполезны и светить их снаружи смысла нет. Пусть Node - элемент сцены, тогда напрашиваются такие геттеры
Код
C++ (Qt)
struct CReferenceManager {
...
Node * GetInpNode( TArcType type, const Node * src ) const;
Node * GettOutNode( TArcType type, const Node * src ) const;
Неплохо, во многих случаях ссылка данного типа может быть только одна (или NULL - никакой). Но не во всех. Как тогда извлекать инфу о ссылке? Думаю нужно вводить класс/сущность "ссылка/связка", предлагаю такую, незатейливую
Код
C++ (Qt)
struct CRefArc {
 TArcType mType;
 Node * mNode;
 CArcData * mData;   // данные ссылки (проблематично)
};
И, не мудрствуя лукаво, возвращать константные указатели на нее, напр
Код
C++ (Qt)
struct CReferenceManager {
...
const CRefArc * GetInpArc( TArcType type, const Node * src, int * arcCount ) const;
const CRefArc * GetOutArc( TArcType type, const Node * src, int * arcCount ) const;
};
Ну пока хватит, критикуем, предлагаем...


Название: Re: Деревянный айтем
Отправлено: Igors от Февраль 08, 2019, 12:59
..критикуем, предлагаем...
Мда..  :) Ну ладно, расскажу пока что такое "данные ссылки", может появятся идеи.

Когда боны (кости) линкуются к модели, для каждой боны вычисляется на какие вертексы модели она влияет (индексы) и насколько (вес).
Код:
struct CBoneWeight  {
  int vertexIndex;
  double weight;
};

typedef std::vector<CBoneWeight> CBoneInfo;  // каждая прилинкованная бона имеет этот вектор
Вот тут все четко - данные принадлежат именно ссылке, сами по себе они не имеют смысла ни для кости ни для модели.

Однако меня смущает что этот случай - единственный, никаких других не находится. В подавляющем большинстве случаев достаточно "голого факта" ссылки, ссылающийся обычно прекрасно сам знает что делать. В немногих других да, есть данные что используются совместно со ссылкой, но они просто принадлежат ссылающемуся. Напр зависимость "иерархия" имеет набор опций (напр наследовать ли вращение парента и.т.п.), но эти опции должны предъявляться в UI объекта независимо от наличия парента в данный момент. Ладно, вот изначальная плохонькая констукция
Код
C++ (Qt)
struct CRefArc {
 TArcType mType;
 Node * mNode;
 CArcData * mData;   // данные ссылки (проблематично)
};
 
Что здесь мне не нравится

- случай весьма редкий, а заряжается регулярный член mData. Не смертельно, но как-то не по-хозяйски

- данные (mData) шарятся - если их имеет парент то и чайлд тоже. Тупо QSharedPointer<CArcData> вроде в тему, но хз

- стандартная проблема копирования указателя на полиморфный класс (вместе с содержимым). Придется видимо заряжать
Код
C++ (Qt)
virtual CArcData * CArcData::Clone( void ) const = 0;
Что при желании можно причислить к "костылям"

Связываться с богомерзкими темплейтами - обычная история, себе дороже. Это моментально сделает вмещающий класс (CRefArc) шаблонным, дальше развалится его владелец и.т.п. И придется работать на аптеку с "гетерогенными контейнерами"

Или все-таки можно сделать как-то "модерново" вместо этого "С с классами"? (та знаю что нет ну а вдруг?  :))


Название: Re: Деревянный айтем
Отправлено: Авварон от Февраль 08, 2019, 15:55
Ну вот и "пошли детали" без которых не догадаться что там вам надо. Откуда нам было знать, что такое данные связи и как часто они нужны?

Ну хорошо, чем вам "матричный" граф не нравится? Есть матрица N*N где N - количество нод. В ячейке i,j лежит битарей, который говорит, какие связи между нодами i,j есть.
Матрицу можно реализовать на основе хэша (ключ - std::pair<int /*i/*, int /*j*/>), тогда возможно меньше будет пропадать места, энивей, добавление элемента не будет требовать релокации всей матрицы.
Тогда дату для одной связи можно положить в соседний хэш с аналогичным ключом.
Плюс решения - есть универсальный "граф" который держит любое кол-во связей.
Минус - что данные о связи отдельно. Ну так вроде это и была хотелка.
Еще минус - загадочные undo и redo, которые может быть сложно реализовать (придется побегать циклами по матрице, ну ой, ничего страшного)


Название: Re: Деревянный айтем
Отправлено: Igors от Февраль 09, 2019, 10:24
Ну хорошо, чем вам "матричный" граф не нравится? Есть матрица N*N где N - количество нод. В ячейке i,j лежит битарей, который говорит, какие связи между нодами i,j есть.
Так а где взять эти индексы i/j ? Они же сразу "уплывут" если удалился объект сцены.

Матрицу можно реализовать на основе хэша (ключ - std::pair<int /*i/*, int /*j*/>), тогда возможно меньше будет пропадать места, энивей, добавление элемента не будет требовать релокации всей матрицы.
Тогда уже ключ хеша QPair<Node *, Node *>, но как тогда напр "пробежаться по всем чайлдам" (причем в порядке их следования)? Хотелка как раз в том что для любого нода сцены иметь под рукой всех его парентов и чайлдов.

Еще минус - загадочные undo и redo, которые может быть сложно реализовать (придется побегать циклами по матрице, ну ой, ничего страшного)
Заметим что при undo порядок следования чайлдов (как они были прилинкованы к паренту) должен быть точно восстановлен.

Ну вот и "пошли детали" без которых не догадаться что там вам надо. Откуда нам было знать, что такое данные связи и как часто они нужны?
Ну "как работают боны" - вполне в рамках популярных знаний, причем с бородой, за последние 25 лет не слышал ничего нового. Впрочем и этого не требуется - "зависимость может иметь собственные данные" - все что Вам нужно знать для разработки структур/архитектуры. Популярно мнение что, мол, надо все-все знать/изучить и вот тогда... Это наивное заблуждение (а чаще просто повод увильнуть от работы), объем инфы быстро превышает (небольшую) емкость мозга. Всех подробностей не помнят даже авторы. Напр я помню "29" потому что на загрузке есть точка где все они настраиваются, я туда progress bar добавлял. Из этих 29 зависимостей я помню может один десяток (в основном те что сам писал).

Тогда дату для одной связи можно положить в соседний хэш с аналогичным ключом.
Плюс решения - есть универсальный "граф" который держит любое кол-во связей.
Минус - что данные о связи отдельно. Ну так вроде это и была хотелка.
Да, есть такой вариант
Код
C++ (Qt)
struct CRefArc {
 TArcType mType;
 Node * mNode;
};
typedef QPair<Node *, CRefArc> TArcDataKey;   // ключ для поиска данных ссылки
typedef QHash<TArcDataKey, CArcData *> TArcDataHash;   // класс для хранения данных ссылок
Ну пока не знаю чем он хорош/плох. Пока вижу только что в использовании несколько неудобен - нужно смотреть чтобы key.first был именно чайлдом. Все-таки придется тащить базовый CArcData? Можно пережить но лучше бы без него.


Название: Re: Деревянный айтем
Отправлено: ssoft от Февраль 11, 2019, 16:36
Доделал реализацию Tree, код все там же (https://gitlab.com/ssoft-sandbox/prog.org.ru/tree-example).

Как и обещал, всё усложнилось в реализации ;D, но в использовании осталось всё по простому (на мой взгляд, конечно).

Узлы Node теперь реализуют классический parent-child, пример их отдельного использования в exampleParentChild.cpp.
Работает копирование/перемещение узлов и передача чайлдов.

Дерево осталось с наблюдателем. Из дерева можно извлечь узел со всей иерархией, далее можно перенести узел в другое дерево.
Также доступно копирование/перемещение узлов и передача чайлдов.

Кроме дерева, как я понял, требуется еще и направленный граф (Node|Edge).
Задачка тоже интересная сама по себе. Если найду в себе силы, сделаю и его.  ;)


Название: Re: Деревянный айтем
Отправлено: Igors от Февраль 14, 2019, 08:15
Доделал реализацию Tree, код все там же (https://gitlab.com/ssoft-sandbox/prog.org.ru/tree-example).

Как и обещал, всё усложнилось в реализации ;D,
Да, в этот раз я "ни асилил"  :)
..но в использовании осталось всё по простому (на мой взгляд, конечно).
Ну как... было бы прекрасно "просто пользоваться" не вникая в "детали реализации", но так не всегда выходит. Напр нод сцены удаляется, надо записать данные для undo, и вот уже, вероятно, (глубокого) изучения внутренностей не избежать. И это будет непросто. Хотя, справедливости ради, это довольно противная задачка для любой "деревянной" структуры, даже самой примитивной.
Кроме дерева, как я понял, требуется еще и направленный граф (Node|Edge).
Ну вообще-то не "кроме/еще" а он-то и требовался  :) Собсно чего я туда полез. Цель (которую я уже не раз озвучивал)

- для любого нода уметь находить "кто ссылается на него" и "на кого ссылается он".

Сейчас это решается просто членами класса, "голыми" указателями. Напр
Код
C++ (Qt)
struct  GeomGroup : public Node {
...
 Material * masterMaterial;
...
};
И .. это все! Если нужен список ссылающихся на какой-то Material (напр для того же undo), то пробегаемся по всем GeomGroup и находим всех с masterMaterial == this. Как ни странно, пока сцена невелика - такое свинство работает, но вот дальше тормоза, да и "поискового кода" не так уж мало. Ну и как решать? Прямолинейно
Код
C++ (Qt)
struct  Material : public Node {
...
 std::vector<GeomGroup *> materialUsers;  // список "ссылающихся"
...
};
Не, ну если бы эта зависимость была одна, то может так и сделать и забыть.Но их гораздо больше. А при ближайшем рассмотрении поддержка "списка ссылающихся" оказывается не такой уж дешевой.

Эта задача близка к "дереву", но не равна ей. Может быть N парентов и/или данные конкретной зависимости (хотя оба случаи очень редки). А главное - "фокус" на том что зависимостей "много" и всяких-разных. Поэтому думаю лучше сразу создавать деревянный контейнер что хранит все зависимости (а не распылять их "по деревьям"). Какие-то "внутренние ноды" неизбежны, но давать их наружу не следует, пользователь класса должен оперировать только с "зависимостями" (между парой нодов сцены).

Спасибо


Название: Re: Деревянный айтем
Отправлено: Авварон от Февраль 15, 2019, 18:00
А шо это ??? Киньте ссылочку если не затруднит. Спасибо

Ну кстати вот неплохая статья на русском (https://habr.com/ru/post/440388/).