Punteros inteligentes para modelar una estructura de árbol general y sus iteradores

Estoy modelando una estructura de árbol general al tener una clase para cada nodo con punteros a padre, primer hijo y primer hermano, más un puntero a último hermano (no es necesario, pero es útil). A esto, estoy agregando algunos datos extra atd. Mi implementación actual es:

class TreeNode { typedef boost::shared_ptr Ptr; typedef boost::weak_ptr WPtr; WPtr p2parent; ///< pointer to the parent node (NULL in the root) Ptr p2sibling; ///< pointer to the first sibling (or NULL) Ptr p2child; ///< pointer to the first child (or NULL) WPtr p2lastChild; ///< pointer to the last child (not strictly needed) }; 

Como puede ver, estoy usando shared_ptr para hermanos y niños, por lo que se puede eliminar todo el árbol simplemente eliminando su raíz. Para el puntero a padre, sé que no debería usar shared_ptr, ya que esto crearía ciclos, por lo que tengo que elegir entre weak_ptr y un puntero en bruto (TreeNode *): ¿alguna idea?

Para el puntero (opcional) al último elemento secundario, la opción es entre weak_ptr, shared_ptr y un puntero sin procesar: ¿cuál es la mejor opción para que toda la clase sea coherente internamente?

Finalmente, tengo un par de iteradores sobre la estructura, como un iterador primero en profundidad. ¿Qué punteros deben usar internamente los iteradores: puntero sin formato, weak_ptr o shared_ptr? ¿Cuáles son las ventajas de los tres enfoques?

shared_ptr es una exageración total: es un árbol, por lo que no hay propiedad compartida de los nodos. Cada nodo tiene un único propietario: su padre.

Si la implementación que está utilizando lo admite, debe usar std::unique_ptr para los dos punteros secundarios y para el puntero al nodo raíz. Si su implementación no es compatible con std::unique_ptr , puede usar std::auto_ptr pero querrá hacer que la clase de nodo no pueda copiarse explícitamente. En cualquier caso, puede usar un puntero en bruto para el puntero de nuevo al padre.

(Tenga en cuenta que deberá escribir un constructor de copia y un operador de asignación de copia para la clase de árbol, independientemente del tipo de puntero que use: los declarados implícitamente no tienen la semántica correcta).

Un iterador solo necesita un puntero en bruto al elemento al que apunta.

Para el puntero principal: debe asegurarse de que siempre apunte al principal real en los configuradores para los Treenode principal, por lo que agregar un unset al destructor Treenode es comparativamente simple. En cuyo caso bastará el puntero tonto.

Para el puntero del último niño: es aún más trabajo mantenerlo actualizado y, si lo hace, descubrirá que cubrió todos los casos y no necesita punteros inteligentes para ningún otro. Así que puntero tonto hará aquí también.

Puede usar weak_ptr por un poco de seguridad adicional, aunque realmente debería decir que no están vencidos, porque eso significa que se olvidó de cancelarlos y que probablemente no los administre correctamente.

Iteradores: Se debe utilizar el puntero inteligente.

  • Si usan shared_ptr , mantendrán el subárbol vivo incluso cuando modifique el árbol y lo desconecte.
  • Si usan weak_ptr , se invalidarán a sí mismos cuando se elimine el nodo puntiagudo (tendrá que verificar que el puntero aún sea válido en muchos lugares).

La elección depende de qué semántica quieras.