Здравствуйте, _hum_, Вы писали:

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

__>для двоичного не дольше O(N) — N -число узлов
Если структуру дерева хранить в std::vector, то рушить — O(1)

__>вы же предложили объекты (атрибуты узла) держать отдельно, делая на них ссылки. вот те объекты нужно будет как-то удалять при разрушении дерева и копировать при создании копии.

А когда будет не надо?
Ну и потом, данные узла тоже могут быть POD...

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

Здравствуйте, _hum_, Вы писали:

__>Erop, я же несколько раз повторил, что проблема — как все перевести на язык смартов ил признать, что смарты не смогут во всем заменить простые указатели.

IMHO, очевидно, что не могут...

Здравствуйте, _hum_, Вы писали:

__>затем, что библиотека сериализации cereal, которой я пользуюсь (да наверное и остальные)работает только с stl-овскими объектами, в частности, только с умными указателями.

1) Ну так это ограничение этой библиотеки же, а не языка?
2) Я не пользуюсь, поэтому не знаю. А нельзя, структуру сериализовывать самому, а данные библиотекой?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, _hum_, Вы писали:

__>>конечно, можно делать все, как хочешь. речь же шла о наиболее естественном (для задачи) представлении.
E>Ну я с того и начал, что хорошобы ответить на ряд вопросов "зачем?"... :shuffle

для графического задания flow-chart-а алгоритма

__>>для двоичного не дольше O(N) — N -число узлов
E>Если структуру дерева хранить в std::vector, то рушить — O(1)

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

__>>вы же предложили объекты (атрибуты узла) держать отдельно, делая на них ссылки. вот те объекты нужно будет как-то удалять при разрушении дерева и копировать при создании копии.

E>А когда будет не надо?

?

E>Ну и потом, данные узла тоже могут быть POD...

а могут и не быть. да и вообще дополнительна индирекция — это дополнительная головная боль (отслеживание синхронизации, усложнение копирования и т.п.)

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

"дьявол в деталях"

расскажите как вы видите это "просто и легко" (только желательно сперва прочитав наше обсуждение со Stanislav V. Z.)


__>>Erop, я же несколько раз повторил, что проблема — как все перевести на язык смартов ил признать, что смарты не смогут во всем заменить простые указатели.

E>IMHO, очевидно, что не могут...

откуда очевидно-то?

__>>затем, что библиотека сериализации cereal, которой я пользуюсь (да наверное и остальные)работает только с stl-овскими объектами, в частности, только с умными указателями.

E>1) Ну так это ограничение этой библиотеки же, а не языка?

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

E>2) Я не пользуюсь, поэтому не знаю.

да что там знать она просто гарантирует автоматическую сериализацию любого типа stl

E>А нельзя, структуру сериализовывать самому, а данные библиотекой?

самое сложное — это именно сериализация структуры дерева

Здравствуйте, _hum_, Вы писали:

__>>>конечно, можно делать все, как хочешь. речь же шла о наиболее естественном (для задачи) представлении.
E>>Ну я с того и начал, что хорошобы ответить на ряд вопросов "зачем?"... :shuffle

__>для графического задания flow-chart-а алгоритма

Это не ответы на вопросы "зачем"...
Чем плохо для этой графической вьюшки, все объекты отдать во владение дереву?
Ненужные узлы можно просто "терять", оставляя их во владении дерева.
При сериализации и копировании можно писать/копировать только дерево, что заменит GC...

__>если не считать еще и разрушение менеджера хранения (с его списком свободных вершин)
Оно будет вообще бесплатным...

E>>А когда будет не надо?

__>?

Ну мы рассматриваем несколько альтернатив же? В какой их них данные узлов не надо будет рушить?

__>а могут и не быть. да и вообще дополнительна индирекция — это дополнительная головная боль (отслеживание синхронизации, усложнение копирования и т.п.)

А ты делай копирование через интерфейс/абстракции дерева, и не будешь зависеть от реализации

__>"дьявол в деталях"

Там всё очень просто.
Например, если данные о структуре — пара int'ов, как я предлагал, то в одном хранишь число пустых ячеек в блоке, а в другом -- смещение не начало след. блока.

__>расскажите как вы видите это "просто и легко" (только желательно сперва прочитав наше обсуждение со Stanislav V. Z.)

E>>IMHO, очевидно, что не могут...

__>откуда очевидно-то?

Ну много откуда... Умные указатели автоматизируют управление владением и совместным использованием, но сфера применения указателей шире .
В любом случае INHO означает, что МНЕ, очевидно, и это так...

__>языка, потому что библиотека заточена под новый стандарт
Чушь. Это просто авторы библиотеки не предусмотрели сценарий, или ты не понял как они предлагали действовать в этом случае...

__>да что там знать она просто гарантирует автоматическую сериализацию любого типа stl
Как видишь, не любого...

__>самое сложное — это именно сериализация структуры дерева
Выносишь её в std::vector< node_offsets > и получаь сериализацию автоматом...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, _hum_, Вы писали:

__>>>>конечно, можно делать все, как хочешь. речь же шла о наиболее естественном (для задачи) представлении.
E>>>Ну я с того и начал, что хорошобы ответить на ряд вопросов "зачем?"... :shuffle

__>>для графического задания flow-chart-а алгоритма

E>Это не ответы на вопросы "зачем"...
E>Чем плохо для этой графической вьюшки, все объекты отдать во владение дереву?
E>Ненужные узлы можно просто "терять", оставляя их во владении дерева.
E>При сериализации и копировании можно писать/копировать только дерево, что заменит GC...

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

__>>если не считать еще и разрушение менеджера хранения (с его списком свободных вершин)
E>Оно будет вообще бесплатным...

бесплатным ничего не бывает. значит, объем у вас вырастет

E>>>А когда будет не надо?

__>>?

E>Ну мы рассматриваем несколько альтернатив же? В какой их них данные узлов не надо будет рушить?

всегда надо будет

__>>а могут и не быть. да и вообще дополнительна индирекция — это дополнительная головная боль (отслеживание синхронизации, усложнение копирования и т.п.)

E>А ты делай копирование через интерфейс/абстракции дерева, и не будешь зависеть от реализации



__>>"дьявол в деталях"

E>Там всё очень просто.
E>Например, если данные о структуре — пара int'ов, как я предлагал, то в одном хранишь число пустых ячеек в блоке, а в другом -- смещение не начало след. блока.

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


__>>языка, потому что библиотека заточена под новый стандарт
E>Чушь. Это просто авторы библиотеки не предусмотрели сценарий, или ты не понял как они предлагали действовать в этом случае...



__>>да что там знать она просто гарантирует автоматическую сериализацию любого типа stl
E>Как видишь, не любого...

любого. raw-ptr не входит в stl.

__>>самое сложное — это именно сериализация структуры дерева
E>Выносишь её в std::vector< node_offsets > и получаь сериализацию автоматом...

вместе со связным списком свободных блоков, а значит, дополнительным объемом

Здравствуйте, _hum_, Вы писали:

__>я потерял нить беседы. по-моему, я о том же и говорил, что мне удобнее, чтобы владельцем были не узлы, а сам объект, содержащий дерево.

Да, я тоже думаю, что это было бы удобнее, и юник-птры тут не нужны...

__>всегда надо будет
Тогда по этому параметру все схемы равны

__>ну, получается связный список, который, если хранить в том же массиве, что и дерево, даст вам при сериализации разрастание сериализованных данных

Ну, например, можно время от времени запускать GCкомпактификацию...

__>любого. raw-ptr не входит в stl.
Ну не важно...

__>вместе со связным списком свободных блоков, а значит, дополнительным объемом

И что с того? Это проблема? Обычно RAM дороже же диска?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, _hum_, Вы писали:

__>>ну, получается связный список, который, если хранить в том же массиве, что и дерево, даст вам при сериализации разрастание сериализованных данных

E>Ну, например, можно время от времени запускать GCкомпактификацию...

вввооот. а это уже лишнее время, лишний код...

__>>любого. raw-ptr не входит в stl.
E>Ну не важно...

важно, если речь про поддержку объектов сериализации

__>>вместе со связным списком свободных блоков, а значит, дополнительным объемом

E>И что с того? Это проблема? Обычно RAM дороже же диска?

проблема, что файл проекта станет большим, по почте не переслать, например.

Здравствуйте, _hum_, Вы писали:

__>вввооот. а это уже лишнее время, лишний код...
Лишний по сравнению с чем?

Можно просто копировать дерево обходом, например... Это же в любом случае нужно будет написать?

__>проблема, что файл проекта станет большим, по почте не переслать, например.
Ну, можно перед записью итерировать пустое место, и если оно большое -- компактифицировать, заменяя дерево на копию, созданную обходом дерева.

Ну, грубо говоря, пусть у нас дерево хранят в двух параллельных структурах — вектор из смещений + вектор из юник_птров на данные узлов, ну и индекса входа в список пустых.

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

Ну и тривиально сериализуем...

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

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, _hum_, Вы писали:

__>>вввооот. а это уже лишнее время, лишний код...
E>Лишний по сравнению с чем?

лишний по сравнению с изначальной задачей — создать сериализуемое дерево

E>Можно просто копировать дерево обходом, например... Это же в любом случае нужно будет написать?

в какой момент?

__>>проблема, что файл проекта станет большим, по почте не переслать, например.
E>Ну, можно перед записью итерировать пустое место, и если оно большое -- компактифицировать, заменяя дерево на копию, созданную обходом дерева.

E>Ну, грубо говоря, пусть у нас дерево хранят в двух параллельных структурах — вектор из смещений + вектор из юник_птров на данные узлов, ну и индекса входа в список пустых.

E>Ну и вместо копирующего конструктора в наивной реализации, в этой пишем очень похожий компактификатор, который заводит ещё один такой же объект, итерирует дерево рекурсивно, добавляя в массив ссылок, и перенося данные узлов, потом делаем swap, и всё лишнее разрушаем прозрачно для пользователя дерева...

E>Ну и тривиально сериализуем...

E>Я к тому, что возможны разные подход, стоит выбирать дизайн осознанно...

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

Здравствуйте, _hum_, Вы писали:

__>лишний по сравнению с изначальной задачей — создать сериализуемое дерево
Ну конструктор копии у дерева предполагался? Компактификатор — это конструктор копии, написанный через итерацию дерева...

__>в какой момент?
Ну, если парит именно размер файла, то перед записью смотреть, как много есть свободных блоков. Если слишком много, то компактифицировать.
Можно завести счётчик числа свободных блоков, и при освобождении блоков (пополнении списка пустых) его увеличивать, а при аллокации уменьшать, и если пустых слишком много, то и компактифицировать...

__>спасибо, но мне всего лишь нужно было организовать обычное сериализуемое дерево, а тут получается я еще буду тратить уйму времени на написание и отладку всех этих компактификаторов, менеждеров и прочую лабуду. я же изначально и поднял эту проблему — думал, что с приходом с++11 все значительно упростилось. ан нет. оказывается, ничего подобного.

Компактификатор — это просто конструктор глубокой копии. Менеджер -- просто список на маркерах.
Что там писать?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, _hum_, Вы писали:

__>>лишний по сравнению с изначальной задачей — создать сериализуемое дерево
E>Ну конструктор копии у дерева предполагался? Компактификатор — это конструктор копии, написанный через итерацию дерева...

ну это же обман. конструктор копии на то и конструктор копии, чтобы давать КОПИЮ (КЛОН), а не "компактифицированный вариант"


__>>спасибо, но мне всего лишь нужно было организовать обычное сериализуемое дерево, а тут получается я еще буду тратить уйму времени на написание и отладку всех этих компактификаторов, менеждеров и прочую лабуду. я же изначально и поднял эту проблему — думал, что с приходом с++11 все значительно упростилось. ан нет. оказывается, ничего подобного.

E>Компактификатор — это просто конструктор глубокой копии. Менеджер -- просто список на маркерах.
E>Что там писать?

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

Здравствуйте, _hum_, Вы писали:

__>При попытке перевести все на язык смартов возникают трудности: если делать на unique_ptr (что достаточно логично), то непонятно, как быть с указателем на родителя. Если же делать на shared_ptr / weak_ptr, то нарушается логика владения. Как в таком случае быть?
Используй raw pointer для родителя. С другой стороны вопрос, зачем тебе нужен указатель на родителя?
__>p.s. T4r4sB, это же вы, по-моему, недавно говорили, что raw-ptr устарели
Они не устарели, просто с ними надо быть очень внимательным и понимать где, когда и зачем будет использоваться код, учитывать появления исключений и многопоточность.

Здравствуйте, _hum_, Вы писали:

__>>>лишний по сравнению с изначальной задачей — создать сериализуемое дерево
E>>Ну конструктор копии у дерева предполагался? Компактификатор — это конструктор копии, написанный через итерацию дерева...

__>ну это же обман. конструктор копии на то и конструктор копии, чтобы давать КОПИЮ (КЛОН), а не "компактифицированный вариант"

Почему обман? Код, который так бы ты поместил в конструктор копии, поместишь в компактификатор, а конструктор копии, как и сериализатор, будут тривиальными...

__>ну да, по мелочевке кажется ерунда, но этой мелочевки набирается очень много, и каждая требует учета и отладки.

По идее код глубокого копирования обходом дерева в любой реализации будет, тут экономии не выйдет. Просто в одной он будет помещён в компактификатор, а в другой в конструктор копии.
Так что получаем размен конвертилки видов дерева, как у тебя, что гарантирует перерасход памяти в 100%, против тупейшего менеджера блоков...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, _hum_, Вы писали:

__>>>>лишний по сравнению с изначальной задачей — создать сериализуемое дерево
E>>>Ну конструктор копии у дерева предполагался? Компактификатор — это конструктор копии, написанный через итерацию дерева...

__>>ну это же обман. конструктор копии на то и конструктор копии, чтобы давать КОПИЮ (КЛОН), а не "компактифицированный вариант"

аа, вы наверное имели в виду, что нынешний мой конструктор копии — это в вашем варианте компактификатор. тогда понятно.

E>Почему обман? Код, который так бы ты поместил в конструктор копии, поместишь в компактификатор, а конструктор копии, как и сериализатор, будут тривиальными...

__>>ну да, по мелочевке кажется ерунда, но этой мелочевки набирается очень много, и каждая требует учета и отладки.

E>По идее код глубокого копирования обходом дерева в любой реализации будет, тут экономии не выйдет. Просто в одной он будет помещён в компактификатор, а в другой в конструктор копии.
E>Так что получаем размен конвертилки видов дерева, как у тебя, что гарантирует перерасход памяти в 100%, против тупейшего менеджера блоков...

выделенное не понял — какой перерасход памяти?

Здравствуйте, Kernan, Вы писали:

K>Здравствуйте, _hum_, Вы писали:

__>>При попытке перевести все на язык смартов возникают трудности: если делать на unique_ptr (что достаточно логично), то непонятно, как быть с указателем на родителя. Если же делать на shared_ptr / weak_ptr, то нарушается логика владения. Как в таком случае быть?
K>Используй raw pointer для родителя. С другой стороны вопрос, зачем тебе нужен указатель на родителя?

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

__>>p.s. T4r4sB, это же вы, по-моему, недавно говорили, что raw-ptr устарели
K>Они не устарели, просто с ними надо быть очень внимательным и понимать где, когда и зачем будет использоваться код, учитывать появления исключений и многопоточность.

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

Здравствуйте, _hum_, Вы писали:

__>выделенное не понял — какой перерасход памяти?

Ну я так понял, что ты под сериализацию строишь другое дерево? Или что ты делаешь вместо прошивания дерева руками после загрузки?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, _hum_, Вы писали:

__>>выделенное не понял — какой перерасход памяти?

E>Ну я так понял, что ты под сериализацию строишь другое дерево? Или что ты делаешь вместо прошивания дерева руками после загрузки?

аа, ну так озу нас не волнует

Здравствуйте, _hum_, Вы писали:

__>аа, ну так озу нас не волнует
Ну, тогда, можно компактифицировать перед записью дерево с любым непустым списком свободных блоков... Это явно не дороже создания копии с другой структурой

Здравствуйте, _hum_, Вы писали:

__>ясно же, зачем, чтобы иметь возможность выполнения быстрой вставки, например.
Что такое "быстрая вставка" в бинарное дерево?