Copies made of object during push_back()

I have some code where I'm pushing objects onto a vector using push_back(). The class is counting how many times the object is being copied and I'm displaying the copy total after each push_back(). Not knowing anything about how push_back() is implemented I was just curious as to why the copy totals amass like this: 1, 3, 6, 7, 12, 13, 14, 15, 24, 25? I'm especially curious about the jump from 1 to 3 after the second push_back().

The code in question is simply:

Code:

---

while (read(in, record))
 {
    students.push_back(record);
    Student_info::show_info(); // prints copy total
    cout << endl;
}

---

The read() function doesn't make any copies.

Quote:

---

Originally Posted by Sharke

Not knowing anything about how push_back() is implemented I was just curious as to why the copy totals amass like this: 1, 3, 6, 7, 12, 13, 14, 15, 24, 25? I'm especially curious about the jump from 1 to 3 after the second push_back().

---

In order to conform to the requirement that push_back() take amortised constant time, the vector has to increase its capacity by a factor whenever the size is equal to the capacity and a new element is to be pushed back. This may require creating a new dynamic array and copying over the existing elements.

Interesting! I would never have guessed there was a timing requirement....

Quote:

---

Originally Posted by Sharke

Interesting! I would never have guessed there was a timing requirement....

---

It's more of an worst-case average timing requirement. There's no guarantee that any particular call of push_back() will occur within a particular time.

Amortised constant time means there is an asymptotic upper bound for the worst-case average time to perform an operation. It is not guaranteed that one operation will occur within constant time, but it is guaranteed (for large enough n) that the time for n operations will approach time O(n).

The philosophy is that expensive operations (eg reallocating the storage and copying elements) only execute occasionally and less expensive operations (initialising an unused element of an already-allocated array to a particular value) are executed more often. When averaged across a reasonably large number of operations, this is less expensive, computationally, than requiring every call of push_back() reallocating new memory, copying existing elements to that memory, and releasing the old memory.