Деревянный айтем

[Авварон]

Вот для членов класса подчеркнуть (дать понять) владение - дело хорошее. Но для всего-всего - думается перегиб. Для возвращаемого значения смысл  может быть довольно расплывчатым. Напр в первом случае (возврат 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 (или нулей).
Это можно решить "списками" - хранить массив вершин а в нем список (или другой массив) вершин, до которых можно дойти напрямую. Тут сложнее удаление ребер, кроме того, больше аллокаций (и, возможно, менее кэш-френдли).

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

[Igors]

Вообще-то 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" ясно показывает что это созданная копия. И чего было калечить простой и совершенно нормальный код? 

[Igors]

Ну давайте теперь прот граф поговорим. Итак, графы бывают ..

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

Два 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 - всего лишь один из возможных связей.

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


 

[ViTech]

В то же время прототип 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)

[Igors]

Т.е. Вы по имени функции можете определить, берёт она владение или нет .

В общем случае - нет, в конкретном случае выше - да. Как-то Вы зациклились исключительно на "владении" как будто других дел нет 

[ViTech]

В общем случае - нет, в конкретном случае выше - да. Как-то Вы зациклились исключительно на "владении" как будто других дел нет 

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

[Авварон]

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

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

[Igors]

Если бы все вокруг решали вашу задачу..

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

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

Я достаточно часто меняю конторы

Я догадываюсь почему

[ViTech]

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

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

[Авварон]

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

Прикиньте, да, далеко не все работают с 3д графикой. Более скажу - я никогда не работал с 3д графикой. У меня никогда не было задачи "повернуть объект". Серьезно, пока вы перемножали матрицы поворота, я решал другие задачи. Совершенно другие.
И пусть вас не смущают мои вопросы в разделе 3д графики, это для самообразования.

нужно разработать структуру данных, т.е. работа чисто программистская

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

такая задача может возникнуть в любой предметной области.

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

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

Я вообще-то вам тоже самое и сказал. Привел пяток реализаций графа и спросил - вам какой? Вы не ответили. Даже не заметили судя по всему, так как уперлись в свою реализацию на указателях.

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

[Igors]

Прикиньте, да, далеко не все работают с 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). Как тогда мы будем искать парент/чайлд для нашего айтема?

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

[Авварон]

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

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

[Igors]

Еще раз - вам надо несколько графов.
Для простоты - у вас есть графиксцена (дерево). Это дерево управляет временем жизни. И только временем жизни!

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

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

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

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

[ViTech]

Мне нужна структура данных для хранения связей которые могут быть очень разнообразны.

Вы все объекты хотите в одно дерево/граф засунуть? Ну получится граф из 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 пихать в одно дерево? Что у них общего?

Мы тут ещё немного попереписываемся, но, скорей всего, в конечном итоге всё вернётся на круги своя . С таким же результатом.

[Igors]

Есть 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)?

Мы тут ещё немного попереписываемся, но, скорей всего, в конечном итоге всё вернётся на круги своя . С таким же результатом.

Ну это я тоже знаю Потом неожиданно выяснится что Вы "что-то предлагали", а я никак не смогу вспомнить а что же?