Capacity management: Ensure Capacity, Pack
Capacity management mechanism should be developed first, before we can add or remove values. The mechanism consists of two functions: ensure capacity and pack.
Ensure capacity
Before value or several values is added, we should ensure, that we have enough capacity to store them. Do the following steps:
- check, if current capacity isn't enough to store new items;
- calculate new capacity by the formula: newCapacity = (oldCapacity * 3) / 2 + 1. Algorithm makes a free space reserve in order not to resize the storage too often.
- check if new capacity is enough to store all new items and, if not, increase it to store exact amount of items;
- allocate new storage and copy contents from the old one to it;
- deallocate the old storage (in C++);
- change the capacity value;
Enlargement coefficient can be chosen arbitrary (but it should be greater, than one). Proposed value is 1.5 and it is optimal on average.
Example. capacity = 6, size = 6, want to add 1 new item.
Pack
When items are removed, amount of the free space increases. If there are too few values in the dynamic array, unused storage become just a waste of space. For the purpose of saving space, we develop a mechanism to reduce capacity, when it is excessive.
- check, if size is less or equal, than half of the capacity;
- calculate new capacity by the formula: newCapacity = (size * 3) / 2 + 1. Algorithm leaves exact the amount of space, as if storage capacity had been trimmed to the size and then method to ensure capacity was called.
- allocate new storage and copy contents from the old one to it;
- deallocate the old storage (in C++);
- change the capacity value.
Example. capacity = 12, size = 6, do packing.
Lower boundary for size, after which packing is done, may vary. In the current example it is 0.5 of the capacity value. Commonly, pack is a private method, which is called after removal. Also, dynamic array interface provides a trim method, which reduces capacity to fit exact amount of items in the array. It is done from the outside of the implementation, when you are sure, that no more values to be added (for instance, input from user is over).
Code snippets
Both Java and C++ provides efficient tools to copy memory, which are used in the implementations below.
Java
import java.util.Arrays;
public class DynamicArray {
…
public void ensureCapacity(int minCapacity) {
int capacity = storage.length;
if (minCapacity > capacity) {
int newCapacity = (capacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
storage = Arrays.copyOf(storage, newCapacity);
}
}
private void pack() {
int capacity = storage.length;
if (size <= capacity / 2) {
int newCapacity = (size * 3) / 2 + 1;
storage = Arrays.copyOf(storage, newCapacity);
}
}
public void trim() {
int newCapacity = size;
storage = Arrays.copyOf(storage, newCapacity);
}
}
C++
#include <cstring>
void DynamicArray::setCapacity(int newCapacity) {
int *newStorage = new int[newCapacity];
memcpy(newStorage, storage, sizeof(int) * size);
capacity = newCapacity;
delete[] storage;
storage = newStorage;
}
void DynamicArray::ensureCapacity(int minCapacity) {
if (minCapacity > capacity) {
int newCapacity = (capacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
setCapacity(newCapacity);
}
}
void DynamicArray::pack() {
if (size <= capacity / 2) {
int newCapacity = (size * 3) / 2 + 1;
setCapacity(newCapacity);
}
}
void DynamicArray::trim() {
int newCapacity = size;
setCapacity(newCapacity);
}
| Previous: Dynamic array overview | Next: Dynamic array data access functions |
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!