Loading article…
コンピュータプログラミングにおいて、ドープベクトルはデータオブジェクトに関する情報、特にそのメモリレイアウトを保持するために使用されるデータ構造です。 [1]
目的
ドープベクターは、通常、特定のデータ型の複数のインスタンスを連続したメモリブロックとして格納する配列を記述するために最もよく使用されます。たとえば、各要素が 32 バイトを占める 100 個の要素を含む配列には、100 × 32 バイトが必要です。このようなメモリブロック自体には、配列 (またはその他のオブジェクト) の全体的な大きさ、配列内の各要素の大きさ、または配列に含まれる要素の数を追跡する場所がありません。ドープベクターは、このような情報を格納する場所です。ドープベクターは、配列または変数要素を含む可能性のある 構造を記述することもできます。
このような配列が連続して格納され、最初のバイトがメモリ位置Mにある場合、最後のバイトは位置M + 3199にあります。この配置の主な利点は、項目Nの検索が簡単なことです。項目 N は位置M + ( N × 32)から始まります。もちろん、値 32 がわかっている必要があります (この値は一般に配列の「ストライド」または配列要素の「幅」と呼ばれます)。インデックスを使用して配列データ構造をナビゲートすることを、デッドレコニングと呼びます。
ただし、この配置 (ドープ ベクトルを追加しない場合) では、項目 N の位置がわかっても、インデックス N 自体、またはストライド、またはN − 1またはN + 1に要素があるかどうかを検出するのに十分ではありません。たとえば、関数またはメソッドは配列内のすべての項目を反復処理し、各項目を別の関数またはメソッドに渡すことがあります。その関数またはメソッドは、項目が配列の一部であることをまったく認識せず、配列がどこにあり、どのくらい大きいかはわかりません。
ドープベクターがなければ、配列全体のアドレスがわかっても、配列の大きさはわかりません。これは、N要素のみを含む配列のN + 1要素に書き込むと、他のデータが破壊される可能性があるため重要です。多くのプログラミング言語は文字列を一種の配列として扱うため、これは悪名高いバッファオーバーフロー問題に直接つながります。
ドープベクターは、配列 (またはその他のオブジェクト) とともに少量のメタデータを保存することで、これらの問題を軽減します。ドープベクターを使用すると、コンパイラーは配列またはその他のオブジェクトの末尾を超えて誤って書き込むことを防ぐコードを簡単に (オプションで) 挿入できます。また、プログラマーは安全のため、またはその他の目的で、必要なときにドープベクターにアクセスできます。
説明
ドープ ベクターに含まれるメタデータの正確なセットは言語やオペレーティング システムによって異なりますが、配列のドープ ベクターには次のものが含まれる場合があります。
- 配列要素が始まるメモリ内の位置へのポインタ (これは通常、配列の 0 番目の要素 (すべての添え字が 0 の要素) の位置と同一です。 (添え字が 0 から始まらない場合、これは実際の最初の要素ではない可能性があります。)
- 各配列要素の型 (整数、ブール値、特定のクラスなど)。
- 配列のランク。
- 配列の範囲 (インデックスの範囲)。(多くの言語では、配列の開始インデックスは 0 または 1 に固定されていますが、終了インデックスは配列が (再) 割り当てられるときに設定されます。)
- 特定の時点で使用中の範囲が変化する可能性がある配列の場合、最大範囲と現在の範囲の両方が格納されることがあります。
- 配列のストライド、つまり配列の各要素が占有するメモリの量。
プログラムは、ドープ ベクトルを参照することで、配列 (または他のドープ ベクトルを使用するオブジェクト) を参照できます。これは、高級言語では一般的に自動的に行われます。配列の要素を取得するには、少しコストがかかります (通常、ドープ ベクトルから実際のデータへのポインターを取得する 1 つの命令)。一方、他の多くの一般的な操作は、より簡単かつ高速です。
- ドープ ベクトルがなければ、配列内の要素の数を決定することは不可能です。したがって、配列の末尾に「予約済み」値 (NULL など) を持つ追加の要素を追加するのが一般的です。その後、配列を前方にスキャンし、この「終了マーカー」に達するまで要素をカウントすることで、長さを決定できます。もちろん、これにより、ドープ ベクトルで直接長さを検索するよりも、長さのチェックがはるかに遅くなります。
- 配列の範囲がわからないと、不要になったときにそのメモリをfree() (割り当て解除) することはできません。したがって、dope ベクターがなければ、その長さをどこか別の場所に格納する必要があります。たとえば、特定の OS に 3200 バイトの配列の領域を割り当てるように要求すると、場所 M に 3204 バイトが割り当てられる可能性があります。次に、サイズを最初の 4 バイトに格納し、要求元のプログラムに、割り当てられた領域が M+4 から始まることを伝えます (そのため、呼び出し側は余分な 4 バイトを配列の一部として扱いません)。この余分なデータは dope ベクターとは見なされませんが、同じ目的の一部を達成します。
- ドープベクターがない場合、配列要素のストライド (または幅) に関する追加情報も保持する必要があります。Cでは、この情報はコンパイラによって処理され、コンパイラは「20 バイト幅の要素の配列へのポインタ」と「1000 バイト幅の要素の配列へのポインタ」のデータ型の区別を追跡する必要があります。これは、どちらの種類の配列の要素へのポインタも、次の要素または前の要素に到達するために増分または減分できることを意味しますが、配列の幅は早い段階で固定する必要があることも意味します。
ドープ ベクトルを使用しても、配列の特定のメンバーへのポインタ (のみ) を持つだけでは、配列内の位置、配列の場所、またはドープ ベクトル自体を見つけることはできません。必要な場合は、配列内の各要素にそのような情報を追加できます。このような要素ごとの情報は便利ですが、ドープ ベクトルの一部ではありません。
ドープベクターは、複数のデータ型（配列や文字列だけでなく）で共有できる汎用的な機能です。[2]
参照
参考文献
- ^ Pratt, T.; Zelkowitz, M. (1996).プログラミング言語: 設計と実装(第 3 版). Upper Saddle River, NJ : Prentice-Hall . p. 114. ISBN 978-0-13-678012-0。
- ^ Claybrook, Billy G. (1976 年 10 月 13 ～ 15 日)。「一般化されたデータ構造定義機能のためのテンプレート構造の設計」。ICSE '76: 第 2 回国際ソフトウェア工学会議。米国カリフォルニア州サンフランシスコ: IEEE Computer Society Press。pp. 408 ～ 413。