XOR 連結リストは、各ノードが 2 つではなく 1 つの「ポインタ」を格納する、通常の二重連結リストの修正バージョンです。その「ポインター」は、次のポインターと前のポインターの XOR で構成されます。リストをトラバースするには、現在のノードへのポインターと、次または前のノードへのポインターの 2 つのポインターが必要です。前方にトラバースするには、前のノードのアドレスが現在のノードに格納されている「ポインター」と XOR 演算され、真の「次の」ポインターが明らかになります。
C++ 標準では、ポインターと整数に対する一連の操作によって未定義の動作が発生します。たとえば、数値の特定のビットを設定しても、ハードウェアが割り込みをトリガーしないことを保証できないため、場合によっては bit の結果いじりは未定義にすることができます。
私の質問は次のとおりです。未定義の動作にならない XOR リンク リストの C++ 実装はありますか?
私の質問は次のとおりです。未定義の動作にならない XOR リンク リストの C++ 実装はありますか?
「実装はありますか」が「すでに書かれている」という意味であれば、私にはわかりません。「書くことは可能ですか」という意味であれば、そうですが、移植性についていくつかの注意事項があるかもしれません。
uintptr_t開始する前に両方のポインターを に変換し、その型をポインターの代わりにノードに格納すると、心ゆくまで少しいじることができます。符号なしの型に対するビット単位の演算によって、未定義の動作が発生することはありません。
ただし、uintptr_tオプションのタイプであるため、完全に移植できるわけではありません。C++ 実装が実際にアドレスを表現できる整数型を持っている必要はありません。実装にない場合uintptr_t、コードは診断を使用してコンパイルすることが許可されます。この場合、その動作は標準の範囲外になります。それを「UBなし」の侵害と見なすかどうかはわかりません。つまり、真剣に、未定義の型を使用するコードを許可するコンパイラですか? ;-)
回避するためuintptr_tに、代わりに符号なし文字の配列でビットいじりを行うことができると思います。sizeof(node*)ポインターは POD 型であるため、オブジェクト表現がポインターとして使用される前に元の状態に復元されていれば、コピー、スピンドル、および切断することができます。
また、C++ 実装にガベージ コレクターがある場合、convert-to-integer / xor / xor-back-again / convert-to-pointer は、収集中のオブジェクトを停止する必要がないことにも注意してください (「安全でない派生エラーが発生するため」ポインター」）。したがって、移植性のために、結果のポインターが有効であることも確認する必要があります。これを行うには 2 つの方法があります。
declare_reachableます。get_pointer_safety()、緩和された実装が厳密であると誤って主張することが許されていることを念頭に置いてテストできます)。第 3 の方法があると思われるかもしれません (XOR リンク リストの目的を無効にする方法ではありますが)。
これが動作することは保証されていません。たまたま安全に派生したポインター (3.7.4.3/4) と等しい場合でも、安全でない派生ポインターは無効です。私も驚きました。