## Arrays

Array-based data structures are fast for some applications, but they are relatively inflexible since the size of the array must be specified when it is allocated. The <#9066#>Array<#9066#> class solves this problem by allocating a fixed size initial array, and doubling it whenever it gets full. To cost of recopying the current contents is amortized over the size of the array. <#9067#>Array<#9067#> objects offer the ability to circumvent the standard <#9068#>Container<#9068#> iteration scheme, though the latter still works. Since the elements are stored in a contiguous block, it is much more efficient to iterate through them using pointer arithmetic. There is no need to package the data elements in structures from the <#9069#>ContainerNode<#9069#> hierarchy. The example in Figure~#fig:Array1#9057> illustrates both forms of iteration on the elements of an <#9070#>Array<#9070#> object: <#9058#>

Figure 2.11: Iteration and <#9105#>Array<#9105#> objects
#figure9058#

<#9058#> <#9106#>1. Creation<#9106#>
<#9108#>

<#9110#>

Figure 2.11: Iteration and <#9105#>Array<#9105#> objects
Array<#9155#>;SPMlt;<#9155#>Item<#9157#>;SPMgt;<#9157#> | a;

<#9110#>
<#9114#>

Creates an empty dynamic array. A default size of 62 * DEFAULT_SIZE (see general.h) is used. <#9159#>O(1)<#9159#>

<#9114#>

<#9108#>
<#9119#>

<#9121#>

Array<#9161#>;SPMlt;<#9161#>Item<#9163#>;SPMgt;<#9163#> | a( (int) sz);

<#9121#>
<#9125#>

Creates an dynamic array with a block of space large enough to store <#9127#>sz<#9127#> 63s. <#9165#>O(1)<#9165#>

<#9125#>

<#9119#>
<#9131#>

<#9133#>

Array<#9167#>;SPMlt;<#9167#>Item<#9169#>;SPMgt;<#9169#> | a( (Array<#9171#>;SPMlt;<#9171#>Item<#9173#>;SPMgt;<#9173#>&) a);

<#9133#>
<#9137#>

Creates an dynamic array with a block of space as large as that of <#9175#>a<#9175#> and initializes it with the elements of <#9177#>a<#9177#>. <#9179#>O(n)<#9179#>

<#9137#>

<#9131#>
<#9142#>

<#9144#>

Array<#9181#>;SPMlt;<#9181#>Item<#9183#>;SPMgt;<#9183#> | a( (Container<#9185#>;SPMlt;<#9185#>Item<#9187#>;SPMgt;<#9187#>&) c);

<#9144#>
<#9148#>

Creates an dynamic array with storage of default size and initializes it with the elements of <#9189#>c<#9189#>. Note that the storage may be reallocated during this process. <#9191#>O(n)<#9191#>

<#9148#>

<#9142#>
<#9153#>2. Operations<#9153#>
<#9201#>

<#9203#>

Array<#9417#>;SPMlt;<#9417#>Item<#9419#>;SPMgt;<#9419#>& | operator=(Array<#9421#>;SPMlt;<#9421#>Item<#9423#>;SPMgt;<#9423#>& a)

<#9203#>
<#9208#>

Allocate space large enough to hold the elements of <#9210#>a<#9210#>, then copy its contents.

<#9208#>

<#9201#>
<#9214#>

<#9216#>

ContainerNode * | insert(Item item)

<#9216#>
<#9221#>

Insert <#9223#>item<#9223#> into the 0'th cell of <#9402#>Array<#9402#>, shifting one cell forward any contiguous block of elements starting with that cell. If this operation would extend the active range of cells beyond the current allocation, reallocate the <#9403#>Array<#9403#> and recopy the elements. Note: The return type is <#9224#>ContainerNode*<#9224#> so that this method may be called from <#9404#>Container<#9404#> pointers or references. However, since there is no packaging node structure in <#9405#>Array<#9405#>, a NULL pointer is returned. <#9425#>O(n)<#9425#>

<#9221#>

<#9214#>
<#9228#>

<#9230#>

ContainerNode * | append(Item item)

<#9230#>
<#9235#>

The same as insert(Item item), except that the new item is added to the empty cell adjacent to the cell in the array's active range of largest index.

<#9235#>

<#9228#>
<#9240#>

<#9242#>

void | remove(Item item)

<#9242#>
<#9247#>

Remove the item from <#9406#>Array<#9406#> if it is there. Shift the elements of larger index to fill in the vacancy left by the removal. <#9427#>O(n)<#9427#>

<#9247#>

<#9240#>
<#9252#>

<#9254#>

Item | start()

<#9254#>
<#9259#>

Returns the address of the 0'th element of the <#9407#>Array<#9407#>. <#9429#>O(1)<#9429#>

<#9259#>

<#9252#>
<#9264#>

<#9266#>

Item | get()

<#9266#>
<#9271#>

Return the last element in the active range of the array and remove it. <#9431#>O(1)<#9431#> <#9273#>Caution:<#9273#> If the <#9408#>Array<#9408#>stores no elements, this routine returns an uninitialized <#9274#>Item<#9274#> object.

<#9271#>

<#9264#>
<#9278#>

<#9280#>

void | clear()

<#9280#>
<#9285#>

Remove all items from the active range of the <#9409#>Array<#9409#>. <#9433#>O(n)<#9433#>

<#9285#>

<#9278#>
<#9290#>

<#9292#>

Bool | memberQ(Item& item)

<#9292#>
<#9297#>

Is item in the array or not? <#9435#>O(n)<#9435#>

<#9297#>

<#9290#>
<#9302#>

<#9304#>

Bool | sortedQ() const

<#9304#>
<#9309#>

Return FALSE. <#9437#>O(1)<#9437#>.

<#9309#>

<#9302#>
<#9314#>

<#9316#>

int | order()

<#9316#>
<#9321#>

Return the number of cells allocated in the array. <#9439#>O(1)<#9439#>

<#9321#>

<#9314#>
<#9326#>

<#9328#>

int | size()

<#9328#>
<#9333#>

Return the active range of elements, defined to be (<#9441#>m-0<#9441#>, where <#9443#>m<#9443#> is the largest index of a referenced cell. <#9445#>O(1)<#9445#>

<#9333#>

<#9326#>
<#9338#>

<#9340#>

Item& | operator[] (int ix)

<#9340#>
<#9345#>

Return item of index ix. Bounds checking is done, and the element count is updated if the cell referenced has a larger index than that of any previous reference. <#9447#>O(1)<#9447#>

<#9345#>

<#9338#>
<#9350#>

<#9352#>

int | search(Item)

<#9352#>
<#9357#>

Search for an item in the active range of the array and return its index if it is found. Return -1 otherwise <#9449#>O(n)<#9449#> .

<#9357#>

<#9350#>
<#9362#>

<#9364#>

Item | min()

<#9364#>
<#9369#>

The <#9410#>Container<#9410#> method is redefined since faster iteration is possible in this class. <#9451#>O(n)<#9451#>

<#9369#>

<#9362#>
<#9374#>

<#9376#>

Item | max()

<#9376#>
<#9381#>

The <#9411#>Container<#9411#> method is redefined since faster iteration is possible in this class. <#9453#>O(n)<#9453#>

<#9381#>

<#9374#>
<#9386#>

<#9388#>

ostream& | display(ostream& os)

<#9388#>
<#9393#>

Output the list to the output stream <#9395#>os<#9395#>. Uses <#9396#>Container::displayItem(...)<#9396#> to display each element. <#9455#>O(n)<#9455#>

<#9393#>

<#9386#>