What is an unbounded array?
arrays, data-structures, definition
Solution
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 index `size` which tracks how many elements are actually in the array. When we add a new element we increment `size`, when we remove an element we decrement `size`. The tricky issue is how to proceed when we are already at the `limit` and want to add another element. At that point, we allocate a new array with a larger `limit` 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.
Problem
What is an unbounded array and is there any difference between an unbounded array and a dynamically allocated array? What are the common operations associated with the unbounded array? (like we have pop and push for stack data structure)