Реализация стека из указателей в C#

Question

Пытаюсь реализовать стек с использованием указателей. Пробовал сделать так (пока набросок):

    Node* head;

    unsafe struct Node 
    {
        public Int32 Value;
        public Node* Next;
    }        

    public LinkedStack()
    {
        head = null;
    }

    public void Add(Int32 value)
    {
        // Создаётся новый элемент стека, который ссылается на предыдущую "голову"
        Node newNode = new Node();
        newNode.Next = head;
        newNode.Value = value;

        head = &newNode;
    }

    public Int32 Peek()
    {
        return head->Value;
    }

При этом любое обращение к head->Value вне блока Add (к примеру в блоке Peek()) возвращает семизначные и более числа, которые не были занесены в стек.

Но при вынесении переменной newNode в переменные класса следующим образом и обращение к ней используя fixed работает нормально и возвращает корректные значения:

    Node* head;
    Node newNode;

    unsafe struct Node 
    {
        public Int32 Value;
        public Node* Next;
    }        

    public LinkedStack()
    {
        head = null;
    }

    public void Add(Int32 value)
    {
        fixed (Node* pNewNode = &newNode) // Необходимый костыль
        {
            pNewNode->Next = head;
            pNewNode->Value = value;

            // Меняем указатель головы на новый элемент
            head = pNewNode;
        }
    }

    public Int32 Peek()
    {
        return head->Value;
    }

Не могу понять в чём проблема. Почему после окончания блока Add значение Value меняется на произвольное другое? А при использовании fixed значение хранится нормально.

Извините, не по делу: а зачем вы это пишете? Ну эти указатели, стек? Какой практический выхлоп планируется от всего этого? — Bulson, Feb 13 '17 at 20:58
@Bulson В лабораторной была задача сделать стек с использованием указателей на любом языке. В то время я изучал C#, поэтому мой выбор был очевиден =) — Exide, Jul 19 '17 at 23:37
Как успехи? Сдали лабораторку? Ответ VladD вам помог? Если да, то закройте, пожалуйста, этот вопрос, поставьте галку слева от ответа. — Bulson, Jul 20 '17 at 07:34
@Bulson В конце концов я просто сделал через классы, так и сдал =) — Exide, Sep 05 '17 at 16:15

score 4 · Accepted Answer · edited Apr 13 '17 at 12:53

Вы делаете неправильно практически всё, вам стоит освежить в памяти начальные главы учебника по C#.

Напомню базовые вещи. Структуры в C#, в отличие от классов, являются объектами-значениями. Они аллоцируются на стеке* (да, new в C# означает не то же самое, что в C++), копируются по значению при передаче из функции, и умирают вместе с фреймом, в котором были аллоцированы. Отсюда следует, что указатель на структуру, не находящуюся в «долгоживущей» памяти, не имеет смысла.

Это объясняет проблемы первой реализации Add.

Далее, любой объект, не закреплённый (например, при помощи блока fixed) в памяти, может в любой момент быть перемещён сборщиком мусора. Поэтому указатель на не закреплённый в памяти объект (в отличие от ссылки) также не имеет смысла.

Но центральная проблема второй реализации функции Add не в этом. Она в том, что вы записываете новые данные в один и тот же экземпляр newNode, и новые значения затирают старые. Этого пока не заметно, поскольку у вас в коде есть лишь возможность просмотреть через Peek один элемент, текущую голову списка.

Я бы предложил не использовать unsafe-указатели в C#-коде, если это не является жизненно необходимым. Для их использования нужно реально хорошо понимать работу GC. Пока вы этого не знаете — лучше пользоваться стандартными средствами.

class LinkedStack
{
    Node head = null;

    class Node 
    {
        public int Value;
        public Node Next;
    }        

    public void Add(int value)
    {
        // Создаётся новый элемент стека, который ссылается на предыдущую "голову"
        Node newNode = new Node();
        newNode.Next = head;
        newNode.Value = value;

        head = newNode;
    }

    public int Peek()
    {
        return head.Value;
    }
}

*Строго говоря, не обязательно, но в первом приближении это так.

Реализация стека из указателей в C#

1 Answers1