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

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

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

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

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

insert(TNode* pNodeWhere) за O(1)

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

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

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

insert(TNode* pNodeWhere) за O(1)

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

"ваши доказательства" (с)

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

__>>>ясно же, зачем, чтобы иметь возможность выполнения быстрой вставки, например.
K>>Что такое "быстрая вставка" в дереве? Любая вставка в дерево начинается с поиска.
__>insert(TNode* pNodeWhere) за O(1)
И куда ты это вставишь? Мне кажется есть только одн оместо для этого .
__>>>в том смысле, что в "будущем ими пользоваться практически не будут, и все заменят умные"
K>>Ну ерунда же.
__>"ваши доказательства" (с)
Совместимость с С.

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

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

__>>>>ясно же, зачем, чтобы иметь возможность выполнения быстрой вставки, например.
K>>>Что такое "быстрая вставка" в дереве? Любая вставка в дерево начинается с поиска.
__>>insert(TNode* pNodeWhere) за O(1)

K>И куда ты это вставишь? Мне кажется есть только одн оместо для этого .

список — частный случай дерева, но ставка там не в одно место: std::list::insert

__>>>>в том смысле, что в "будущем ими пользоваться практически не будут, и все заменят умные"
K>>>Ну ерунда же.
__>>"ваши доказательства" (с)
K>Совместимость с С.

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

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

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

Если делать по-человечески, то все узлы дерева должны использовать общий счётчик ссылок: пока есть хоть один указатель на хоть один узел дерева, всё дерево остаётся живым.

Кстати, shared_ptr такое умеет: держать счётчик на один объект, а указатель на другой, жизненно связанный с ним.

struct A {
  B subordinate;
};

shared_ptr<A> pa = make_shared<A>();
shared_ptr<B> pb(&pa->subordinate, pa);
pa.reset(); // но pb, а через него и весь объект A, продолжает жить!
pb.reset(); // теперь А умрёт и по-человечески убъёт B своим деструктором

В нашем случае это ненужное знание, но — так, к слову, вдруг кто не знает. Фича-то полезная.

Проблема возникает тогда, когда мы отцепляем поддерево. Теперь указатели на отцепленное поддерево должны мысленно переключиться на новый счётчик.
И тут есть два варианта решений
— или пропатчить все указатели (что теоретически возможно, если это linked_ptr'ы — но, понятное дело, это не потокобезопасно; с другой стороны, расковыр дерева должен происходить в критической секции, так что какие-то компромиссы здесь могут быть)
— или сделать довольно хитрую механику подсчёта ссылок, больше похожую на интрузивные указатели.

Давайте рассмотрим это поподробнее.

Пусть каждый узел знает, сколько на него есть указателей со стороны — как непосредственно на него, так и на нижележащие. Внутренние указатели в зачёт не идут.

struct Node {
  Node *up, *lt, *rt;
  unsigned refcount;
};

bool is_alive(Node const* node) {
  assert(node);
  return node->up || node->refcount;
}

void delete_subtree(Node* node) {
  if (!node) return;
  delete_subtree(node->left);
  delete_subtree(node->right);
  delete node;
}

void try_delete(Node* node) {
  if (node && !is_alive(node)) delete_subtree(node);
}

void incref_impl(Node* node, int delta) {
  if (delta == 0) return;
  Node* top = nullptr;
  // бежим вверх по дереву
  while(node) {
    top = node;
    node->refcount += delta;
    node = node->up;
  }
  // если корень дерева отсох, удаляем его
  if (delta < 0) try_delete(node);
}

void intrusive_addref(Node* node) { incref_impl(node, +1); }
void intrusive_decref(Node* node) { decref_impl(node, -1); }

void cut_left(Node* node) {
  assert(node && node->left);
  Node* left = node->left;
  // разрываем связь
  left->up = nullptr;
  node->left = nullptr;
  // и отнимаем ставшие неродными счётчики
  incref_impl(node, -left->refcount);
  try_delete(left);
}

void attach_left(Node* node, Node* left) {
  assert(node && !node->left);
  assert(left && !left->up);
  // добавляем счётчики
  incref_impl(node, +left->refcount);
  // и создаём связь
  left->up = node;
  node->left = left;
}

(disclaimer. код эскизный, чисто для иллюстрации; писал "с листа", мог и напутать, поэтому не судите строго)

Проблема здесь в том, что цена каждого присоединения указателя — O(H), где H — высота дерева. Плюс неизбежные кешмиссы.

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

bool is_alive(Node* node) {
  return node->refcount || (node->left && is_alive(node->left)) || (node->right && is_alive(node->right));
}

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

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

К>Если делать по-человечески, то все узлы дерева должны использовать общий счётчик ссылок: пока есть хоть один указатель на хоть один узел дерева, всё дерево остаётся живым.

... и далее следует небольшой комментарий к утверждению "благодаря shared_ptr, C++ стало так же удобно пользоваться, как языками с GC"

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

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

__>insert(TNode* pNodeWhere) за O(1)


ничего не понял.
1) TNode* -- это типа итератор узлов да? Что мешает хранить в нём указатель на отца тоже?
2) Дерево, как я понял, бинарное? То есть у любого узла, не являющегося листом, два сына.

Вот у нас есть узел node, у неге дети left, right, я хочу туда вставить узел toAdd, кто кого в результате усыновит?
В бинарном дереве просто так узел не добавишь, так как узлов всегда на 1 меньше, чем листьев. Так что надо всегда добавлять лист, узел, и что-то перестраивать, например перебалансировывать...
Ну это если дерево не за один проход строится, а инкрементально...

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

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

K>>>>Что такое "быстрая вставка" в дереве? Любая вставка в дерево начинается с поиска.
__>>>insert(TNode* pNodeWhere) за O(1)
K>>И куда ты это вставишь? Мне кажется есть только одн оместо для этого .
__>список — частный случай дерева, но ставка там не в одно место: std::list::insert
Одна история ох...ее другой. Ладно, проехали.

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

BZ>... и далее следует небольшой комментарий к утверждению "благодаря shared_ptr, C++ стало так же удобно пользоваться, как языками с GC"

У языков с GC нет причин для того, чтобы различать составной объект (которым является всё дерево) и его мелкие детали (узлы). Мусороуборщик сам разберётся.
Но вообще, это архитектурное искушение.
Которое выстреливает, например, если один поток (или одна сопрограмма, или один уровень вызова) занимается забегом по дереву, а второй в это время отчекрыживает ветку.

Так что органические ограничения shared_ptr немножко дисциплинируют.

А если эти ограничения реально мешают, то придётся так или иначе отказываться от shared_ptr — включая использование собственных (велосипедных или нормальных) мусороуборщиков.

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

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

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

__>>insert(TNode* pNodeWhere) за O(1)


E>ничего не понял.
E>1) TNode* -- это типа итератор узлов да? Что мешает хранить в нём указатель на отца тоже?

не итератор, а указатель на узел. получен он может быть, например, из графического представления узла (каждый графический элемент, представляющий блок, будет содержать указатель на узел, который он представляет) [напоминаю, речь о графическом представлении flow-chart-а]


E>2) Дерево, как я понял, бинарное? То есть у любого узла, не являющегося листом, два сына.

не два сына (речь не о полном дереве), а не более двух и специфическое

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

__>не два сына (речь не о полном дереве), а не более двух и специфическое
R-дерево?

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

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

__>>не два сына (речь не о полном дереве), а не более двух и специфическое
K>R-дерево?

с чего вы взяли?

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

К>Если делать по-человечески, то все узлы дерева должны использовать общий счётчик ссылок: пока есть хоть один указатель на хоть один узел дерева, всё дерево остаётся живым.

Почему?
Это нужно далеко не во всех задачах.

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

К>>Если делать по-человечески, то все узлы дерева должны использовать общий счётчик ссылок: пока есть хоть один указатель на хоть один узел дерева, всё дерево остаётся живым.

TB>Почему?
TB>Это нужно далеко не во всех задачах.

Если дерево извне представлено цельным объектом, то должны быть владеющие указатели на дерево (не на корневой узел, а именно на дерево, распоряжающееся корневым узлом и всеми прочими узлами) и голые указатели/итераторы на узлы. Которые инвалидируются, если соответствующие узлы умерли (или даже если они перемещены каким-то внезапным способом — тут уже всё зависит от контракта итератора).
Самое малое, что можно сделать в этих условиях — это внутренние связи сделать на shared_ptr/weak_ptr, чтобы получить автоматическое разрушение, а внешние указатели (из итераторов) — на weak_ptr, чтобы инвалидацию можно было диагностировать.

Если же нужно более-менее локально работать с поддеревьями, то придётся изобретать изощрённые механизмы сборщика мусора.
Будь то каскадные счётчики, или предсмертный обход, или ещё что-то.

И, возможно, смотреть в сторону чисто функциональных структур данных — версионных неизменяемых деревьев. Чтобы, если в одном месте ковыряемся, это не затронуло другие места...

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

__>Раньше на raw-ptr узел дерева, если говорить о двоичном варианте, выглядел
__>

__>struct TNode
__>{
__>   TAtrributes m_Atrributes;

__>   TNode* m_pLeftChild;
__>   TNode* m_pRightChild;

__>   TNode* m_pParent;
__>};
__>

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

__>p.s. T4r4sB, это же вы, по-моему, недавно говорили, что raw-ptr устарели

Бустовые shared_ptr + weak_ptr должны спасти отца русской демократии. Надо лишь для себя определиться с семантикой, кто будет владеть shared-указателем на кого (родитель на дочерних или дочерние на родителя), тогда weak должен будет использоваться в обратном направлении. Оба варианта имеют право на жизнь, в зависимости от предполагаемых сценариев.

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

К>Если дерево извне представлено цельным объектом, то должны быть владеющие указатели на дерево (не на корневой узел, а именно на дерево, распоряжающееся корневым узлом и всеми прочими узлами) и голые указатели/итераторы на узлы. Которые инвалидируются, если соответствующие узлы умерли (или даже если они перемещены каким-то внезапным способом — тут уже всё зависит от контракта итератора).

Сложновато как-то, в СТЛ сколько деревьев, и ни одно из них не отвечает за итераторы, ссылающиеся на узлы. Выходит из зоны видимости — и сразу дохнет со всеми узлами.

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

TB>Здравствуйте, Кодт, Вы писали:

К>>Если дерево извне представлено цельным объектом, то должны быть владеющие указатели на дерево (не на корневой узел, а именно на дерево, распоряжающееся корневым узлом и всеми прочими узлами) и голые указатели/итераторы на узлы. Которые инвалидируются, если соответствующие узлы умерли (или даже если они перемещены каким-то внезапным способом — тут уже всё зависит от контракта итератора).

TB>Сложновато как-то, в СТЛ сколько деревьев, и ни одно из них не отвечает за итераторы, ссылающиеся на узлы. Выходит из зоны видимости — и сразу дохнет со всеми узлами.

Как раз ничего сложного. Именно это я и сказал: дерево — объект, узлы — детали реализации, итераторы — сами себе злые буратины.
Хочешь распределённо владеть деревом — делай shared_ptr на дерево.

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

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

__>>Раньше на raw-ptr узел дерева, если говорить о двоичном варианте, выглядел
__>>

__>>struct TNode
__>>{
__>>   TAtrributes m_Atrributes;

__>>   TNode* m_pLeftChild;
__>>   TNode* m_pRightChild;

__>>   TNode* m_pParent;
__>>};
__>>

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

__>>p.s. T4r4sB, это же вы, по-моему, недавно говорили, что raw-ptr устарели

MD>Бустовые shared_ptr + weak_ptr должны спасти отца русской демократии. Надо лишь для себя определиться с семантикой, кто будет владеть shared-указателем на кого (родитель на дочерних или дочерние на родителя), тогда weak должен будет использоваться в обратном направлении. Оба варианта имеют право на жизнь, в зависимости от предполагаемых сценариев.

а что в бусте семантика shared_ptr + weak_ptr отлична от семантики stl-ксих аналогов?

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

__>а что в бусте семантика shared_ptr + weak_ptr отлична от семантики stl-ксих аналогов?

Это они самые и есть.