如何定義遞歸類型？

我想要一個列表。列表中的條目將存儲值以及迭代器到列表中的另一個條目。我如何定義這種類型？它會是這樣的，但在語法上是正確的。如何定義遞歸類型？

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

如何定義遞歸類型？

回答

相關問題