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

E>>Потому, как хранить можно только подветку, вынув её из дерева, и забыв о родителях.
S>В случае shared_ptr можно хранить и дерево и ветки как в сборе, так и отдельно вполне прозрачно. В том и прелесть.

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

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

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

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

E>>>Потому, как хранить можно только подветку, вынув её из дерева, и забыв о родителях.
S>>В случае shared_ptr можно хранить и дерево и ветки как в сборе, так и отдельно вполне прозрачно. В том и прелесть.

E>На самом деле не всё так радужно. GC сделать трудно. Зато не нужно.
E>Можно пойти по другому пути. Можно сделать свой указатель на ноду, который будет хранить счётчик сразу на дерево. Но я подозреваю, что это не то, что нужно, на самом-то деле.

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

Задача — построение задачеориентированной объектной модели для обработки XML. В частности из XML дерево и получается, но потом обрастает спецификой задачи, из атрибутов вырастают свойства, появляеются спецметоды обработки и т.п.

Смущает меня то, что если мы добавляем к дереву А ветку Б, то получим дерево. Если мы от дерева отнимем ветку Б, то мы ее уже не сможем приклеить к дереву В, т.к. она будет тут же удалена. Как-то не хочется различать операции удаления поддерева от отцепления поддерева.
Хочется что бы отодрал ветку — она жива. Бросил — уничтожилась.

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

S>Разве удаление объекта не нарушает его константность?
тут дело в не в смарт-пойнтерах. а в языке
удалять объект разрешено, если есть указатель на конст объект

const A* const ptr = new A();
delete ptr;

S>А сконвертировать shared_ptr<MyClass> в shard_ptr<const MyClass>?
сконвертить можно простым присваиванием вроде
можно и убирать конст (аналог const_cast для shared_ptr)
http://www.boost.org/doc/libs/1_41_0/libs/smart_ptr/shared_ptr.htm#const%5Fpointer%5Fcast

S>нет, речь не об универсальном дереве. Узел есть нечто вроде узла дерева XML. Пока они однотипны, но сейчас еще не видно, будет ли специализация.
S>На этом этапе хочется избежать ручной реализации освобождения.

Ввести сущность контейнер-дерева, который содержит в себе узлы. Это дополнительно помогает оптимизировать память. Можно считать контейнер за пул узлов. Каждый узел имеет ссылку на контейнер (или можно вычислить адрес контейнера, если это линейный кусок памяти). Сам контейнер имеет счётчик ссылок и соответственно адресация к узлам идёт через указатель с подсчётом ссылок, в котором пользуется счётчик контейнера.

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

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

S>>Разве удаление объекта не нарушает его константность?
U>тут дело в не в смарт-пойнтерах. а в языке
U>удалять объект разрешено, если есть указатель на конст объект
U>

U>const A* const ptr = new A();
U>delete ptr;
U>

По меньшей мере странно это выглядит. Изменять нельзя, удалять можно.

S>>А сконвертировать shared_ptr<MyClass> в shard_ptr<const MyClass>?
U>сконвертить можно простым присваиванием вроде
U>можно и убирать конст (аналог const_cast для shared_ptr)
U>http://www.boost.org/doc/libs/1_41_0/libs/smart_ptr/shared_ptr.htm#const%5Fpointer%5Fcast
спасибо за ссылку, не натыкался на такой метод.

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

S>Хочется что бы отодрал ветку — она жива. Бросил — уничтожилась.

Ну, то есть, ветки могут жить без дерева/без родителя? Я верно понял?

ну тогда делаешь просто.

1) На ноду в клиентском коде всегда указываешь через shared_ptr
2) Нода на своих детей тоже через shared_ptr указывает
3) Дети хранят в себе обычный указатель на родителя.
4) При добавлении подветки (в том числе и одинокой ноды) в дерево, в смысле в список детей какого-то родителя, родитель регится в своём новом ребёнке.
При отделении ребёнка в свободное плавание -- родитель разрегистрируется в ребёнке. И ребёнок становится сиротой.

то есть код метода AddChild будет какой-то такой:

void MyTree::AddChild( shared_ptr<MyTree> newChild )
{
    if( newChild->HasParent() ) {
        newChild->Detach();
    }
    children.push_back( newChild );
    newChild->setParent( this );
}

А в деструкторе MyTree каждому детю из children скажут setParent( 0 );\


Теперь то, что касается "исчезнет, как только я его оттуда достану". Если ты всё время будешь иметь shared_ptr на ноду, то она не исчезнет. Просто может осиротеть.

Ну и последнее. Я не знаю насколько большие деревья предполагаются, но если реально большие, то меня бы на shared_ptr задавила бы жаба. Можно же раздельнео владение со счётчиком и подешевле организовать!

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

S>>нет, речь не об универсальном дереве. Узел есть нечто вроде узла дерева XML. Пока они однотипны, но сейчас еще не видно, будет ли специализация.
S>>На этом этапе хочется избежать ручной реализации освобождения.

AS>Ввести сущность контейнер-дерева, который содержит в себе узлы. Это дополнительно помогает оптимизировать память. Можно считать контейнер за пул узлов. Каждый узел имеет ссылку на контейнер (или можно вычислить адрес контейнера, если это линейный кусок памяти). Сам контейнер имеет счётчик ссылок и соответственно адресация к узлам идёт через указатель с подсчётом ссылок, в котором пользуется счётчик контейнера.

До знакомства с дотнетом мне бы такое решение понравилось

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

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

А, понятно, что ты делаешь.
Я бы наверное использовал интрузивные счётчики "в стиле COM", а проблему слабого указателя на родителя решил бы тем, что родитель обнуляет указатель на себя у всех дочерних узлов (у него все равно есть этот список). Что-то типа такого:

struct node_t
{
    unsigned refcount_;
    node_t* parent_;
    std::vector<node_t*> children_;
    int data_;

    node_t(int data)
    {
        data_ = data;
        refcount_ = 1;
        parent_ = 0;
    }

    node_t* acquire()
    {
        ++refcount_;
        return this;
    }

    void release()
    {
        if (--refcount_ == 0)
            delete this;
    }

    void add_child(node_t* n)
    {
        assert(n->parent_ == 0);
        n->acquire();
        n->parent_ = this;
        children_.push_back(n);
    }

    ~node_t()
    {
        assert(parent_ == 0);
        for (auto child = children_.begin(); child != children_.end(); ++child)
        {
            assert((*child)->parent_ == this);
            (*child)->parent_ = 0;
            (*child)->release();
        }
    }
};

int main()
{
    node_t* n1 = new node_t (1);
    node_t* n2 = new node_t (2);
    node_t* n3 = new node_t (3);
    // собираем дерево
    n1->add_child(n2);
    n2->release();
    n1->add_child(n3);
    n3->release();

    // захватываем один из подузлов
    node_t* n4 = n2->acquire();

    // удаляем дерево, но наш узел пока живёт
    n1->release();

    // отпускаем наш подузел
    n4->release();
}

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

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

S>>Хочется что бы отодрал ветку — она жива. Бросил — уничтожилась.

E>Ну, то есть, ветки могут жить без дерева/без родителя? Я верно понял?
да

E>ну тогда делаешь просто.

E>1) На ноду в клиентском коде всегда указываешь через shared_ptr
E>2) Нода на своих детей тоже через shared_ptr указывает
E>3) Дети хранят в себе обычный указатель на родителя.
E>4) При добавлении подветки (в том числе и одинокой ноды) в дерево, в смысле в список детей какого-то родителя, родитель регится в своём новом ребёнке.
E>При отделении ребёнка в свободное плавание -- родитель разрегистрируется в ребёнке. И ребёнок становится сиротой.
да, что-то подобное я подразумевал в стартовом посте.

E>то есть код метода AddChild будет какой-то такой:

void MyTree::AddChild( shared_ptr<MyTree> newChild )

да, но предпочитаю передавать shared_ptr по константной ссылке, чтобы уменьшить передергивания счетчика.

E>Теперь то, что касается "исчезнет, как только я его оттуда достану". Если ты всё время будешь иметь shared_ptr на ноду, то она не исчезнет. Просто может осиротеть.
да, это я представляю.

E>Ну и последнее. Я не знаю насколько большие деревья предполагаются, но если реально большие, то меня бы на shared_ptr задавила бы жаба. Можно же раздельнео владение со счётчиком и подешевле организовать!
нет, реально не очень большие, жаба пока не давит.

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

S>да
S>да, что-то подобное я подразумевал в стартовом посте.
S>да, но предпочитаю передавать shared_ptr по константной ссылке, чтобы уменьшить передергивания счетчика.
S>да, это я представляю.
S>нет, реально не очень большие, жаба пока не давит.

Тогда не ясно в чём твои проблемы-то?

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

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

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

R>А, понятно, что ты делаешь.
R>Я бы наверное использовал интрузивные счётчики "в стиле COM", а проблему слабого указателя на родителя решил бы тем, что родитель обнуляет указатель на себя у всех дочерних узлов (у него все равно есть этот список).
Да, к интрузивным счетчикам я уже пришел, но ввожу их через базовый класс и таки указатель на объекты с интрузивынми счетчиками сделал умными.

А вот решение проблемы слабого родителя через удаление ссылки родителем мне показалось интереснее, чем впендюривание weak_ptr в интрузивный подсчет ссылок.

R>Что-то типа такого:
+1, только по-ближе к C++, чем к C.

R>

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

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

S>>да
S>>да, что-то подобное я подразумевал в стартовом посте.
S>>да, но предпочитаю передавать shared_ptr по константной ссылке, чтобы уменьшить передергивания счетчика.
S>>да, это я представляю.
S>>нет, реально не очень большие, жаба пока не давит.

E>Тогда не ясно в чём твои проблемы-то?

проблемы в потенциальной опасности нарушения целостности памяти путем случайного приведения shared_ptr<T> к T* и обратно. Дисциплина и порядок — это решение этой проблемы. Но оно не надежное. Т.е. решение надежное, но вот дисциплина у меня хромает. Рассеянный. Хочу что бы проблема не возникала в принципе, либо хоть компилятор бы принуждал к дисциплине. А он молчит

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

S>>>Разве удаление объекта не нарушает его константность?
U>>тут дело в не в смарт-пойнтерах. а в языке
U>>удалять объект разрешено, если есть указатель на конст объект
U>>

U>>const A* const ptr = new A();
U>>delete ptr;
U>>

S>По меньшей мере странно это выглядит. Изменять нельзя, удалять можно.

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

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

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

U>>>удалять объект разрешено, если есть указатель на конст объект

S>>По меньшей мере странно это выглядит. Изменять нельзя, удалять можно.

MD>Что же тут странного? Гарантируется, что в течение свой жизни const-экземпляр будет неизменным (ну, не считая хаков со всякими кастами-мутастами).
Если только считать что он умирает мгновенно не изменившись. Но из деструктора можно вызвать любой неконстантный метод, что делает смерть объекта не атомарной.

MD>Но также верно, что каждый порожденный экземпляр имеет конституционное право на смерть. Тут и сказке конец.
Странно что в этой сказке вершить приговор может любой.

S>Однако, есть ньюансы, связанные со спецификой shared_ptr, а точнее внешним хранением блока счетчиков ссылок по отношению к объекту. Нельзя создавать более одного shared_ptr по сырому указателю Node*.

S>Хотелось бы узнать, как принято работать с shared_ptr в таких случаях?
intrusive_ptr — и экономнее и проблему данную решает..

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

R>Я бы наверное использовал интрузивные счётчики "в стиле COM", а проблему слабого указателя на родителя решил бы тем, что родитель обнуляет указатель на себя у всех дочерних узлов (у него все равно есть этот список). Что-то типа такого:
...

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

struct node_t
{
    node_t* parent_;
    node_t* next_;
    node_t* children_;

ну или так:

struct node_t : intrusive_list_member<> // или какой нибудь intrusive_set если надо по детям поиск прикручивать
{
    node_t* parent_;
    intrusive_list<node_t> children_;

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

S>только вектор тут ни к чему, я бы как нибудь так сделал:

Согласен, так ещё лучше.

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

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

S>>только вектор тут ни к чему, я бы как нибудь так сделал:

R>Согласен, так ещё лучше.

А чем лучше?

Как-то странно. Вроде язык высокоуровневый считается, куча умных контейнеров и указателей в библиотеках.. А как доходит до банального дерева — приходится выпиливать его руками с нуля

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

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

S>>>только вектор тут ни к чему, я бы как нибудь так сделал:


S>Как-то странно. Вроде язык высокоуровневый считается, куча умных контейнеров и указателей в библиотеках.. А как доходит до банального дерева — приходится выпиливать его руками с нуля

Извиняюсь, пропустил intrusive_list<node_t>

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

S>Если только считать что он умирает мгновенно не изменившись. Но из деструктора можно вызвать любой неконстантный метод, что делает смерть объекта не атомарной.

Объект считается мёртвым, как только начал выполняться его деструктор.