c#克隆一个堆栈

Question

我的代码中有很少的堆栈用于跟踪我的逻辑位置.在某些时候我需要复制堆栈,但我似乎无法以保留订单的方式克隆它们.我只需要浅层复制(引用,而不是对象).

这样做的正确方法是什么？或者我应该使用其他类型的堆栈？

注意:我看到这篇文章Stack Clone Problem:.NET Bug或Expected Behavior？,但不确定如何为Stack类设置克隆方法.

注意#2:我使用System.Collection.Generic.Stack

Answer 1

var clonedStack = new Stack<T>(new Stack<T>(oldStack));

您可以将此作为扩展方法编写为

public static Stack<T> Clone<T>(this Stack<T> stack) {
    Contract.Requires(stack != null);
    return new Stack<T>(new Stack<T>(stack));
}

这是必要的,因为Stack<T>我们在这里使用的构造函数Stack<T>(IEnumerable<T> source)当然是当你遍历IEnumerable<T>实现时Stack<T>它将重复从堆栈中弹出项目,从而按照你希望它们的顺序反向输入它们新的堆栈.因此,执行此过程两次将导致堆栈处于正确的顺序.

或者:

var clonedStack = new Stack<T>(oldStack.Reverse());


public static Stack<T> Clone<T>(this Stack<T> stack) {
    Contract.Requires(stack != null);
    return new Stack<T>(stack.Reverse());
}

同样,我们必须从迭代堆栈的输出以相反的顺序遍历堆栈.

我怀疑这两种方法之间存在性能差异.

Answer 2

这是一个简单的方法,使用LINQ:

var clone = new Stack<ElementType>(originalStack.Reverse());

您可以创建一个扩展方法,以使这更容易:

public static class StackExtensions
{
    public static Stack<T> Clone<T>(this Stack<T> source)
    {
        return new Stack<T>(originalStack.Reverse());
    }
}

用法:

var clone = originalStack.Clone();

Answer 3

对于那些照顾性能的人来说.还有其他一些方法可以在没有性能损失的情况下迭代原始堆栈成员:

public T[] Stack<T>.ToArray();
public void Stack<T>.CopyTo(T[] array, int arrayIndex);

我写了一个粗略的程序(链接将在帖子的末尾提供)来衡量性能,并为已经建议的实现添加了两个测试(请参阅Clone1和Clone2),以及ToArray和CopyTo方法的两个测试(请参阅Clone3和Clone4),它们都使用更高效的Array.Reverse方法).

public static class StackExtensions
{
    public static Stack<T> Clone1<T>(this Stack<T> original)
    {
        return new Stack<T>(new Stack<T>(original));
    }

    public static Stack<T> Clone2<T>(this Stack<T> original)
    {
        return new Stack<T>(original.Reverse());
    }

    public static Stack<T> Clone3<T>(this Stack<T> original)
    {
        var arr = original.ToArray();
        Array.Reverse(arr);
        return new Stack<T>(arr);
    }

    public static Stack<T> Clone4<T>(this Stack<T> original)
    {
        var arr = new T[original.Count];
        original.CopyTo(arr, 0);
        Array.Reverse(arr);
        return new Stack<T>(arr);
    }
}

结果是:

• 克隆1:318,3766毫秒
• 克隆2:269,2407毫秒
• 克隆3:50,6025毫秒
• 克隆4:37,5233毫秒 - 获胜者

我们可以看到,使用CopyTo方法的方法快8倍,同时实现非常简单明了.此外,我对堆栈大小的最大值进行了快速研究:在OutOfMemoryException发生之前,Clone3和Clone4测试适用于更大的堆栈大小:

• 克隆1:67108765元素
• 克隆2:67108765元素
• 克隆3:134218140元素
• 克隆4:134218140元素

Clone1和Clone2的上述结果较小,原因是显式/隐式定义了额外的集合,因此影响了内存消耗.因此,Clone3和Clone4方法允许更快地克隆堆栈实例并减少内存分配.你可以使用Reflection获得更好的结果,但这是一个不同的故事:)

完整的程序列表可以在这里找到.