To track capacity, capacity() returns the total amount of capacity in the devector, and capacity_front() and capacity_back() return size() + the amount of free capacity at that end.
The operations clear, reserve, and resize have two variants, one that puts the free capacity in the front, one for the back. The default is to put the free space in the back. For example:
clear_back() -> clears the vector and increases capacity_back() by size()
clear_front() -> clears the vector and increases capacity_front() by size()
clear() -> calls clear_back()
In some scenarios assign and operator= also create free capacity -- this is put at the back. The operations erase, pop_back, pop_front generate free capacity at the end that is closest to their operation.
The goal of the allocation strategy is to grow the total capacity of the devector if needed, but also reclaim unused capacity from one end and hand it to the other.
A request can come in to increase the amount of capacity at the back or the front. If there was no memory allocated at all yet, it will allocate space for 1 element at the requested end and the below doesn't apply.
We acquire an amortized constant insert at either end by creating at least 1/3 * size() free space at the requested end. In this process we steal 1/2 of the free space of the other end. This allows capacity to flow between the ends. We get the following two formulas for how much free space we want on this end and the other end:
new_free_this = size() >= 16 ? size() / 3 : size()
new_free_other = free_other / 2
Iff new_free_this + size() + new_free_other > capacity() a new allocation is made using the formula:
new_capacity = capacity() >= 16 ? capacity() * 1.5 : capacity() * 2
The elements are then moved to the new location such that there is new_free_other free space at the other end, the elements in the middle, and the rest of the free space at the requested end. If a new allocation was made the old memory is deallocated.