Given the following implementation of vector: :push.back trace through the cost

Question

Given the following implementation of vector: :push.back trace through the cost of the first 10 pushbacks, if a "cheap" pushback (i.e., a single copy) has a cost of 1, and the initia size and capacity are 0. void vector: : push_back(int x) f if(size capacity) ( // Full, reallocate to make room int* old.data data; data new int[1 5 capacity 3]; // Copy everything to the new array for(int i 8; i capacity; ++i) data[i] old.data[i]; capacity 15capacity / 3; deletel] old.data; // Add new element datalsize++] x;

Explanation / Answer

Initially the size and capacity are 0

size = 0

capacity = 0

cost = 0

1 + 5 * capacity / 3

1 + 5 * 0 / 3

1

is created. Also, nothing is copied from old_data. So, no cost for this operation. Then the new element is added. Now

size = 1

capacity = 1

cost = 0

1 + 5 * capacity / 3

1 + 5 * 1 / 3

2

is created. Also, 1 element is copied from old_data. So, cost of 1 for this operation. Then the new element is added. Now

size = 2

capacity = 2

cost = 1

1 + 5 * capacity / 3

1 + 5 * 2 / 3

4

is created. Also, 2 elements are copied from old_data. So, cost of 2 for this operation. Then the new element is added. Now

size = 3

capacity = 4

cost = 3

size = 4

capacity = 4

cost = 3

1 + 5 * capacity / 3

1 + 5 * 5 / 3

9

is created. Also, 4 elements are copied from old_data. So, cost of 4 for this operation. Then the new element is added. Now

size = 5

capacity = 9

cost = 7

size = 9

capacity = 9

cost = 7

1 + 5 * capacity / 3

1 + 5 * 9 / 3

16

Also, 9 elements are copied. So, the cost of 9 for this operation. So,

size = 10

capacity = 16

cost = 7 + 9 = 16

If you consider adding a new element as cost too. Then,

cost = 16 + 10 = 26

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.