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(); 
    } 
} 

啊，好吧。以上可能不适用于该错误。