Which algorithm is Best ?

Question

In C++
There is Data Structure named Vector

It has initial capacity 1 and after in full it double it's capacity and copy old array into new and do it forever even we have only 1025 members it's capacity is still 2048

What if we use
calloc or mallic functions of c
And realloc memory for each new element
Thus we can save space and it's time complexity is also O(1) which is pure because we do not copy old element into it

Which algo. is good ?
Does my approach create any kind of Problem?

Answer 1

The first one is better because it does fewer reallocations and data moves. Both methods copy the old elements into the new space. Whenever realloc cannot expand the current memory location into contiguous memory, it allocs a new space and copies data.

Answer 2

In general, computers have lots of memory and plenty of speed, so the factors between the two approaches are marginal. But in specific conditions you must choose wisely. Still, in all cases it is better to expand the storage by more than one element at a time so there is less time taken to do the overhead operation. Limited memory may require you to expand the storage in smaller chunks rather than doubling every time - perhaps even one element at a time if more space is not available. Though if that is the case, your whole system is having serious performance problems.