Unbounded arrays can be (and usually are) statically allocated.
The primary concern when implementing an unbounded array is to provide dynamic-array like freedom to decide the array size during run-time without the performance penalties of run-time memory allocation.
The following excerpt from an excellent article on unbounded arrays explains it succinctly -
The general implementation strategy is as follows. We maintain an array of a fixed length
limit
and an internal indexsize
which tracks how many elements are actually in the array. When we add a new element we incrementsize
, when we remove an element we decrementsize
. The tricky issue is how to proceed when we are already at thelimit
and want to add another element. At that point, we allocate a new array with a largerlimit
and copy the elements we already have to the new array.
Notice that during run-time, until size
exceeds the initial value of limit
there is no dynamic allocation involved with an unbounded array.
Some features (design requirements) of an unbounded array :
- Getting or setting the value at a particular index (constant time)
- Iterating over the elements in order (linear time, good cache performance)
- Inserting or deleting an element at the end of the array (constant amortized time)
Keeping performance in mind, the only additional operations(compared to regular arrays) associated with unbounded arrays are :
add_to_end()
delete_from_end()
to allow modifying the size of the unbounded array.
Operations like Insert_in_middle()
and Delete_in_middle()
are NOT provided keep in mind the primary design principle of an unbounded array i.e. performance.
For more details, checkout the answers to this question.
NOTE : Though the question specifically mentions dynamically allocated arrays, probably you might also want to checkout dynamic arrays. A good example of a dynamic-array is the C++ std::vector
itself which addresses several of the same design principles as that of an unbounded array.