2011-09-12 41 views
13

我的代码中有几个堆栈用于跟踪我的逻辑位置。在某些时候,我需要复制堆栈,但似乎无法以保留顺序的方式克隆它们。我只需要浅层重复(引用,而不是对象)。c#克隆一个堆栈

什么是正确的方法来做到这一点?或者我应该使用其他类型的堆栈?

注意:我看到这篇文章Stack Clone Problem: .NET Bug or Expected Behaviour?,但不知道如何为Stack类设置克隆方法。

注2:我用System.Collection.Generic.Stack

回答

21
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>实现时,它将重复弹出堆栈中的项目,从而将它们反馈给您,顺序与您w蚂蚁他们去新的堆栈。因此,执行此过程两次将导致堆栈按正确顺序排列。

或者:

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

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

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

+0

令人遗憾的是,奇怪的是,这并不能保持顺序:((我认为双栈初始化是一个错误或是一个诡计?) – SpaceBear

+0

@Angrius:它确实保存了顺序,双重实例化是一个技巧,被保留的顺序 – jason

+1

@Angrius:因为每一个颠倒的顺序“双初始化”要求如果颠倒两次你原来的顺序 – Gabe

7

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

困惑。为什么会反向 – SpaceBear

+0

谢谢,简单的逆向工作! – SpaceBear

+0

为我工作。这也保留了原始堆栈。 – MStodd

1

如果你不”吨需要一个实际的Stack`1,但只想快速复制一个现有的Stack`1 y您可以按照Pop返回的顺序行走,另一个选项是将Stack`1复制到Queue`1。这些元素将以Dequeue的顺序与原来的Stack`1Pop相同。

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 
2

对于那些谁拿的性能照顾..还有一些其他的方式如何通过无需在性能损失就大了原来的堆叠成员重复:

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

我写了一个粗略的方案(该链接将在帖子的末尾提供)来衡量性能和增加了两个试验已经表明实现(见Clone1Clone2),和两个试验ToArray的CopyTo从方法(见Clone3Clone4,他们都使用更有效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); 
    } 
} 

的结果是:

  • Clone1:318,3766毫秒
  • Clone2:269,2407毫秒
  • Clone3:50,6025毫秒
  • Clone4:37,5233 ms - 赢家

因为我们可以看到,使用CopyTo从方法的方法是快8倍,并在同一时间实现是非常简单和直接。此外,我做了一个快速研究堆大小的最大值:Clone3Clone4测试OutOfMemoryException异常工作之前更大的堆栈大小发生:

  • Clone1:67108765种元素
  • Clone2:67108765元件
  • Clone3:134218140个元件
  • Clone4:134218140个元件

上述用于Clone1Clone2结果,要由显式/隐式定义的,并因此影响了存储器消耗的附加集合是较小的。因此,Clone3Clone4方法允许更快克隆栈实例和使用较少的内存分配。你可以得到使用反射更好的结果,但它是一个不同的故事:)

完整的程序列表中可以发现here