связанный список XOR

TL;DR Я быстро написал пробную версию реализации XorLinkedList на С#.

Это абсолютно возможно с использованием небезопасного кода на C#. Однако есть несколько ограничений:

1. XorLinkedList должен быть «неуправляемой структурой», т. е. он не может содержать управляемые ссылки.
2. Из-за ограничения универсальных шаблонов C# связанный список не может быть универсальным (даже с where T : struct).

Последнее, по-видимому, связано с тем, что вы не можете ограничить универсальный параметр неуправляемыми структурами. С помощью всего лишь where T : struct вы также разрешите структуры, содержащие управляемые ссылки.

Это означает, что ваш XorLinkedList может содержать только примитивные значения, такие как целые числа, указатели или другие неуправляемые структуры.

Низкоуровневое программирование на C#

private static Node* _ptrXor(Node* a, Node* b)
{
    return (Node*)((ulong)a ^ (ulong)b);//very fragile
}

Очень хрупкий, я знаю. Указатели C# и IntPtr не поддерживают оператор XOR (вероятно, хорошая идея).

private static Node* _allocate(Node* link, int value = 0)
{
    var node = (Node*) Marshal.AllocHGlobal(sizeof (Node));
    node->xorLink = link;
    node->value = value;
    return node;
}

Не забудьте Marshal.FreeHGlobal эти узлы впоследствии (реализуйте полный IDisposable и не забудьте разместить бесплатные вызовы за пределами блока if(disposing).

private static Node* _insertMiddle(Node* first, Node* second, int value)
{
    var node = _allocate(_ptrXor(first, second), value);
    var prev = _prev(first, second);
    first->xorLink = _ptrXor(prev, node);
    var next = _next(first, second);
    second->xorLink = _ptrXor(node, next);
    return node;
}

Заключение

Лично я бы никогда не использовал XorLinkedList в C# (возможно, в C, когда я пишу действительно низкоуровневые системные вещи, такие как распределители памяти или структуры данных ядра. В любом другом случае небольшой выигрыш в эффективности хранения действительно не стоит боли. тот факт, что вы не можете использовать его вместе с управляемыми объектами в C#, делает его практически бесполезным для повседневного программирования.

Кроме того, хранилище сегодня почти бесплатно, даже основная память, и если вы используете C #, вы, вероятно, не слишком заботитесь о хранилище. Я где-то читал, что заголовки объектов CLR были около 40 байт, так что этот указатель будет наименьшей из ваших проблем;)

C# обычно не позволяет вам манипулировать ссылками на этом уровне, так что, к сожалению, нет.

В качестве альтернативы небезопасным решениям, которые были предложены.

Если вы подкрепили свой связанный список массивом или коллекцией списков, где вместо указателя памяти «следующий» и «предыдущий» указывают индексы в массиве, вы могли бы реализовать этот xor, не прибегая к использованию небезопасных функций.

Существуют способы работы с указателями в C#, но вы можете иметь указатель на объект только временно, поэтому вы не можете использовать их в этом сценарии. Основная причина этого — сборка мусора — пока вы можете делать такие вещи, как указатели XOR и отменять их XOR позже, GC не может узнать, безопасно ли собирать определенный объект или нет.

Вы могли бы сделать что-то очень похожее, эмулируя указатели с помощью индексов в одном большом массиве, но вам пришлось бы реализовать простую форму управления памятью самостоятельно (например, при создании нового узла, где в массиве я должен его поместить?).

Другой вариант - использовать C++/CLI, который обеспечивает полную гибкость указателей, с одной стороны, и GC, а также доступ к фреймворку, когда он вам нужен, с другой.

Конечно. Вам просто нужно закодировать класс. оператор XOR в С# - это ^ Это должно быть все, что вам нужно, чтобы начать кодирование. Обратите внимание, что для этого потребуется, чтобы код был объявлен «небезопасным». здесь: как использовать С#.

Делая здесь широкое обобщение: C#, похоже, пошел по пути удобочитаемости и чистых интерфейсов, а не по пути битовой возни и максимально плотной упаковки всей информации.

Итак, если у вас нет особой потребности здесь, вы должны использовать список, который вам предоставлен. Будущие программисты сопровождения будут вам за это благодарны.

Это возможно, однако вы должны понимать, как С# смотрит на объекты. Переменная экземпляра фактически содержит не объект, а указатель на объект в памяти.

DateTime dt = DateTime.Now;

dt — указатель на структуру в памяти, содержащую схему DateTime.

Таким образом, вы можете сделать этот тип связанного списка, хотя я не уверен, почему вы это сделаете, поскольку структура обычно уже реализовала наиболее эффективные коллекции. В качестве эксперимента мысли это возможно.