Splice_after執行forward_list

在forward_list中有一個函數splice_after（for reference），具體來說就是給定鏈接中的函數＃3。考慮到list是單獨鏈接的，將如何實施。Splice_after執行forward_list

作爲練習，當我實現它，我不得不遍歷列表，直到我到達節點first之前（這樣我就可以連接first到last），並再次直到我last之前到達節點（讓我能將當前列表的節點連接到節點last之前）。這對我來說似乎並不可怕，而且想知道是否有更好的方法可以不迭代地完成它？

來源

2012-01-08 Samaursa

我懷疑你誤讀了「（first，last）」被移動的有些微妙的範圍規範，而不是「[first，last）」（注意左括號/括號）。也就是說，如名稱所示，拼接操作僅在之後的第一個對象開始。

功能的實現其實很簡單（如果你忽略了迭代器和事實的常量性，它可能需要處理分配器是不同的）：

void splice_after(const_iterator pos, forward_list& other, const_iterator first, const_iterator last) { node* f = first._Node->_Next; node* p = f; while (p->_Next != last._Node) { // last is not included: find its predecessor p = p->_Next; } first._Node->Next = last._Node; // remove nodes from this p->_Next = pos._Node->_Next; // hook the tail of the other list onto last pos._Node->_Next = f; // hook the spliced elements onto pos }

此操作具有線性的，因爲它的複雜性需要找到last的前身。

來源

2012-01-08 02:50:32

您懷疑是否正確！但是，我的問題依然存在。最後的元素呢？它需要在列表中，這意味着我必須迭代它。 – Samaursa 2012-01-08 02:57:50

爲什麼要迭代到元素？你只需要把'last'的下一個指針放到'first'的下一個指針中，顯然在保存之後你可以把它放到另一個列表中。我想，我會更新我的答案，以潛在的函數執行... – 2012-01-08 03:01:31

@Samaursa，你說：「這樣我就可以將當前列表的節點連接到最後節點」。但我認爲當前節點應該連接到最後，而不是連接到最後一個節點。 – 2012-01-08 03:04:40

（社區維基，請貢獻）

A -> B -> C -> D -> E 
     ^
     ^pos points to C

在other列表

U -> V -> W -> X -> Y -> Z 
    ^   ^
    ^first  ^last

呼叫.splice(pos, other, first, last)

我們移動W和X到頂部的列表。即包括但不包括first和last之間的所有內容。最後以A->B->C->W->X->D->E結尾，底部以U->V->Y->Z結束。

auto copy_of_first_next = first->next; 
first->next = last; 
// the `other` list has now been emptied 

auto copy_of_pos_next = pos->next; 
pos -> next = first; 
while(first->next != last) ++first; 
// `first` now points just before `last` 
first->next = copy_of_pos_next

來源

2012-01-08 03:17:50

Splice_after執行forward_list

回答

相關問題