Dlist：在foreach循環中使用stableLinearRemove

Question

我已經寫了下面的代碼，但它沒有給出正確的結果（例如，如果輸入[-1，-1]，它會返回[-1，-1， -1]。

import std.stdio, std.range, std.container, std.algorithm; 

DList!T strandSort(T)(DList!T list) { 
    static DList!T merge(DList!T left, DList!T right) { 
     DList!T res; 
     while (!left.empty && !right.empty) { 
      if (left.front <= right.front) { 
       res.insertBack(left.front); 
       left.removeFront(); 
      } else { 
       res.insertBack(right.front); 
       right.removeFront(); 
      } 
     } 
     res.insertBack(left[]); 
     res.insertBack(right[]); 
     return res; 
    } 

    DList!T result, sorted; 

    while (!list.empty) { 
     sorted.clear(); 
     sorted.insertBack(list.front); 
     list.removeFront(); 
     foreach (item; list) { 
      if (sorted.back <= item) { 
       sorted.insertBack(item); 
       list.stableLinearRemove(list[].find(item).take(1))); 
      } 
     } 
     result = merge(sorted, result); 
    } 

    return result; 
} 

void main() { 
    auto lst = DList!int([-1,-1]); 
    foreach (e; strandSort(lst)) 
     writef("%d ", e); 
} 

有時，stableLinearRemove不會從列表中刪除的項目。現在的問題是，它是在我的代碼中的錯誤，或者在火衛一？

又見設置探討Rosettacode.org

編輯：我懷疑它是c由removeFront激活。當第一個節點被刪除時，它不會將第二個節點的prev節點指針設置爲null。當通過linearRemove從列表中刪除的項目碰巧是第一個節點時，它不會被刪除。刪除功能檢查「之前」和「之後」節點和「之前」仍然設置。如果我把它寫這樣的，它的工作：

if (sorted.back <= item) { 
    sorted.insertBack(item); 
    if (list.front == item) 
     list.removeFront(); 
    else 
     list.stableLinearRemove(list[].find(item).take(1))); 
} 

Answer 1

我不認爲這是在火衛一的錯誤，而是一個疑難雜症。如果它可能是列表中的第一個元素，則不應該依賴linearRemove刪除元素。首先檢查並使用removeFront。也更高效。

在上述情況下，一個更好的解決辦法是複製的清單：

DList!T result, sorted, leftover; 

while (!list.empty) { 
    leftover.clear(); 
    sorted.clear(); 
    sorted.insertBack(list.front); 
    list.removeFront(); 
    foreach (item; list) { 
     if (sorted.back <= item) 
      sorted.insertBack(item); 
     else 
      leftover.insertBack(item); 
    } 
    result = merge(sorted, result); 
    list = leftover; 
} 

Answer 2

你是對的，那絕對是在removeFront的錯誤。

雖然我可能會指出，通過foreach刪除迭代元素即使它應該是有效的也不會有效。你需要一個範圍的句柄。考慮：

auto rng = list[]; 
while(!rng.empty) { 
    auto item = rng.front; 
    if(sorted.back <= item) { 
     sorted.insertBack(item); 
     auto rng2 = rng.save(); 
     rng.popFront(); 
     list.stableLinearRemove(rng2.take(1)); // O(1) removal! 
    }else{ 
     rng.popFront(); 
    } 
} 

啊，好吧。以上可能不適用於該錯誤。