std :: forward_list在C++中的swap（）實現11

我的假設是，在std::list<>中，列表本身的swap函數是通過交換錨節點完成的。該節點可以訪問前一個節點並輕鬆更新前一個節點的下一個指針，以指向另一個列表的錨點;但是這不能在std::forward_list中完成（當然，這可能非常昂貴）。std :: forward_list在C++中的swap（）實現11

如果我的假設是正確的，swap()如何以有效的方式在std::forward_list中實現？而我們在這個時候，swap()如何實現的std::forward_list？

來源

2012-01-25 Samaursa

一個std::forward_list簡直就是一個單鏈接，而不是像std::list雙向鏈表，所以你可以簡單地交換名單的head和tail指針以完成swap()操作。

來源

2012-01-25 18:31:44 Jason

我的印象是'std :: list'在內部是一個循環列表，我假設'std :: forward_list'是一樣的。我猜測這完全取決於實施。 – Samaursa

即使它們是循環鏈表，仍然不需要更新節點上的任何指針。整個列表正在交換，因此沒有任何節點鏈接會改變。所有這些變化都是從std :: list到節點的指針。 – bames53

@ bames53：如果它是一個循環列表，那麼每個節點都指向下一個節點或列表的尾部。而列表尾部指向頭部，而頭部又指向第一個元素。那麼如何交換尾指針，因爲您需要調整指向尾部的節點，並且除非遍歷整個列表，否則無法到達尾指針。或者尾指針是指向頭部以及最後一個節點的對象？ – Samaursa

這完全是特定於實現的，但如果通過讓類只存儲指向第一個和最後一個鏈接列表單元的指針來實現轉發列表，那麼swap就可以交換這兩個指針。由於前向鏈表沒有任何後退指針，因此不需要進行更新，整個操作可以在O（1）中完成。

至於與迭代器交換，這實際上並沒有交換兩個列表之間的鏈接列表單元格;它只有第一個迭代器指向第二個迭代器引用的單元格，反之亦然。如果要交換指向的值，則可以通過修改鏈接列表單元格中的對象以便更改值來完成此操作。你不需要以任何方式重新列表。

希望有所幫助！

來源

2012-01-25 18:32:46 templatetypedef

啊，當然！（+1） – Samaursa

我相信forward_list甚至不需要存儲尾指針，但可以使用通用的空迭代器作爲結束迭代器。 –

我覺得你很困惑（或者我對你的要求感到困惑）。 std :: forward_list :: swap（std :: forward_list &其他）很簡單，每個列表對象交換指向其列表頭部的指針（以及任何其他成員變量） - 就像std :: list一樣。

迭代器對象沒有交換方法。包含的對象可能或可能使用全局交換方法 - 但是對對象進行操作，並且不會改變列表本身或其節點。

來源

2012-01-25 18:32:49

std :: forward_list在C++中的swap（）實現11

回答

相關問題