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#>