.net 如何克隆堆栈< T>

lf5gs5x2  于 2023-03-04  发布在  .NET
关注(0)|答案(4)|浏览(143)

在我的代码中,我很少有堆栈用来跟踪我的逻辑位置。在某些时候,我需要复制堆栈,但我似乎不能以这样的方式复制它们,它保持了顺序。我只需要浅复制(引用,而不是对象)。
正确的方法是什么?或者我应该使用其他类型的堆栈?
我看到这篇文章Stack Clone Problem: .NET Bug or Expected Behaviour?,但不知道如何设置Stack<T>类的克隆方法。
我使用System.Collection.Generic.Stack<T>

7gs2gvoe

7gs2gvoe1#

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),当然,当你迭代Stack<T>IEnumerable<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());
}

同样,我们必须按照与迭代堆栈的输出相反的顺序遍历堆栈。
我怀疑这两种方法之间是否存在性能差异。

lf3rwulv

lf3rwulv2#

对于那些关心性能的人来说..还有一些其他的方法来迭代原始的堆栈成员而不会对性能造成大的损失:

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

我编写了一个粗略的程序(链接将在文章末尾提供)来测量性能,并为已经建议的实现添加了两个测试(参见 * Clone1 * 和 * Clone2 *),以及为ToArrayCopyTo方法添加了两个测试(参见 * 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倍,同时实现也非常简单和直接。此外,我还快速研究了堆栈大小的最大值:* Clone3 * 和 * Clone4 * 测试在 * OutOfMemoryException * 发生之前适用于更大的堆栈大小:

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

由于显式/隐式定义了额外的集合,因此影响了内存消耗,因此 * Clone1 * 和 * Clone2 * 的上述结果较小。因此,* Clone3 * 和 * Clone4 * 方法允许更快地克隆堆栈示例,并使用更少的内存分配。使用反射可以获得更好的结果,但情况不同:)
完整的程序列表可在here中找到。

4si2a6ki

4si2a6ki3#

这里有一个简单的方法,使用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();
s5a0g9ez

s5a0g9ez4#

如果你不需要一个实际的Stack1,而只是想要一个现有Stack1的快速拷贝,你可以按照Pop返回的顺序遍历它,另一个选择是将Stack1复制到Queue1中,然后元素将按照从原始Stack1Pop的相同顺序进行Dequeue`。

using System;
using System.Collections.Generic;

class Test
{
  static void Main()
  {
    var stack = new Stack<string>();

    stack.Push("pushed first, pop last");
    stack.Push("in the middle");
    stack.Push("pushed last, pop first");

    var quickCopy = new Queue<string>(stack);

    Console.WriteLine("Stack:");
    while (stack.Count > 0)
      Console.WriteLine("  " + stack.Pop());
    Console.WriteLine();
    Console.WriteLine("Queue:");
    while (quickCopy.Count > 0)
      Console.WriteLine("  " + quickCopy.Dequeue());
  }
}

输出:

Stack:
  pushed last, pop first
  in the middle
  pushed first, pop last

Queue:
  pushed last, pop first
  in the middle
  pushed first, pop last

相关问题