c # клонировать стек

Question

В моем коде есть несколько стеков, которые я использую для отслеживания моего логического местоположения.В определенные моменты мне нужно дублировать стеки, но я не могу их клонировать таким образом, чтобы сохранить порядок.Мне нужно только поверхностное дублирование (ссылки, а не объект).

Как правильно это сделать?Или я должен использовать другие виды стеков?

ПРИМЕЧАНИЕ. Я видел этот пост Проблема клонирования стека: ошибка .NET или ожидаемое поведение? , но не уверен, как настроить метод клонирования дляКласс стека.

ПРИМЕЧАНИЕ # 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 мс
• Clone2: 269,2407 мс
• Clone3: 50,6025 мс
• Клон4: 37,5233 мс - победитель

Как мы видим, подход с использованием CopyTo метода в 8 раз быстрее и в то же время реализация довольно проста и прямолинейна. Более того, я провел быстрое исследование максимального значения размера стека: тесты Clone3 и Clone4 работали для больших размеров стека до того, как OutOfMemoryException произойдет:

• Clone1: 67108765 элементов
• Clone2: 67108765 элементов
• Clone3: 134218140 элементов
• Clone4: 134218140 элементов

Приведенные выше результаты для Clone1 и Clone2 меньше из-за дополнительных коллекций, которые были явно / неявно определены и, следовательно, влияли на потребление памяти. Таким образом, подходы Clone3 и Clone4 позволяют клонировать экземпляр стека быстрее и с меньшими выделениями памяти. С помощью Reflection вы можете добиться еще лучших результатов, но это уже другая история :)

Полный список программ можно найти здесь .

Answer 4

Если вам не нужен фактический Stack`1, а просто нужна быстрая копия существующего Stack`1, который вы можете перемещать в том же порядке, что и Pop, другой вариант - дублировать Stack`1в Queue`1.Затем элементы будут Dequeue в том же порядке, в котором они будут Pop из исходного Stack`1.

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