Как определить рекурсивный тип?

Ответ 1

Позвольте превратить проблему наизнанку с помощью опрыскивания пользовательских типов, чтобы разбить рекурсию объявлений:

struct Node {
    int _value;
    std::list<Node>::const_iterator _next;
};

Если вы хотите использовать typedef, вы можете:

struct Node;
typedef std::list<Node> NodeList;

struct Node {
    int _value;
    NodeList::const_iterator _next;
};

Изменить: Как T.C. напомнил мне, что создание стандартных контейнеров с неполными типами может быть Undefined Behavior (некоторые стандартные реализации библиотеки этого не гарантируют). Итак, отложите все это до более поздней точки.

Изменить: Ну, это тоже не помогает. Итак, убедитесь, что ваша реализация std::list поддерживает неполные типы (или доверяет ей сделать это, это часто работает честно) или использовать Boost:: контейнеры.

template <class = void>
struct Node_ {
    int _value;
    typename std::list<Node_>::const_iterator _next;
};

typedef Node_<> Node;

Ответ 2

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

struct Element {
  int first;
  Element* second;
};

typedef list<Element> MyList;

Это очень похоже на то, что вы просили, но second - это указатель, а не итератор. Если вам действительно нужно, чтобы он был итератором, мы можем отключить std::list<> для boost::intrusive::list<> (или встроенный интрузивный список, если вы не можете использовать Boost). Тогда value_type (т.е. Element) на самом деле будет содержать указатели prev/next, и вы можете использовать это как итератор. В Boost, который называется iterator_to(), объясняется здесь: http://www.boost.org/doc/libs/1_43_0/doc/html/intrusive/obtaining_iterators_from_values.html

Ответ 3

Вы можете сделать такой трюк, если хотите:

typedef list<pair<int, void*> > MyList;
typedef list<pair<int, void*> >::const_iterator MyListIterator;

int main() {
    MyList l;
    MyListIterator it;
    pair<int, void*> p(2, &it);
    l.push_back(p);
}

Кстати, я предпочитаю решение Джона Звинка.

Ответ 4

Вы можете добиться этого, перейдя вперед, объявив свой элемент.

#include <list>

struct Element;
typedef std::list<Element> ElementList;

struct Element
{
    int value;
    ElementList::iterator element;
};

int main() {
    ElementList l;
    l.push_back({0, l.end()});
    l.push_back({1, l.begin()});
}

Ответ 5

Используйте boost::any или эквивалент, чтобы сохранить iterator. Поскольку итераторы имеют тенденцию быть маленькими, оптимизация небольших объектов будет наноситься, а накладные расходы будут низкими.