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

[Igors]

Добрый день

Банальная структурка

Код

C++ (Qt)
struct CTreeItem {
  QString m_name;     // имя 
  ...                           // .. еще данные айтема
  QVector<CTreeItem> m_child; // чайлдво
 
  CTreeItem * m_parent;   // ???
};
 

Вот этот m_parent - иметь его хочется, это делает айтем "самодостаточным" для многих операций.  Но получаем проблемы с копированием. Конечно их можно пережить, но нет ли лучшего решения?

Спасибо

[ssoft]

Тама то многажды раз здесь изъезженная)) 

На пальцах:
У класса есть данные (свойства - 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'ы не копируются, а создаются на основе данных другого, с указанием новых ассоциативных связей.

[Igors]

Тама то многажды раз здесь изъезженная)) 

Наверное "тема", но все равно - впервые слышу

Когда концы ассоциативных связей являются частью класса, имеет смысл разделить его на две функциональные части:
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;  
 

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

[Авварон]

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 ничем не плох.

[Авварон]

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

[Igors]

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

Не очень понял что имеется ввиду под "старым добрым". Отказаться от контейнера и добавить члены m_prev/m_next, что ли?

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

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

[Авварон]

Не очень понял что имеется ввиду под "старым добрым". Отказаться от контейнера и добавить члены m_prev/m_next, что ли?

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

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

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

[Авварон]

Чот быстро заглохло=)

[Igors]

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

Ну хорошо, попробуем сделать выводы:

- если хотим ссылаться на 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. Не много ли?

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

[Авварон]

Ну хорошо, попробуем сделать выводы:

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

Вывод неверный=)

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

Увы.

и, увы, с дефаулт конструктором.

Не обязательно

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

Хмммм, нам надо как-то передавать нового парента, блин, как же это сделать, не передавая нового парента?

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

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

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

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

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

Что значит "внешней"?

[Igors]

Если хотите сделать дерево на value-based классе - вперед, будет домашнее задание=)

Ну такого я сделать не смогу, поэтому, учитель, покажите мне как это делается  Спасибо

Ну а если серьезно, то почему бы не ответить просто и без затей, напр:

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

Что значит "внешней"?

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

[Авварон]

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

Как раз таки все эти новомодные цацки нужны чтобы код был читаемый а не как ваша каша с непонятным владением.
Мув явно говорит - владение передали дереву. метод слон(парент) - плохой, негодный метод. Я лично напишу две строки - выделить поддерево (слон без параметров) и вставить в поддерево в новое место (item->append/item->insert).
юник_птр избавляет от богомерзких qDeleteAll, по это то же самое, что "vector<Item>"
Все ваши проблемы что вы не можете разобраться кто чем владеет.

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

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

[Igors]

.. а не как ваша каша с непонятным владением.
...
Все ваши проблемы что вы не можете разобраться кто чем владеет.

Да как же "непонятным" если члены называются "m_parent" и "m_child"? Куда уж понятнее? И что толку здесь от unique_ptr - ведь обращаться к чайлду все равно как-то надо. И зачем затевать котовасию с move если можно просто извлечь указатель из одного контейнера и поместить в другой? (для того и делаем вектор указателей)

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

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

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

[Авварон]

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

Тогда зачем создавать тему про дерево, если вы хотите реализовать граф?? ВНЕЗАПНО у вас задача меняется.

[Igors]

А теперь следите за руками

Код:

std::unique_ptr<TreeItem> tree = getTree();

ВНЕЗАПНО, unique_ptr на айтем становится самотоятельным объектом ДЕРЕВА а не отдельным элементом (айтемом)

Код:

ObserverPointer<TreeItem> node = getNode();

ВНЕЗАПНО, ObserverPointer на айтем становится элементом дерева, а не деревом! Типа псевдо-"итератор".

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

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

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

Тогда зачем создавать тему про дерево, если вы хотите реализовать граф?? ВНЕЗАПНО у вас задача меняется.

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