What is an unbounded array?

Question

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)

Answer 1

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.}

Answer 2

A dynamically allocated array is a fixed-size array where the size is fixed when the array is created. It is the allocation that is dynamic when the array is created. Once it is created it is fixed.

Note that dynamically allocated is different from dynamic.

With an unbounded array, the size of the array can grow and shrink arbitrarily as you add items to and remove items from the array. An unbounded array often uses dynamically allocated arrays in the background. Essentially creating chunks / pools of memory using dynamically allocated arrays as an efficiency gain instead of continually resizing when a new item is added.

Looking at the code for an unbounded array from the article linked by TheCodeArtist:

struct ubarray {
    int limit; /* limit > 0 */
    int size; /* 0 <= size && size <= limit */
    elem[] A; /* \length(A) == limit */
};

Note that this array will grow as needed (when limit is reached), and that it is backed by a dynamically allocated array:

elem[] A; /* \length(A) == limit */

Answer 3

Two different concepts really. A statically or dynamically defined array is bounded as in the code that uses it needs to know what the bounds are. With an unbound array the code needs some way to discover the bounds from the array itself.

e.g

sArray = Array[2..10] Of Integer
dArray = Array[x..y] Of Integer

void DoSomethingToArray(Array Of Integer : myArray)
{
   for(int i = myArray.LowerBound; i <= myArray.UpperBound; i++)
   {
      // twiddle with it.
   }
} 

You could pass sArray or dArray to the function and it would be quite happy.

Lower and UpperBound are an option, While !Stack.Empty, List.Count > 0, an Enumerator, even Sizeof(myArray) / SizeOf(myArrayType) are all possibilities. The important point is that the code being passed the array, doesn't have to know how the array is bound and can take any array of a specific Type.

Setting the bounds of an array is about allocating memory essentially. A function that uses the array, should hopefully only care that it doesn't reference memory that wasn't allocated to the array.