CODEWITHSUNDEEP
javac++
rookie
rookie

Reputation: 7883

appending an existed array

I have some question about arrays, I'm reading some book about Java, and now I was reading about class StringBuilder, I was taught that this class saves my string in array with current capacity, in the case that the capacity is not sufficient, this class automatically increases capacity capacity = 2*(capacity + 1), when I was studying c and c++, I was taught to do the same things if I don't have enough space in my array, but what is the logic behind this statement? why can't I just find out how much memory do I need and then to do capacity = capacity + homMuchDoINeed(), or why not capacity = 4 * capacity, thanks in advance for the answers

Upvotes: 0

Views: 92

Answers (5)

Peter Lawrey
Peter Lawrey

Reputation: 533720

If you know how much capacity you need, you can provide the capacity for the collection when you start. The doubling code assumes you don't know how much memory you will eventually need (or at least don't want to worry about it)

Upvotes: 0

fredoverflow
fredoverflow

Reputation: 263250

why can't I just find out how much memory do I need and then to do

capacity = capacity + homMuchDoINeed()

Because then you need to allocate new memory with each insertion, so a single insertion takes linear time, and n insertions take quadratic time. If, on the other hand, you grow by a constant factor like x2 or x1.5, a single insertion takes amortized constant time, and n insertions take linear time.

Stephan T. Lavavej explains this in multiple videos, for example, this one.

Upvotes: 2

neurolabs
neurolabs

Reputation: 542

The automatic increase is just a rule of thumb in order to minimize object construction.

If you know how many elements will be appended, and that no more elements will be appended in the future, it is better to explicitly specify the size in order to save memory. In Java you can do this with:

Arrays.copyOf(oldArray, newSize)

If you're not sure that no more elements will be appended to the array, in java you could just use an ArrayList, since it takes care of the resizing transparently using this rule of thumb:

int newCapacity = (oldCapacity * 3)/2 + 1;

Upvotes: 1

Palmik
Palmik

Reputation: 2665

capacity = C * (capacity + K) is usually better than capacity = capacity + K because you do not have to reallocate that often, and capacity = C * capacity is not viable at all (what if the current capacity was 0?).

However, I advice you to use standard containers if possible.

Upvotes: 0

Eamorr
Eamorr

Reputation: 10022

Just use ArrayList

Upvotes: 0

Related Questions