STL ベクトルのストレージが初期化されていませんか?

https://stackoverflow.com/questions/96579

01-07-2019
|

質問

配置する必要がある内部ループを作成しています struct連続ストレージ内にあります。これが何個あるか分かりません struct事前にあります。私の問題は、STL vector は値を 0 に初期化するため、何をしても、初期化のコストに加えて、 structのメンバーを自分の価値観に合わせます。

初期化を防ぐ方法はありますか、それともサイズ変更可能な連続ストレージと初期化されていない要素を備えた STL のようなコンテナはありますか?

(コードのこの部分は最適化する必要があると確信しており、初期化には多大なコストがかかると確信しています。)

また、初期化がいつ行われるかについては、以下の私のコメントを参照してください。

いくつかのコード:

void GetsCalledALot(int* data1, int* data2, int count) {
    int mvSize = memberVector.size()
    memberVector.resize(mvSize + count); // causes 0-initialization

    for (int i = 0; i < count; ++i) {
        memberVector[mvSize + i].d1 = data1[i];
        memberVector[mvSize + i].d2 = data2[i];
    }
}

解決

std::vector 何らかの方法で配列内の値を初期化する必要があります。これは、何らかのコンストラクター (またはコピーコンストラクター) を呼び出す必要があることを意味します。の動作 vector 配列の初期化されていないセクションに、初期化されているかのようにアクセスした場合、(または任意のコンテナクラス) は未定義になります。

最良の方法は使用することです reserve() そして push_back(), そのため、コピーコンストラクターが使用され、デフォルトの構築が回避されます。

サンプルコードを使用すると、次のようになります。

struct YourData {
    int d1;
    int d2;
    YourData(int v1, int v2) : d1(v1), d2(v2) {}
};

std::vector<YourData> memberVector;

void GetsCalledALot(int* data1, int* data2, int count) {
    int mvSize = memberVector.size();

    // Does not initialize the extra elements
    memberVector.reserve(mvSize + count);

    // Note: consider using std::generate_n or std::copy instead of this loop.
    for (int i = 0; i < count; ++i) {
        // Copy construct using a temporary.
        memberVector.push_back(YourData(data1[i], data2[i]));
    }
}

電話をかけるときの唯一の問題 reserve() （または resize()) このように、コピーコンストラクターを必要以上に頻繁に呼び出すことになる可能性があります。配列の最終的なサイズを適切に予測できる場合は、次のようにすることをお勧めします。 reserve() 最初にスペースを 1 回入れます。ただし、最終的なサイズがわからない場合でも、少なくともコピー数は平均して最小限になります。

現在のバージョンの C++ では、一時的な値がスタック上に構築され、ベクトルメモリにコピー構築され、最後に一時的な値が破棄されるため、内部ループは少し非効率的です。ただし、C++ の次のバージョンには、R 値参照と呼ばれる機能があります (T&&）それは役に立ちます。

によって提供されるインターフェイス std::vector デフォルト以外の値を構築するためにファクトリのようなクラスを使用するという別のオプションは許可されません。このパターンを C++ で実装するとどうなるかを示す大まかな例を次に示します。

template <typename T>
class my_vector_replacement {

    // ...

    template <typename F>
    my_vector::push_back_using_factory(F factory) {
        // ... check size of array, and resize if needed.

        // Copy construct using placement new,
        new(arrayData+end) T(factory())
        end += sizeof(T);
    }

    char* arrayData;
    size_t end; // Of initialized data in arrayData
};

// One of many possible implementations
struct MyFactory {
    MyFactory(int* p1, int* p2) : d1(p1), d2(p2) {}
    YourData operator()() const {
        return YourData(*d1,*d2);
    }
    int* d1;
    int* d2;
};

void GetsCalledALot(int* data1, int* data2, int count) {
    // ... Still will need the same call to a reserve() type function.

    // Note: consider using std::generate_n or std::copy instead of this loop.
    for (int i = 0; i < count; ++i) {
        // Copy construct using a factory
        memberVector.push_back_using_factory(MyFactory(data1+i, data2+i));
    }
}

これを行うには、独自のベクタークラスを作成する必要があることを意味します。この場合、単純な例であるはずのものも複雑になります。ただし、このようなファクトリ関数を使用した方が良い場合もあります。たとえば、挿入が他の値に条件付きであり、実際には必要ではない場合でも、高価な一時関数を無条件に構築する必要がある場合などです。

他のヒント

C++0x は新しいメンバー関数テンプレートを追加します emplace_back に vector (可変引数テンプレートと完全転送に依存します)、一時変数を完全に削除します。

memberVector.emplace_back(data1[i], data2[i]);

reserve() 応答について明確にするには、次のようにします。reserve() を Push_back() と組み合わせて使用する必要があります。このように、デフォルトのコンストラクターは各要素に対して呼び出されるのではなく、コピーコンストラクターが呼び出されます。構造体をスタック上に設定してからベクターにコピーするというペナルティが依然として発生します。一方、使用すると、次の可能性があります。

vect.push_back(MyStruct(fieldValue1, fieldValue2))

コンパイラは、ベクトルに属するメモリ内に新しいインスタンスを直接構築します。それはオプティマイザがどれだけ賢いかによって決まります。それを確認するには、生成されたコードをチェックする必要があります。

C++11 (およびブースト) では、次の配列バージョンを使用できます。 unique_ptr 初期化されていない配列を割り当てます。これは完全な stl コンテナではありませんが、それでもメモリ管理されており、C++ っぽいので、多くのアプリケーションには十分です。

auto my_uninit_array = std::unique_ptr<mystruct[]>(new mystruct[count]);

ここで問題が発生します。サイズ変更は挿入を呼び出し、新しく追加された要素ごとにデフォルトで構築された要素からコピー構築を実行します。これをコスト 0 にするには、独自のデフォルトコンストラクターと独自のコピーコンストラクターを空の関数として記述する必要があります。これをコピーコンストラクターに対して実行すると、 とても悪い考え std::vector の内部再割り当てアルゴリズムが壊れてしまうためです。

まとめ：std::vector ではこれを行うことはできません。

エラー...

方法を試してください:

std::vector<T>::reserve(x)

これにより、何も初期化せずに x 項目用に十分なメモリを予約できるようになります (ベクトルはまだ空です)。したがって、x を超えるまで再割り当ては行われません。

2 番目の点は、vector は値を 0 に初期化しないということです。コードをデバッグでテストしていますか?

g++ で検証すると、次のコードになります。

#include <iostream>
#include <vector>

struct MyStruct
{
   int m_iValue00 ;
   int m_iValue01 ;
} ;

int main()
{
   MyStruct aaa, bbb, ccc ;

   std::vector<MyStruct> aMyStruct ;

   aMyStruct.push_back(aaa) ;
   aMyStruct.push_back(bbb) ;
   aMyStruct.push_back(ccc) ;

   aMyStruct.resize(6) ; // [EDIT] double the size

   for(std::vector<MyStruct>::size_type i = 0, iMax = aMyStruct.size(); i < iMax; ++i)
   {
      std::cout << "[" << i << "] : " << aMyStruct[i].m_iValue00 << ", " << aMyStruct[0].m_iValue01 << "\n" ;
   }

   return 0 ;
}

次の結果が得られます。

[0] : 134515780, -16121856
[1] : 134554052, -16121856
[2] : 134544501, -16121856
[3] : 0, -16121856
[4] : 0, -16121856
[5] : 0, -16121856

あなたが見た初期化はおそらくアーティファクトでした。

[編集] サイズ変更に関するコメントの後、コードを変更してサイズ変更行を追加しました。サイズ変更は、ベクター内のオブジェクトのデフォルトコンストラクターを効果的に呼び出しますが、デフォルトコンストラクターが何も行わない場合、何も初期化されません。私は今でもそれがアーティファクトだと信じています (次のコードを使用して初めてベクトル全体をゼロにすることができました:

aMyStruct.push_back(MyStruct()) ;
aMyStruct.push_back(MyStruct()) ;
aMyStruct.push_back(MyStruct()) ;

それで...:-/

[編集2] Arkadiyがすでに提供しているように、解決策は、必要なパラメータを受け取るインラインコンストラクタを使用することです。何かのようなもの

struct MyStruct
{
   MyStruct(int p_d1, int p_d2) : d1(p_d1), d2(p_d2) {}
   int d1, d2 ;
} ;

これはおそらくコードにインライン化されるでしょう。

ただし、プロファイラーを使用してコードを調査し、このコード部分がアプリケーションのボトルネックであることを確認する必要があります。

std::vector::reserve() メソッドを使用します。ベクトルのサイズは変更されませんが、スペースが割り当てられます。

他の投稿者へのコメントから、あなたには malloc() とその友達が残っているようです。Vector では、構築されていない要素を使用できません。

コードからは、それぞれ 2 つの int で構成される構造体のベクトルがあるように見えます。代わりに int の 2 つのベクトルを使用できますか?それから

copy(data1, data1 + count, back_inserter(v1));
copy(data2, data2 + count, back_inserter(v2));

これで、構造体のコピーに毎回料金を支払う必要がなくなります。

どうしても要素を初期化しないことを主張し、front()、back()、push_back() などのメソッドを犠牲にする場合は、 numeric からのブーストベクトルを使用してください。これにより、resize() を呼び出すときに既存の要素を保持しなくても済みます...

何も行わないデフォルトのコンストラクターを使用して、要素型の周囲にラッパー型を使用できます。例えば。：

template <typename T>
struct no_init
{
    T value;

    no_init() { static_assert(std::is_standard_layout<no_init<T>>::value && sizeof(T) == sizeof(no_init<T>), "T does not have standard layout"); }

    no_init(T& v) { value = v; }
    T& operator=(T& v) { value = v; return value; }

    no_init(no_init<T>& n) { value = n.value; }
    no_init(no_init<T>&& n) { value = std::move(n.value); }
    T& operator=(no_init<T>& n) { value = n.value; return this; }
    T& operator=(no_init<T>&& n) { value = std::move(n.value); return this; }

    T* operator&() { return &value; } // So you can use &(vec[0]) etc.
};

使用するには:

std::vector<no_init<char>> vec;
vec.resize(2ul * 1024ul * 1024ul * 1024ul);

構造体自体は連続したメモリ内にある必要がありますか、それとも struct* のベクトルを持たせても問題ありませんか?

ベクトルは、追加したものすべてのコピーを作成するため、オブジェクトではなくポインターのベクトルを使用することがパフォーマンスを向上させる 1 つの方法です。

STL があなたの答えではないと思います。realloc() を使用して独自のソリューションを作成する必要があります。ポインターと要素のサイズまたは数を保存し、それを使用して realloc() の後に要素の追加を開始する場所を見つける必要があります。

int *memberArray;
int arrayCount;
void GetsCalledALot(int* data1, int* data2, int count) {
    memberArray = realloc(memberArray, sizeof(int) * (arrayCount + count);
    for (int i = 0; i < count; ++i) {
        memberArray[arrayCount + i].d1 = data1[i];
        memberArray[arrayCount + i].d2 = data2[i];
    }
    arrayCount += count;
}

私なら次のようなことをします:

void GetsCalledALot(int* data1, int* data2, int count)
{
  const size_t mvSize = memberVector.size();
  memberVector.reserve(mvSize + count);

  for (int i = 0; i < count; ++i) {
    memberVector.push_back(MyType(data1[i], data2[i]));
  }
}

memberVector に格納されている型の ctor を定義する必要がありますが、両方の長所を活用できるため、コストはわずかです。不要な初期化は行われず、ループ中に再割り当ては発生しません。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow