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

Question

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

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

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

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

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

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

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

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

0

c++data-structures pointers rust

Решение

Другие решения

Причина использования указателей, а не значений, заключается в том, что вы никогда не сможете определить свой 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 Члены …. вы можете видеть, куда это идет.

2

Источник

Accepted Answer

Пример Rust использует вектор потомков — он также может быть пустым.

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

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

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

2