1

std::vector要素がメモリ内で連続していることが保証されていることは知っています。

では、他のベクトルを含むベクトルのコレクション全体が連続していると期待できないのはなぜでしょうか?

ベクターは、囲まれたアイテムの連続したメモリレイアウトを保証することになっています。それらのエンクロージャーもベクターである場合、最上位のベクターの完全なコンテンツが連続したメモリにあると予想されます。

しかし、これが正しいかどうかについては、いくつかの論争があるようです。安全に信頼できるかどうか。一部の人々はこれを達成するために道を踏み外しているようですが、私はそれが保証されていると思います.

4

6 に答える 6

3

これに答える最も正しい正式な方法 (既存の実装を説明するのではなく) は、§23.3.6.1/1 に基づいていると思います。

[...] ベクトルの要素は連続して格納されます。つまり、T が bool 以外の型である場合、恒等式に従いますv。vector<T, Allocator>

&v[n] == &v[0] + n

すべてのために0 <= n < v.size()。

これ&v[i]は、ベクトルの個々の要素のアドレスについて述べており、特に、ベクトルの各要素のサイズが一定であることを意味していることに注意してくださいsizeof(T)(ポインタ演算がそのように機能するため)。

これは、実行時にベクトルの要素のサイズを変更できないことを意味します。avector<vector<T>>が 1 つの連続したメモリ ブロックとして実装されている場合、それ自体がベクトルである外部ベクトルのメンバーは、サイズを変更できます。

したがって、余分なレベルの間接性が必要です。つまり、個々のベクトルには、別の場所に格納されている可変サイズのデータ​​構造へのある種のポインタが含まれている必要があります。

于 2013-04-05T01:43:33.567 に答える
3

ベクトルは、実際の配列へのポインターを含むオブジェクトです。

ベクトルのベクトルは、オブジェクトの配列へのポインターを持つオブジェクトになります。各オブジェクトは、ヒープ上の別の場所にある独自の配列を指します。いいえ、あなたが求めている方法でそれらが連続することは決してありません。

于 2013-04-05T00:49:28.217 に答える
0

簡単に言えば、std::vector は、要素が連続して格納されることを保証します。ただし、要素のメンバーデータのみが含まれます。ベクターの場合、そのサイズ、容量などに加えて、実際のベクターデータへのポインターが含まれます。

そのため、ベクトルのベクトルはベクトルの連続したベクトルを提供しますが、それらのベクトルのデータは任意のメモリ アドレスに動的に割り当てられます。

オブジェクトのサイズはコンパイル時に知る必要があるため、さまざまなサイズのオブジェクトを持つことはできません。これを行う唯一の方法は、動的メモリ割り当てを使用することです。内部で動的メモリ割り当てを使用しない固定サイズのカスタム ベクトルがある場合はstd::vector<customVector>、customVectors を連続して格納しますが、customVector 要素データの実際の連続性を「中断」する追加の補助メンバーがまだあります。

于 2013-04-05T01:20:52.833 に答える
0

vector の (論理) メモリ レイアウトを見てみましょう。

[size:4/8 bytes]
[capacity:4/8 bytes]
[other datamembers:n bytes]
*[elements:size*sizeof(element) bytes] << one contiguous memory (pointer to heap)

ベクトルのベクトルを使用すると、次のようになります。

[size:4/8 bytes]
[capacity:4/8 bytes]
[other datamembers:n bytes]
* [
    [Vector:0]
        [size:4/8 bytes]
        [capacity:4/8 bytes]
        [other datamembers:n bytes]
        *[elements:size*sizeof(element) bytes] << pointer to contiguous memory for elements
    [Vector:1]
        [size:4/8 bytes]
        [capacity:4/8 bytes]
        [other datamembers:n bytes]
        *[elements:size*sizeof(element) bytes]
    [Vector:2]
        [size:4/8 bytes]
        [capacity:4/8 bytes]
        [other datamembers:n bytes]
        *[elements:size*sizeof(element) bytes]
    ...
    ...
] << contiguous memory of vectors

これは、ベクトルがベクトルを格納する連続したメモリへのポインタを持ち、各ベクトルが要素を格納する連続したメモリを持つ別のヒープを指す要素を格納することを意味します。

しかし、ベクトルで使用されるアロケータを作成して、連続するメモリ ブロックを割り当てることができたとしても、ネストされたベクトルの 1 つが削除されると、メモリが連続しなくなるという問題に直面することになります。ネストされたベクトルのサイズが異なる状況は言うまでもありません。

ユースケースに応じて、ベクトルのベクトルに顧客の連続ブロック メモリ アロケータを使用するか、メモリの 1 つの連続ブロックを手動で割り当ておよび割り当て解除する古い方法で行うことができます。

于 2013-04-05T00:50:01.837 に答える
0

問題は、ベクター テンプレートには、「インライン」または直接処理するデータが含まれていないことです。別の言い方をすれば、ベクトル クラスはそれが保持するデータ配列をボックス化します。ベクトル クラスは、要素の配列を含むメモリ領域へのポインタを保持します。構造的には次のものと同等です。

template <typename T>
struct vector_eq {
    T *ptr;
};

そしてそうではない

template <typename T>
struct vector_neq {
    T arr[SIZE];
};

要素を構造体に含めるには、SIZEコンパイル時に知る必要があります (つまり、 a constexpr) 。arr

メモリの単一ブロックへのポインタを含むように特化vector<vector<T>>し、そのメソッドがそのメモリ ブロックのスライスを共有するアドホック インスタンスを返すようにすることは可能だと思いますvector<T>が、その背後にあるロジックはおそらく少し複雑です。

于 2013-04-05T01:04:50.013 に答える