TL; DR C＃で概念実証XorLinkedList実装をすばやく作成しました。
これは、C＃で安全でないコードを使用して絶対に可能です。ただし、いくつかの制限があります。
- XorLinkedListは「管理されていない構造体」である必要があります。つまり、管理された参照を含めることはできません。
- C＃ジェネリックの制限により、リンクリストをジェネリックにすることはできません
where T : struct（
後者は、ジェネリックパラメーターをアンマネージ構造体に制限できないためと思われます。where T : struct管理された参照を含む構造体も許可します。
これは、XorLinkedListが保持できるのは、int、ポインター、その他のアンマネージ構造体などのプリミティブ値のみであることを意味します。
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後でそれらのノードを忘れないでください（完全なIDisposableif(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;
}
結論
個人的には、C＃でXorLinkedListを使用することは決してありません（メモリアロケータやカーネルデータ構造などの非常に低レベルのシステムを記述している場合は、Cで使用する可能性があります。他の設定では、ストレージ効率を少し上げるだけでは苦労する価値はありません。 C＃の管理対象オブジェクトと一緒に使用できないという事実は、日常のプログラミングにはほとんど役に立たないものにします。
また、ストレージは現在ほとんど無料です。メインメモリもあります。C＃を使用している場合は、ストレージについてあまり気にしないでしょう。私はどこかでCLRオブジェクトヘッダーが約40バイトであったことを読んだので、この1つのポインターはあなたの懸念の中で最も少ないでしょう;）