43

Stanley B.Lippman、Josee Lajoie、Barbara E. Moo による C++ Primer 第 4 版では、次のように述べられています。

ベクトルは効率的に成長するため、通常は、要素の値がわかっているときに要素を動的に追加してベクトルを成長させるのが最善です。

と

c や Java の使用に慣れている読者は、ベクトル要素が連続して格納されるため、予想されるサイズでベクトルを事前に割り当てることが最善であると考えるかもしれません。実は逆なんですが…

と

ベクトルに指定された数の要素を事前に割り当てることができますが、通常は空のベクトルを定義して要素を追加する方が効率的です。

これが正しいと仮定すると (著者は評判が高く、C++ 自体の共著者でもあります)、誰かがこの声明を証明するケースを私に与え、その理由を説明できますか?

4

3 に答える 3

40

場合によります。

最終的なサイズがわからない場合は、その割り当てスキームを使用してベクターを割り当てます (通常は毎回 2 倍にするか、そのあたりのどこかで)。このようにして、すべての要素の再割り当てを回避します。

std::vector<int> v;

// good:
for (/* populate v */) // unknown number of iterations
{
    v.push_back(i); // possible reallocation, but not often
}

// bad:
for (/* populate v */) // unknown number of iterations
{
    v.reserve(v.size() + 1); // definite reallocation, every time
    v.push_back(i); // (no reallocation)
}

ただし、事前に再割り当てしないことがわかっている場合は、事前に割り当てます。

std::vector<int> v;

// good:
v.reserve(10); 
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // no reallocations
}

// not bad, but not the best:
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // possible reallocation, but not often (but more than needed!)
}
于 2012-08-09T17:02:15.970 に答える
6

かもね。要素が何であるか、それらをコピーまたは構築するのにどれだけの作業が必要か、そして要素の数に大きく依存します。

ベクトルを事前に割り当てると、各要素のデフォルトのコンストラクターを呼び出して空の要素を作成し、後でスペースにアイテムをコピーすることになります。要素を追加すると、要素をその場でコピーまたは構築できるため、より効率的になります。

于 2012-08-09T16:57:50.977 に答える