Создание дерева с использованием std :: array

Question

Код внизу генерирует следующую ошибку времени компиляции. Ошибки исчезают, если я использую std::vector<Node> или std::array<unique_ptr<Node>, 3>. Может кто-нибудь объяснить, что это значит?

In file included from main.cpp:1:0: /usr/include/c++/4.9/array: In instantiation of ‘struct std::array’: main.cpp:9:23:
required from here /usr/include/c++/4.9/array:97:56: error: ‘std::array<_Tp, _Nm>::_M_elems’ has incomplete type typename _AT_Type::_Type _M_elems; ^main.cpp:3:7: error: forward declaration of ‘class Node’ class Node

#include <array> 

class Node 
{ 
public: 
    Node(Node* parent, int x) : parent_(parent), x_(x) {} 
    Node* parent_; 
    int x_; 
    std::array<Node, 3> children_; // ERROR 
}; 

Answer 1

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

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

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

Соответственно, используя std::array<Node, 3> внутри вашего Node определение не работает, потому что std::array ставит свою память в том же месте, как это было объявлено (в функции, что бы стек, в объекте, который был бы в самом объекте). Чтобы выяснить, сколько памяти необходимо, необходимо знать размер Node, и есть проблема.

Использование std::unique_ptr<Node> в порядке по той же причине, что и обычный указатель: указатель всегда имеет одинаковый размер.

Использование std::vector<Node> прекрасно (в принципе, но не обязательно на практике) по тем же причинам снова, но, возможно, менее очевидно, так: вы можете думать vector как имеющие 2 элементов данных, указатель на массив Node с и размер. Ключевой частью является указатель. Потому что только «дескриптор» в vector живет внутри памяти Node, и данные выделяются в другом месте, это прекрасный способ сохранить вещи.

Вероятно, лучший способ выразить свое намерение с учетом ограничений языка является: std::array<std::unique_ptr<Node>, 3>

Вы все еще не имеют фиксированное число детей, автоматическое управление памятью, и больше не работать в вопрос, не зная, как большой размер хранилища данных.

Для чего это стоит, это то же рассуждение, что позволяет идиома pimpl.

Answer 2

Node, очевидно, не может содержать три Nodes.
Это будет рекурсивное отношение, которое может закончиться только в одном из двух условий:

1. конец вселенной
2. она обманывает вас

Ваш выбор. ИМО не является оптимальным.

Answer 3

Вы пытаетесь объявить, что узел содержит элемент, который содержит 3 узла. Это просто невозможно, так как это неограниченная рекурсия.

std :: vector < Узел> работает, потому что векторы изначально пустые и добавляются динамически.

std :: array < std :: unique_ptr < Узел>, 3> работает, потому что этот тип массива содержит только указатели на объекты узла, а не сами объекты.