Details of C++ Vector push_back()

Question

I'm trying to debug a program, and in doing so have bumped up against my understanding of the C++ vector push_back() function.

To illustrate my point, I've written the following short program:

#include <iostream>
#include <vector>
#include <cstdlib>

using std::cout;
using std::endl;
using std::vector;

class Test {
private:
  int mTestMember;
public:
  Test(int val);
  Test(const Test&);

  int GetValue() const;
};

Test::Test(int val)
{
  cout << "Constructor\n";
  mTestMember = val;
}

Test::Test(const Test& test)
{
  cout << "Copy Constructor\n";
  mTestMember = test.mTestMember;
  cout << "mTestMember: " << mTestMember << endl;
}

int main(){

  vector<Test> tests;
  tests.push_back(Test(int(5)));
  cout<< endl;
  tests.push_back(Test(int(6)));
  cout << endl;
  tests.push_back(Test(int(7)));

  return(0);
}

and if I compile and run, I get the following output:

Constructor
Copy Constructor
mTestMember: 5

Constructor
Copy Constructor
mTestMember: 6
Copy Constructor
mTestMember: 5

Constructor
Copy Constructor
mTestMember: 7
Copy Constructor
mTestMember: 5
Copy Constructor
mTestMember: 6

It would appear that, in the process of the push_back() function, a copy is performed of the object that is passed as the argument to the push_back() function (which I already knew), and then the rest of the elements that were present in the pre-existing are also copied to the new vector starting from the front.

Am I correct in my understanding of the process?

Answer 1

std::vector stores its elements in an array. An array always has fixed size, so if you keep adding elements to a std::vector, its underlying array will eventually fill up. When the array is full and you add another element (via push_back or another member function that adds new elements), it must:

1. Create a new, larger array,
2. Copy or move^(*) the elements from the old array to the new array,
3. Insert the new element into the new array, and
4. Destroy the old array

This process is called reallocation. A correct implementation of std::vector should resize the array exponentially. The Visual C++ std::vector implementation uses a growth factor of 1.5x; other implementations may use a different growth factor.

---

^{(*) C++11 adds support for moving objects.}