4

std::vector の push_back は、引数として渡されたオブジェクトのコピーを最後に配置することを理解しています。

この簡単な例を考えてみましょう

class Foo
{
public:
  Foo(int i=-1) :i_(i) {std::cout << "Foo:" << i_ << std::endl;}

  Foo(const Foo& rhs) 
  {
    i_ = rhs.i_;
    std::cout << "Foo copy CTOR:" << i_ <<  std::endl;
  }

  ~Foo() {std::cout << "~Foo:" << i_ << std::endl;}

private:
  int i_;
};

そして、このコードの断片

void testObjects()
{
  std::vector<Foo> vFoo;

  for (int i=0; i < 3; i++)
  {
    std::cout << std::endl;
    Foo aFoo(i+100);
    vFoo.push_back(aFoo);
    std::cout << "i=" << i << " vector size=" << vFoo.size() 
              << std::endl;
  }
  std::cout << "end of loop - vector size=" << vFoo.size() 
            << std::endl << std::endl;
}

私が得ている結果は次のとおりです。

Foo:100
Foo copy CTOR:100
i=0 vector size=1
~Foo:100

Foo:101
Foo copy CTOR:100
Foo copy CTOR:101
~Foo:100
i=1 vector size=2
~Foo:101

Foo:102
Foo copy CTOR:100
Foo copy CTOR:101
Foo copy CTOR:102
~Foo:100
~Foo:101
i=2 vector size=3
~Foo:102
end of loop - vector size=3

~Foo:100
~Foo:101
~Foo:102

ベクターのサイズが 1 つ大きくなり (予想どおり)、その内容がシフトされ (下に?)、余分な (??) コピー構築が発生するという印象を受けました。私は正しいですか？

お時間をいただきありがとうございます。

よろしく

4

1 に答える 1

3

ベクトルの内容はシフトされません。それ以外の場合は、push_back()一定時間償却できません。

std::vector出力に基づいて、の実装は容量0または1で始まり、容量を超えると容量が2倍になると思います。あなたが見ているのは、ベクトルの内容のシフトではなく、内部メモリ バッファの再割り当てです。

確認するには、 の宣言の後に次の行を追加しますvFoo。

vFoo.reserve(16);

その後、余分なコピー コンストラクター呼び出しは表示されません。

または、ベクトルのサイズを大きくして (少なくとも 4 つまで) テスト コードを実行し、すべての要素のコピー構築がますます頻繁に行われないことを確認することもできます。長期的には、N 個の挿入に対して最大で O(log N) 個の再割り当てが必要です。

上記に当てはまらない場合はstd::vector、C++ 標準に準拠していない壊れた実装を使用していることを示しています。

于 2013-10-08T10:10:58.790 に答える