ベクトルデータ構造とは

Question

私はベクトルをC++とJavaで知っていますが、動的配列と似ていますが、ベクトルデータ構造の一般的な定義は見つかりません。だからベクトルは何ですか？ Vectorは一般的なデータ構造（arrray、stack、queue、treeなど）ですか？それとも言語に応じたデータ型ですか？

Answer 1

これは、動的に割り当てられたスペースを持つ配列です。このスペースを超えるたびに、メモリ内の新しい場所が割り当てられ、古い配列が新しい場所にコピーされます。古いものは解放されます。

さらに、vectorは通常、必要以上に多くのメモリを割り当てます。したがって、新しい要素が追加されると、すべてのデータをコピーする必要はありません。

リストは非常に優れているように見えるかもしれませんが、必ずしもそうであるとは限りません。ベクトルを頻繁に（サイズの点で）変更しないと、コンピュータのキャッシュメモリは、メモリ空間内で連続しているので、リストよりもベクトルではるかによく機能します。欠点は、拡大する必要がある大きなベクターがある場合です。次に、大量のデータをメモリ内の別の領域にコピーすることに同意する必要があります。

さらに、新しいデータをベクトルの最後と前に追加することができます。ベクトルは配列のようなものなので、ベクトルの先頭に要素を追加するたびに、すべての配列をコピーする必要があります。ベクトルの最後に要素を追加する方がはるかに効率的です。リンクされたリストにはこのような問題はありません。

Vectorは、リスト、キュー、スタックは保持しないが、内部保持データをランダムアクセスします。

Answer 2

（複数の被験者にできたとしても、あなたの質問に）混乱を利用することができ語、数学から借りているコンピュータサイエンス/プログラミングに適用される「ベクター」、。

数学におけるベクターの最も単純な例では、基本数学を教えるために使用される数直線である（特に負の数、負の数を減算し、負の数の付加などを視覚化するために）。

ベクトルはある点からの距離と方向です。ベクトルデータ構造は、3Dグラフィックスエンジンで使用される構造内のX、Y、Zの3点、または2D点（ちょうどX、Y）であるため、議論を混乱させる理由です。このコンテキストでは、このような2つのポイントの減算がベクトルになります。ベクトルは、ソースオペランドの1つから他のオペランドへの移動距離と方向を表します。その記憶装置は、（メモリアドレス空間における点に類似している、または数直線上の）アドレスからの距離として表されるで

これは、STLベクトルまたはJavaベクターのような記憶装置に適用されます。

概念は配列に関連しています。なぜなら、配列はベクトルに割り当てられた記憶域である可能性がありますが、ベクトルは配列よりも大きな概念であるということです。ベクトルには開始点からの距離の概念が含まれていなければならず、配列の始点を開始点と考えると、配列の終わりまでの距離はそのサイズになります。

ベクトルを表すデータ構造体にはサイズが含まれている必要がありますが、配列にはサイズが含まれる記憶域がないため、割り当てられていると想定されます。つまり、配列を動的に割り当てると、その配列のサイズを格納するデータ構造はなく、プログラマはそのサイズを知っているか、または整数または長整数で格納することを前提にしなければなりません。

ベクトルデータ構造（たとえば、ベクトルクラスのデザイン）では、サイズを格納する必要があるため、最低限、開始点（配列のベースまたはメモリ内のいくつかのアドレス）があります。その点からの距離はサイズを示します。

実際には "RAM"になっていますが、説明にはまだ説明されていない点が1つあります。これはベクトルを記述するデータの一部でなければなりません。ベクトルがバイトを表し、メモリの記憶域が通常バイト単位で測定される場合、アドレスと距離（またはサイズ）はバイトのベクトルを表しますが、それ以外は何もありません。いくつかの構造のそれより高い考え方は、フロートやダブルのサイズ、C++の構造やクラスなどの独自のサイズを持っています。要素のサイズがどのようなものであっても、N個を格納するのに必要なメモリは、ベクトルデータ構造が何を格納しているか、その大きさについて何らかの知識が必要です。これは、「文字列のベクトル」や「点のベクトル」の観点から考える理由です。ベクトルには要素サイズも格納する必要があります。

したがって、基本的なベクトルデータ構造を有していなければならない：

アドレス（起点）

素子のサイズを（それが記憶する各ものがXバイト長である）

要素の数格納されます（エレメントのサイズが「最小」のストレージ・サイズの要素の数です）。

ベクトルデータ構造のこの単純な3項目のリストで行われた重要な「仮定」は、アドレスにはメモリが割り当てられており、ある時点で解放されなければならず、ベクトル。

これは、何か不足していることを意味します。ベクトルクラスを動作させるためには、ベクトルに格納されているITEMSの数と、その記憶域に割り当てられたメモリの量との間に認識可能な違いがあります。通常、STLからのベクターの使用から分かるように、10個のアイテムを格納する余地があることを「知っている」かもしれませんが、現在は2個しかありません。

したがって、ワーキングベクタークラスでは、メモリ割り当て量を格納する必要があります。これは、自動的にストレージを拡張するのに十分な情報を持つように、動的に拡張する方法です。

ベクタークラスをどのように動作させるかを考えてみると、ベクタークラスを操作するために必要なデータ構造が得られます。