如何定义递归类型？

Question

我想要一份清单.列表中的条目将存储值以及迭代器到列表中的另一个条目.我该如何定义这种类型？它是这样的,但在语法上是正确的.

typedef list<pair<int, MyList::const_iterator>> MyList;

Answer 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;
};

编辑:正如TC提醒我的那样,实例化具有不完整类型的标准容器可能是未定义行为(一些标准库实现确实不保证).所以,让我们把所有这些推迟到以后.

编辑:那也无济于事.因此,验证您的std::list实现是否支持不完整的类型(或信任它这样做,它通常是诚实的),或使用Boost :: containers.

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

typedef Node_<> Node;

Answer 2

列表中的迭代器不仅不会因插入或删除其他元素而失效，而且这些迭代器指向的元素也将保持不变。因此我们可以这样做：

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

typedef list<Element> MyList;

这与您所要求的非常相似，但它second是一个指针而不是迭代器。如果您确实需要它作为迭代器，我们可以切换std::list<>为boost::intrusive::list<>（如果您不能使用Boost，则可以切换为自制的侵入式列表）。然后，value_type(ie Element) 实际上包含上一个/下一个指针，您可以将其用作迭代器。在Boost中，这被称为iterator_to()，解释如下：http://www.boost.org/doc/libs/1_43_0/doc/html/intrusive/obtaining_iterators_from_values.html