Рекурсивные структуры данных без использования указателей

Question

Во время моей степени бакалавра в CS я часто сталкивался с использованием рекурсивных структур данных. В C++ я всегда в конечном итоге с помощью указателей, чтобы мои структуры данных рекурсивных, так же как и то, что я хотел бы сделать в С.

Упрощенный пример может быть следующим:

struct Tree{ 
    int data; 
    struct Tree *left, *right; 
}; 

Однако, используя указатели, как правило, рискованная работа и требует много часов отладки и тестирования кода. Для этих ресусов я хотел бы знать, есть ли другой эффективный способ определения рекурсивных структур данных в C++.

В других языках программирования, как ржавчина, я видел такие вещи, как, что:

struct Node { 
    children: Vec<Node>, 
    node_type: NodeType, 
} 

Есть более безопасный и комфортабельный способ определения таких рекурсивных структур в C++. Одна из возможностей - использовать std :: Vector, но я не знаю о производительности метода.

Answer 1

В примере Rust используется вектор детей - это также может быть пустым.

В C++ переменная-член может быть объектом, указателем или ссылкой (опущена для простоты).

Поскольку объект узла не может быть использован непосредственно (это будет цикл бесконечно), и вы не хотите использовать указатель, ваши варианты:

• использовать вектор, а также (хотя для бинарного дерева это не самый удобный тип - вы могли бы, однако ограничить его в коде всегда из двух элементов),

• использовать карту (ключ может быть перечисление CHILD_LEFT, CHILD_RIGHT),

• пересмотреть использование указателей, или еще лучше: умный указатели (это выглядит как хороший вариант использования для обычного unique_ptrs).

Answer 2

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

struct Tree{ 
    int data; 
    struct Tree left, right; 
}; 

Пренебрегая отступы и т.д., можно приблизить размер Tree в

sizeof(Tree) == sizeof(int) + sizeof(Tree) + sizeof(Tree) 
//      ^data   ^left   ^right 

но вы можете видеть, что с Tree имеет два члена Tree, и те члены сами имеют два Tree членов, и те, есть два члена Tree .... вы можете видеть, где это происходит.