STLベクトルへの挿入

Question

C++ STLベクトルでは、N要素のベクトルを構築しており、 の理由で、ベクトルの前に挿入することを選択しました。ベクトルの前にあるすべての要素の挿入は、既存のすべての要素のシフトを強制的に1にします。これにより、ベクトル要素の（1 + 2 + 3 + ... + N） +1）シフト。

私の質問は（1 + 2 + 3 + ... N）、1 + 1 + 1.Nでなければならないと思っています。最初に？

ありがとうございます！

Answer 1

（vector::insertが記載されている）：

複雑：複雑さは、挿入要素の数を加えたベクトルの端までの距離で線形です。

要素を追加するたびに、ベクトルの最後までの距離が1増加します。

最初に要素を追加すると1が挿入され、最後までの距離は0なので、複雑さは1 + 0 = 1になります。2回目に1を挿入し、最後までの距離は1なので、複雑さは1 + 1 = 2です。3回目は最後までの距離が2なので、複雑さは1 + 2 = 3になります。これが1 + 2 + 3 + ... + Nのパターンである。

Answer 2

最初の値はN-1回シフトされ、新しい値が挿入されるたびに移動する必要があります。 2番目の値はN-2回だけシフトされます。なぜなら、後ろにN-2個の値が追加されるからです。次の値はN-3などにシフトされます。最後の値はシフトされません。

著者はなぜNについて話しているのか、N-1ではないのか分かりません。しかし、あなたの混乱の理由は、著者が単一の価値のシフトを数え、複数の単一価値のシフトを伴うシフトプロジェクションの数を数えるということです。

Answer 3

nには、現在ベクターに入っている要素がシフトされる必要があります（n）。 [vector.modifiers]/2から

vector<int> values; 
for (size_t i = 0; i < N; ++i) 
{ 
    //At this point there are `i` elements in the vector that need to be moved 
    //to make room for the new element 
    values.insert(values.begin(), 0); 
}