如何在節點類中實現節點引用

Question

我想在C++中編寫一個quadedge類（將它想象成某種圖）。每個節點都應該跟蹤他的鄰居。我必須只跟蹤傳出的弧線。

第一個想法就是用指針來做到這一點：

struct Node { 
     //.... 
     Node * n1,n2,... nk; 
}; 

然而，這種方法是particullary痛苦時，你必須實現一個拷貝構造函數^*（先複製所有的節點，然後映射每指向舊節點的指針指向新節點的相對指針）。

我認爲在這種情況下使用整數索引而不是指針會更好。

struct Node { 
     //.... 
     int n1,n2,...nk; 
}; 

這種方法是否通用且正確？ 如果是，哪個是將索引映射到節點的適當容器？

std::vector<Node>可能是最有效的方法，我可以只使用向量中的索引來引用一個節點，但不幸的是從圖中刪除一個節點會非常複雜（需要將每個引用放入圖形）。

使用std::unordered_map<int,Node>會稍微好一點，但它仍然需要跟蹤自由名稱（如果我插入節點1,2,3然後刪除2，我需要跟蹤事實名稱2可用）。

我需要的是非常類似於堆的實現。考慮一個池分配器，它使用來自其基址的偏移量作爲指針類型。

是否有像這樣的流行容器（在Boost或任何其他流行庫中）？

_{*它的實用性並不侷限於拷貝構造函數，想想系列化例如}

Answer 1

使用int索引進入容器永久是脆弱的，因爲您不能刪除或插入容器中間的項目，而無需重新洗淨所有索引。在複製或序列化操作期間臨時使用索引要好得多：如第一種方法中所述，使用指針來進行不依賴於節點標識的操作，並僅爲節點創建臨時標識（如索引）需要操作的持續時間。

例如，在複製構造函數中開始複製操作之前，請創建一個vector<Node*>和unordered_map<Node*,int>。執行兩遍複製：首先，將沒有對矢量的引用的節點的副本以及舊節點的地址添加到地圖中。然後再次遍歷節點，並使用無序映射中的索引查找向量中新節點的地址來解析引用。

Answer 2

我想介紹一個節點ID的這個新概念只會讓你的生活困難。

如果您需要每個節點序列化的唯一標識符，請在此時創建標識符或僅將節點地址轉換爲int。

如果要複製圖形，可以創建一個臨時std :: unordered_map，將舊節點映射到新節點以跟蹤哪些節點已被複制。

深度複製節點的函數將是遞歸的;它會將舊節點和新節點添加到地圖中，然後深度複製尚未在地圖中的任何鄰居節點。