C ++で再帰データ型（「自己参照型」）が何に適しているかを尋ねる質問に気づき、大胆に主張したくなりました。
これは、連続したメモリ領域を使用せずに任意の大規模なデータコレクションを受け入れることができるデータ構造（より正確にはコンテナ）を構築する唯一の方法です。
つまり、ランダムアクセス配列がない場合は、その型内の型を（論理的に）参照する手段が必要になります（明らかに、MyClass* nextメンバーを持つ代わりに、言うことができますvoid* nextが、それでもMyClassオブジェクトまたは派生物を指します）タイプ）。
しかし、私は絶対的な発言には注意を払っています-何かを考えることができなかったからといって、それが不可能であるとは限らないので、私は何かを見落としていますか？リンクリスト/ツリーと同様のメカニズムを使用して編成されていない、または連続シーケンスのみを使用して編成されていないデータ構造はありますか？
注：これは、 C ++と言語に依存しない両方のタグが付けられています。これは、特にC ++言語だけでなく、理論的な側面にも関心があるためです。
これは、連続したメモリ領域を使用せずに任意の大規模なデータコレクションを受け入れることができるデータ構造（より正確にはコンテナ）を構築する唯一の方法です。
しばらく熟考した後、このステートメントは正しいようです。実際、それは自明です。
連続していないメモリに要素のコレクションがあるとします。また、私が現在要素にいると仮定しますe。ここで問題は、コレクション内の次の要素をどのように知ることができるかということです。方法はありますか？
eコレクションの要素が与えられた場合、次の要素の場所を計算する方法は2つだけです。
sizeof(e)何であるかに関係なくオフセットにあると仮定するeと、次の要素は現在の要素が終了するところから開始することを意味します。しかし、これは、コレクションが連続したメモリにあることを意味します。これは、この説明では禁止されています。
要素e自体が次の要素の場所を教えてくれます。アドレス自体、またはオフセットを格納する場合があります。いずれにせよ、それは自己参照の概念を使用していますが、これもこの議論では禁止されています。
私が見ているように、これらのアプローチの両方の基本的な考え方はまったく同じです。どちらも自己参照を実装しています。唯一の違いは、前者では、自己参照がオフセットsizeof(e)として使用して暗黙的に実装されることです。この暗黙的な自己参照は、言語自体によってサポートされ、コンパイラーによって実装されます。後者の場合、それは明示的であり、オフセット（またはポインター）が要素自体に格納されるため、すべてがプログラマー自身によって行われます。
したがって、自己参照を実装するための3番目のアプローチは見当たりません。自己参照でない場合、要素の次の要素の位置の計算を説明するためにどの用語eを使用しますか。
だから私の結論は、あなたの発言は絶対に正しいということです。
問題は、動的アロケータ自体が連続したストレージを管理していることです。チューリングマシン、またはフォンノイマンアーキテクチャに使用される「テープ」について考えてみてください。したがって、問題を真剣に検討するには、新しいコンピューティングモデルと新しいコンピュータアーキテクチャを開発する必要があります。
基盤となるマシンの連続したメモリを無視しても問題ないと思われる場合は、いくつかの解決策が可能であると確信しています。最初に頭に浮かぶのは、コンテナの各ノードが、メモリ内の位置とは関係のない識別子でマークされていることです。次に、関連付けられたノードを見つけるために、識別子が見つかるまですべてのメモリがスキャンされます。並列マシンに十分なコンピューティング要素があれば、これは特に非効率的ではありません。
これが証明のスケッチです。
プログラムは有限のサイズでなければならないことを考えると、プログラム内で定義されたすべてのタイプは、有限の数のメンバーのみを含み、有限の数の他のタイプのみを参照する必要があります。同じことが、プログラムのエントリポイントと、プログラムの初期化の前に定義されたオブジェクトにも当てはまります。
連続する配列（実行時の自然数を持つ型の積であり、したがってサイズに制約がない）がない場合、すべての型は上記の型の構成を通じて到達する必要があります。タイプの導出（pointer-to-pointer-to- ）は、プログラムのサイズによって依然として制約されます。型を使用して実行時の値を構成するための連続した配列以外の機能はありません。A
これは少し論争の的です。たとえば、マッピングがプリミティブであると見なされる場合、キーが自然数であるマップで配列を近似できます。もちろん、マップの実装では、自己参照データ構造（Bツリー）または連続配列（ハッシュテーブル）を使用する必要があります。
次に、型が非再帰的である場合、型のチェーン（A参照B参照C...）は終了する必要があり、プログラムで定義された型の数を超えてはなりません。したがって、プログラムが参照できるデータの合計サイズは、各タイプのサイズにプログラムで定義された名前の数（エントリポイントおよび静的データ）を掛けたものに制限されます。
これは、関数が再帰的であっても当てはまります（厳密に言えば、関数は型であるため、再帰型の禁止を破ります）。プログラムの任意の時点ですぐに表示されるデータの量は、各タイプのサイズにその時点で表示される名前の数を掛けたものに制限されます。
これの例外は、再帰関数呼び出しのスタックに「コンテナ」を格納する場合です。ただし、そのようなプログラムは、スタックを巻き戻し、データを再読み取りする必要がない限り、データをランダムにトラバースすることはできません。これは、失格のようなものです。
最後に、型を動的に作成できる場合、上記の証明は成り立ちません。たとえば、各セルが異なるタイプであるLispスタイルのリスト構造を作成できますcons<4>('h', cons<3>('e', cons<2>('l', cons<1>('l', cons<0>('o', nil)))))。これは、ほとんどの静的型付き言語では不可能ですが、Pythonなどの一部の動的言語では可能です。
ステートメントが正しくありません。簡単なカウンターの例はstd::dequeC++です。基本的なデータ構造（言語に依存しない部分）は、データの配列へのポインターの連続した配列です。実際のデータは、連続した配列を介してチェーンされたロープ（連続していないブロック）に格納されます。
これは、連続メモリ領域を使用しないことの意味によっては、要件に隣接している可能性があります。保存されたデータは連続していないという解釈を使用していますが、このデータ構造は中間層の配列があるかどうかに依存します。
私はより良い言い回しは次のようになると思います：
It's the only way to construct data structures (more precisely containers) that can accept
arbitrary large data collections without using memory areas of determinable address.
つまり、通常の配列はaddr(idx)=idx*size+inital_addr要素のメモリアドレスを取得するために使用します。ただし、これを次のように変更するとaddr(idx)=idx*idx*size+initial_addr、データ構造の要素は連続したメモリ領域に格納されず、要素が格納される場所の間に大きなギャップが生じます。したがって、それは連続メモリではありません。