如何定义递归类型？

我想要一个列表。列表中的条目将存储值以及迭代器到列表中的另一个条目。我如何定义这种类型？它会是这样的，但在语法上是正确的。如何定义递归类型？

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

来源

2014-08-29 delingren

+15

让我们倒退，我想我们可能会遇到XY问题。您想做什么？为什么你需要两种走链表的方法？图表会代替吗？ – OmnipotentEntity 2014-08-29 07:47:06

请注意，通过仅存储迭代器，您不能删除指向的节点（您也需要它的列表）。并从其他地方删除它将透明地使所述迭代器无效。你对此有过解释吗？ – Quentin 2014-08-29 07:49:37

这将是一个无限（模板类型）深度的类型... – Jarod42 2014-08-29 07:50:13

不仅将在不被其它元素被无效列表迭代器被插入或删除，但元件那些迭代器指向也将保持不变。因此，我们可以这样做：

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

typedef list<Element> MyList;

这非常类似于你问什么，但second是一个指针，而不是一个迭代器。如果你真的需要它是一个迭代器，我们可以将std::list<>转换为boost::intrusive::list<>（或者如果你不能使用Boost，则可以使用本地侵入列表）。然后，value_type（即Element）实际上将包含prev/next指针，并且可以将其用作迭代器。在加速，这就是所谓的iterator_to()，这里解释：http://www.boost.org/doc/libs/1_43_0/doc/html/intrusive/obtaining_iterators_from_values.html

来源

2014-08-29 07:56:21

'std :: list'的问题是你不能从一个指针到迭代器。而你可以用'boost :: multi_index :: iterator_to'来做到这一点。 – 2014-08-29 08:47:21

@MaximYegorushkin：是的，我在我的回答中非常明确地解释了这一点。尽管在这种情况下我会使用'intrusive'而不是'multi_index'。 – 2014-08-29 09:13:49

让我们把问题由内而外用户定义类型洒打破声明递归：

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 ::容器。

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

typedef Node_<> Node;

来源

2014-08-29 07:57:35 Quentin

这是我想要提出的答案，但没有。：）做得好。 – 2014-08-29 08:01:34

使用不完整的类型实例化std :: list（如你的例子中的Node）就是UB，尽管实际上你可能会逃避它。 – 2014-08-29 08:05:49

'typedef'没有实例化'std :: list'。在实际实例化时，Node将被完全定义。编辑：我会做一些关于该成员的研究。 – Quentin 2014-08-29 08:09:35

你可以做一个伎俩就是这样，如果你想：

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

顺便说一句，我喜欢约翰Zwinck的解决方案。

来源

2014-08-29 07:58:50

'l'不拥有'it'，那是非常不安全的。 – 2014-08-29 08:00:17

你可以通过转发声明你的元素来实现。

#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()}); 
}

来源

2014-08-29 08:44:18

使用boost::any或同等产品来存储iterator。由于迭代器往往很小，所以小对象优化将会启动，开销将很低。

来源

2014-08-29 21:19:18 Yakk

如何定义递归类型？

回答

相关问题