在鏈表中應該用哪種智能指針比較合理？

剛學 c++， 想用 智能指針寫個鏈表練習一下。

粗略分為單鏈表和雙向鏈表的情況。自己用 unique_ptr 的方式，感覺並不如裸指針方便，但又想有智能指針般的內存管理。

一開始我的方案是

class Node
{
public:
ValueType value;
unique_ptr& next;
Node(ValueType value_ = 0, unique_ptr& next_ = nullptr)
: value(value_), next(move(next_))
{}
};


但是覺得這樣的話，它的 head 還是要 new 出來，我想盡量避免 new 的操作。

後來把每個結點都當做 unique_ptr，但是有些鏈表相關的操作（比如排序，除重）需要返回頭結點。

如果返回 unique_ptr 的形式，就必須 move，但我覺得如果結點存儲的對象比較龐大，那麼這個 move 是不是比較沒必要？而如果返回 unique_ptr 擁有的裸指針，又不知道應該怎樣替換頭結點。

---

這種情況我認為應該在next內使用智能指針，因為所有權明確；但遍歷和暫時儲存後繼節點的時候使用裸指針，因為不具有所有權。

智能指針中shared_ptr, unique_ptr的語義就是資源所有權。凡是能明確資源所有權的地方，都應該使用shared_ptr或unique_ptr，並且由所有權擁有者儲存這個指針，指向其宣稱的被所有者。其餘情況使用weak_ptr還是裸指針視情況而定。

如何判斷Owner/Resource: 一個簡單的方法就是 a) 是否某個A對象析構後B一定析構？是，僅有A擁有B的所有權 b) 是否一類A對象析構後B一定析構？是：這些對象共同擁有B的所有權

Owner
| has
unique/shared_ptr ------&> Resource
own


不適合用智能指針的例子：

• 在二叉樹中應該用哪種智能指針比較合理？ - C++

二叉樹中子女指向父母的指針：1) 子女不擁有父母所有權 2) 因為父母指向子女使用了unique_ptr，所以子女指向父母不能用weak_ptr 這種時候子女指向父母應該用裸指針。

• 儲存非DAG圖

這種情況所有權不明確，儘管可以強行建立shared_ptr、weak_ptr來解決問題，但是仍然推薦使用裸指針。

接下來分析鏈表的例子：

單鏈表：

a -&> b -&> c


所有權明確，前一鏈表節點擁有後面的鏈表節點的所有權。且只有一個擁有所有權，unique_ptr。

在a後插入d（不考慮空節點等情況）：

//傳統寫法：
d-&>next = a-&>next;
a-&>next = d;
//unique_ptr寫法： d是unique_ptr, a是裸指針
d-&>next = std::move(a-&>next); //移交b的所有權給d，此時a不擁有任何所有權
a-&>next = std::move(d); //確立a對d的所有權


刪除b：

//傳統寫法：
node* anext = a-&>next;
a-&>next = anext-&>next;
delete anext; //經常有人忘記寫這個導致內存泄漏
//unique_ptr寫法：
a-&>next = std::move(a-&>next-&>next); //簡潔，一行解決了內存問題。將a-&>next（即b）擁有的c的所有權轉交給了a，b不被任何對象擁有，自動析構


雙鏈表：

a &<-&> b &<-&> c


兩種處理思路：1) next類似於單鏈表，只不過多保存一個prev裸指針 2) ac同時具有b所有權。個人更推薦1)，因為2)引入的shared_ptr對於鏈表代價太高了。

在a後插入d：

//傳統寫法：
d-&>next = a-&>next;
d-&>prev = a;
a-&>next-&>prev = d;
a-&>next = d;
//智能指針寫法：d是unique_ptr, a是裸指針：
d-&>prev = a; //先處理無傷大雅的裸指針prev域
a-&>next-&>prev = d.get();
d-&>next = std::move(a-&>next); //把a後繼的節點所有權轉交給d
a-&>next = std::move(d); //注意這一步與上一步不能顛倒，否則std::move(d)後d是一個空unique_ptr,d-&>next就不合法了


刪除b：

//傳統寫法：
a-&>next-&>next-&>prev = a;
node* anext = a-&>next;
a-&>next = a-&>next-&>next;
delete anext;
//智能指針寫法 a是裸指針：
a-&>next-&>next-&>prev = a;
a-&>next = std::move(a-&>next-&>next);


可以看出，在兩種情況下，智能指針不僅縮短了代碼長度，而且也避免了裸指針忘記delete的風險。

---

鏈表應該是普通指針吧。因為實際模型就是個queue啊

---

不要用，析構時會爆棧，別問我怎麼知道的

---

unique_ptr是用來解決資源釋放的, 數據結構用普通指針就好.

---

推薦閱讀：