c# clone a stack

Question

I have few stacks in my code that I use to keep track of my logical location. At certain times I need to duplicate the stacks, but I can't seem to clone them in such way that it preserves the order. I only need shallow duplication (references, not object).

What would be the proper way to do it? Or should I use some other sort of stacks?

NOTE: I saw this post Stack Clone Problem: .NET Bug or Expected Behaviour?, but not sure how to setup clone method for the Stack class.

NOTE #2: I use System.Collection.Generic.Stack

Solution 1

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

You can write this as an extension method as

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

This is necessary because the Stack<T> constructor that we are using here is Stack<T>(IEnumerable<T> source) and of course when you iterate over the IEnumerable<T> implementation for a Stack<T> it is going to repeatedly pop items from the stack thus feeding them to you in reverse of the order that you want them to go onto the new stack. Therefore, doing this process twice will result in the stack being in the correct order.

Alternatively:

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

Again, we have to walk the stack in the reverse order from the output from iterating over the stack.

I doubt there is a performance difference between these two methods.

Solution 2

For those who take care of performance.. There are a few other ways how to iterate through the original stack members without big losses in the performance:

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

I wrote a rough program (the link will be provided at the end of the post) to measure performance and added two tests for the already suggested implementations (see Clone1 and Clone2), and two tests for ToArray and CopyTo approaches (see Clone3 and Clone4, both of them use more efficient Array.Reverse method).

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

The results are:

• Clone1: 318,3766 ms
• Clone2: 269,2407 ms
• Clone3: 50,6025 ms
• Clone4: 37,5233 ms - the winner

As we can see, the approach using CopyTo method is 8 times faster and at the same time the implementation is pretty simple and straightforward. Moreover, I did a quick research on a maximum value of stack size: Clone3 and Clone4 tests worked for bigger stack sizes before OutOfMemoryException occurs:

• Clone1: 67108765 elements
• Clone2: 67108765 elements
• Clone3: 134218140 elements
• Clone4: 134218140 elements

The results above for Clone1 and Clone2 are smaller due to additional collections that were explicitly/implicitly defined and therefore affected memory consumption. Thus, Clone3 and Clone4 approaches allow to clone a stack instance faster and with less memory allocations. You can gain even better results using Reflection, but it's a different story :)

The full program listing can be found here.

Solution 3

Here's one easy way, using LINQ:

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

You could create an extension method to make this easier:

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

Usage:

var clone = originalStack.Clone();

Comments

[SpaceBear]

sadly, oddly, that doesn't preserve order :( (I assume double initialization of a stack is typo or is that a trick?)

[jason]

@Angrius: It does preserve the order. The double instantiation is a trick that causes the order to be preserved.

[Gabe]

@Angrius: The "double initialization" is required because each one reverses the order. If you reverse it twice you get the original order.

[jason]

@Angrius: Also, it's not odd that it doesn't preserve the order. Please see my explanation of why it happens. The implementation of IEnumerable<T> for Stack<T> makes perfect sense; if the implementation of IEnumerable<T> for Stack<T> did anything but repeatedly pop and yield I'd be confused. The constructor for Stack<T>(IEnumerable<T> source) makes perfect sense; if this constructor for Stack<T> did anything but pull from the source and push I'd be confused. There is nothing odd about it IMO.

[null]

Worked for me. This also preserves the original stack.

[jason]

@Diego Mijelshon: No, it doesn't! It pops from the top and repeats to the bottom of the stack.

[Diego Mijelshon]

@Jason you're correct, I had misinterpreted my test results. It's the Stack constructor which gets the stuff "wrong" (for the purposes of cloning, that is)

[supercat]

Although it makes sense for a stack constructor to push things in order, it's pretty common in "real life" to build a stack by taking a list of items and pushing them last-item-first. For example, optional arguments in C and derived languages are generally pushed right-to-left to facilitate their being read out in order.

[lordcheeto]

I actually needed the items reversed anyways, so thanks for explaining the reasoning behind the double instantiation!

[AndreyCh]

Proving the results with BenchmarkDotNet. The Clone4 is still the most efficient method, both from CPU and memory standpoints. 1. Clone1 (703.87 ms, 128 MB) 2. Clone2 (535.94 ms, 128 MB) 3. Clone3 (71.60 ms, 64 MB) 4. Clone4 (56.20 ms, 64 MB)