Как я могу эмулировать определение рекурсивного типа в C ++?

Question

Вчера я задал следующий вопрос , воспроизведенный здесь для удобства;

"Для одного из моих проектов я действительно хотел сделать следующее (упростить до минимума);

struct Move
{
    int src;
    int dst;
};

struct MoveTree
{
    Move move;
    std::vector<MoveTree> variation;
};

Я должен признать, что предполагал, что это невозможно сделать напрямую, я думал, что вектор MoveTree внутри MoveTree будет верботен. Но я все равно попробовал, и это прекрасно работает. Я использую Microsoft Visual Studio 2010 Express.

Это портативный? Это хорошая практика? Мне есть о чем беспокоиться? "

В основном ответ сообщества был отрицательным, я не мог этого сделать, стандарт запрещает это, поэтому тот факт, что он работает, означает, что мне просто везет.

Итак, мой новый вопрос. Как я могу реализовать простую функциональность, которую я хочу, в легальном C ++, не добавляя целую кучу неприятных сложностей и боли?

Answer 1

Вам нужно будет использовать указатели и динамическое размещение. И вы должны использовать умные указатели, чтобы не пропустить ничего. boost::shared_ptr позволяет типу быть неполным, и поэтому это допустимо:

std::vector< boost::shared_ptr<MoveTree> > variation;

(я не знаю о 0x std::shared_ptr TBH, но оно должно быть таким же).

Answer 2

Вы можете использовать Boost Pointer Container Library . Это похоже на использование std :: vector, но контейнер владеет указателем, поэтому он будет уничтожать объекты.

Вы можете объявить это:

#include <boost/ptr_container/ptr_vector.hpp>
struct MoveTree{
  Move move;
  boost::ptr_vector<MoveTree> variation;
};

Теперь, если вы хотите добавить новый элемент, вы можете использовать:

variation.push_back(new MoveTree());

Теперь у контейнера есть указатель, и вы получаете его по ссылке, например:

variation[i].move.src = ...

Объект уничтожается при разрушении контейнера.

Answer 3

Если вы можете использовать неполный тип MoveTree в качестве параметра шаблона в любом шаблоне, то используйте одно из решений в других ответах (например, Cat Plus Plus), или просто используйте свое оригинальное решениеДобавьте несколько тяжелых комментариев и сделайте покаяние позже.

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

Ко времени определения класса реализации класс MoveTree будет завершен:

struct Move
{
    int src;
    int dst;
};

struct MoveTreeImpl;

struct MoveTree
{
    Move move;

    // Todo: Implement RAII here for the impl
    // Todo: Provide impl accessor functions here

private:
    MoveTreeImpl* impl;
};

struct MoveTreeImpl
{
    std::vector<MoveTree> variation;
};

В этом решении есть волосатые части:

Поскольку вы пытаетесь избежать прямого создания экземпляра любого шаблона с неполными типами, вам придется реализовать RAII вручную.Вы не получите помощь от std::scoped_ptr<MoveTreeImpl>, так как MoveTreeImpl также неполный.

Какая подпись у ваших функций доступа?Можете ли вы вернуть std::vector<MoveTree>& от средства доступа?Я не уверен в этом - мы стараемся избегать шаблонов, которые используют MoveTree напрямую.Это может отличаться, потому что это не элемент данных, но я не уверен:)

Редактировать:

Чтение немного больше и получение ответов отдругим пользователям, кажется, большая часть этой ерунды не нужна.Только стандартные контейнеры имеют ограничение.Вы могли бы реализовать pimpl с std:scoped_ptr<MoveTreeImpl>, и я думаю, что верните std::vector<MoveTree>& из функции доступа, оба без проблем.

Answer 4

У меня нет в наличии копии стандарта C ++, поэтому я не могу проверить стандарт, но вот проблема:

• Классы не могут содержать конкретные экземпляры самих себя, дажетранзитивно - например, struct foo { foo x; } является незаконным по очевидным причинам.В более общем смысле, вы не можете ссылаться на размер структуры ни в одном из ее членов, кроме тела функций-членов.
• Классы могут содержать указатели на себя - struct foo { foo *x; } идеально подходит

Таким образом, вопрос в том, определяет ли std::vector какие-либо элементы (кроме функций-членов), которые прямо или косвенно зависят от sizeof(MoveTree)?

Очевидно, что std::vector не может иметь статический член, равный MoveTree сам по себе, поскольку это будет означать, что пустой вектор вызывает конструктор MoveTree.Однако можно представить std :: vector с выровненной char inlineStorage[sizeof(MoveTree)] оптимизацией для одноэлементных векторов.Если оставить в стороне вопрос о том, может ли это улучшить производительность, то под рукой стоит вопрос, позволяет ли стандарт реализации использовать такой подход.

Тем не менее, это по-прежнему плохая идея по другой причине: поскольку векторы должны копироватьсяих элементы при изменении размера хранилища, плохая идея иметь элементы с дорогим конструктором копирования в векторе.Здесь у нас есть класс, конструктор копирования которого должен рекурсивно воссоздать все дерево.Было бы лучше использовать класс интеллектуальных указателей для косвенной ссылки на дочерние узлы, чтобы избежать этих издержек:

std::vector<boost::shared_ptr<MoveTree> > variation;
// in C++0x:
std::vector<std::shared_ptr<MoveTree> > variation;
// in C++0x you can also use for lower overhead:
std::vector<std::unique_ptr<MoveTree> > variation;
// you must then use this pattern to push:

variation.push_back(std::move(std::unique_ptr<MoveTree>(new MoveTree())));

Answer 5

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

struct Move
    {
        int src;
        int dst;
    };

struct MoveTree;

struct MoveTree
    {
        Move move;
        std::vector<MoveTree*> variation;
    };

Если вам требуется управление типом, используйте интеллектуальный указатель, который может обработатьты.

Оригинальный ответ на этот вопрос .