std :: vector push_back() semantics

Question

Я понимаю, что push_back в std :: vector помещает копию объекта, переданного в качестве аргумента в конце.

Рассмотрим этот простой пример

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 

У меня впечатление о вектор увеличивает его размер на единицу (как и ожидалось), и его содержимое сдвигается (вниз?), вызывая дополнительные (??) копирования строительство. Я прав?

Я благодарю вас за ваше время.

Привет

Answer 1

Содержимого вектора не смещается, в противном случае push_back() не может быть амортизируются постоянное время.

Основываясь на выходе, я думаю, что ваша реализация std::vector начинается с емкости 0 или 1 и удваивает емкость при ее превышении. То, что вы видите, это не смещение содержимого вектора, а перераспределение буфера внутренней памяти.

Чтобы проверить, добавьте эту строку после объявления vFoo:

vFoo.reserve(16); 

Вы не должны увидеть дополнительный конструктор копирования требует после этого.

В качестве альтернативы вы можете запустить тестовый код до более высоких размеров вектора (как минимум до 4) и убедиться, что конструкции копирования всех элементов происходят реже и реже. В конечном счете должно быть не более O (log N) перераспределений для N вставок.

Если это не так, это означает, что вы используете сломанную реализацию std::vector, которая не соответствует стандарту C++.