Rust中的侵入算法等價物

Question

我正在尋找Rust編程語言並試圖將我的C++思想轉換爲Rust。常見的數據結構，如列表和樹，以前已經用C++中的指針實現，我不確定在Rust中如何實現確切的等價物。我感興趣的數據結構是入侵算法，類似於Boost入侵庫中的數據結構，這些在嵌入式/系統編程中很有用。

Rust（Dlist）中的鏈接列表示例非常直截了當，但它使用容器類型，其中實際類型位於容器內部。我正在尋找的入侵算法有點反其道而行之：您有一個主要類型，其中列表節點被插入或繼承。

另外，Linux中着名的鏈表也是列表數據在結構成員中的另一個例子。這就像插入算法的Boost成員變體一樣。這使您可以多次使用您的類型在多個列表/樹中。這與Rust如何工作？

所以我不確定如何將這些設計模式轉換爲我習慣於在C/C++中使用的Rust。任何成功理解這一點的人？

Answer 1

Rust想要你考慮所有權和生命期。誰擁有成員，他們會活多久？

在Dlist的問題中，答案是'容器'。使用侵入算法沒有明確的答案。一個列表的成員可能會在另一個列表中重用，而其他列表中的成員可能會被第一個列表破壞。最終，你可能想要使用參考計數（std::sync::Arc）。

Answer 2

我認爲有兩種方法可以完成像Rust這樣的事情。讓我們來看看圖的實現，通常使用侵入式鏈接。

第一種方法依賴於Rc<RefCell<Node>>。你可以在這裏找到更多的細節：Graphs and arena allocation

第二種方法依賴向量索引。你可以在這裏找到更多的信息：Modeling Graphs in Rust Using Vector Indices。

我相信第二種方法更好，但我沒有做任何測試。