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

544

15 февраля 2017, 21:01

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

    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 значение хранится нормально.

Answer 1

Вы делаете неправильно практически всё, вам стоит освежить в памяти начальные главы учебника по 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;
    }
}