![[Diagram showing a pointer to a vector of pointers to (small) vectors of array elements]](ArrayInternals.gif)
GCO4020/CSC428 - Advanced Object Oriented Techniques In C++
Week 1
The Standard Template Library¤ provides a number of array-like class
templates: vector, list, and deque, with a sophisticated
and unifying iterator access idiom. In this topic we will examine
aspects of the interface¤ and implementation¤ of a
much simpler array-like container with features not found in the STL¤
version.
The main feature of the Array class template presented here
is that it is
implemented as a "vector¤ of buckets". This two-step allocation
strategy strikes an unusual balance between the (time-)cost of
insertion against the (space-)cost of storage (see "Concept overview").
Array class
ElementType
Array
Array
Array(void) constructor
Array single-element constructor and copy constructor
Array::Size nested class and associated Array constructors
~Array destructor
Array
Array elements
Array
Array
Array
Arrays for equality
One of the problems in implementing an efficient array class is that the requirements of the accessor functions¤ and the internal memory management are in conflict.
The accessor functions¤ need to provide fast (preferably constant-time) access to individual elements of the array, and therefore mandate that a C++ vector¤ of elements (which can be indexed in constant time) be used.
The memory management functions seeks to provide fast (preferably constant-time) reallocation of internally allocated memory. But the reallocator's performance may severely compromised by the use of C++ vectors¤, since, when the allocated vector¤ is full, a new (larger) vector¤ must be allocated and the existing elements copied across to it. If many elements are stored and/or those elements are individually expensive to copy, reallocation will be unacceptably slow.
The Array class described below uses a two-stage allocation
strategy to balance and minimize access and reallocation costs. For a
given type of element (ElementType), instead of storing array
elements in a vector¤ of ElementType pointed to by an
ElementType*, the Array class stores a vector¤ of vectors¤ of
ElementType pointed to by an ElementType**. That is,
internally an Array object looks like this:
rather than this:
![[Diagram showing a pointer to a single (long) vector of array elements]](NotArrayInternals.gif)
Each of the small vectors¤ of ElementType (which we shall hereafter
refer to as "buckets") is of a fixed size, which is a multiple of 2 to
simplify indexing (see "Accessing elements" below). Each
bucket is allocated only once. When extra space is required, a new
vector¤ of pointers to buckets (hereafter called a "bucket vector¤") is
allocated and each bucket pointer is copied across.
Hence for an Array with B buckets storing E elements each, if the
total element storage space (E×B) is required to double,
instead of copying the entire E×B elements, only B pointers
need be copied. This is a significant improvement, not only because of
the 1/E reduction in the number copies, but also because each copy is
only of a single ElementType* pointer, rather than of an entire
ElementType object.
See also: Exercise 1
The declaration of the Array class template is shown below
(see source code listing: Array.C).
Note that Array is templated only on the type of the element to
be stored (not on its ordering behaviour or its storage allocation
mechanism, as in the STL¤).
template <class ElementType>
class Array
{
private:
enum
{
log2BucketSize = 4,
bucketSize = 1<<log2BucketSize,
modBucketSize = bucketSize-1,
divBucketSize = log2BucketSize
};
ElementType& access(int index) const;
void reallocate(int reqBucketCount);
public:
Array(void);
Array(const ElementType& elem);
Array(const Array<ElementType>& array);
class Size
{
friend class Array<ElementType>;
public:
explicit Size(int s);
private:
int myElemCount;
};
explicit Array(Array::Size initsize);
Array(Array::Size initsize, const ElementType& initval);
~Array(void);
int Count(void) const;
int Contains(const ElementType& elem) const;
struct BoundsError
{
BoundsError(int i, int m);
int index;
int max;
};
ElementType& operator[] (int index);
ElementType operator[] (int index) const;
Array& operator= (const ElementType& elem);
Array& operator= (const Array& array);
Array& Append(const ElementType& elem);
Array& Append(const Array& array) ;
Array& RemoveLast(int n = 1);
Array& Reset(void);
friend bool operator==(const Array& a1, const Array& a2);
private:
int myBucketCount;
int myNextFree;
ElementType** myElement;
};
Array class
The following code shows some uses of the Array class template.
struct Mark { int score; string name;
Mark(void) : score(-1) {} Mark(int s, string n) : score(s), name(n) {}
void Print(const Mark& m) { cout << name << ": " << score << endl; } };
Array<Mark> marks;
ifstream markFile("marks.txt");
int nextName, nextMark; while (markFile >> nextName >> nextMark) { marks.Append( Mark(nextMark,nextName) ); }
cout << "Read " << marks.Count() << " marks" << endl;
int nextIndex; char nextCmd; while (cin >> nextCmd) { switch (nextCmd) { case 'p': cin >> nextIndex; marks[nextIndex].Print(); break;
case 'd': marks.RemoveLast(); break; } }
ElementType
Like most templated class, Array imposes some constraints on the types
which are used to instantiate its template parameter ElementType. These
constraints are:
ElementType must have a no-argument constructor
(that is, ElementType::ElementType(void)).
ElementTypes must be possible.
ElementTypes for equality.
ElementType, since each element in such a vector¤ is initialized by calling
the appropriate no-argument constructor.
The second constraint is required to enable the value of elements of the
Array to be changed. This may occur as a result of constructor calls,
assignments to the Array, or append operations
(see "Appending elements to an Array").
The third constraint is required in order to implement the
Array::Contains member function (see "Finding elements in an Array") and equality operator (see "Comparing Arrays for equality").
Note that all inbuilt types (including pointer types) satisfy these constraints.
Array
At the start of the Array class four private integer constants
are declared within an anonymous enum (this is the usual method of
declaring integral constants in a class):
enum
{
log2BucketSize = 4,
bucketSize = 1<<log2BucketSize,
modBucketSize = bucketSize-1,
divBucketSize = log2BucketSize
};
The constant log2BucketSize specifies the log (base
2) of the number of elements per bucket. This is rather an awkward
means of specifying the size of each bucket, but has the distinct
advantage that it allows us to automate the computation of all other
constants, as well as guaranteeing that the size of each bucket an
integral multiple of two, which is important for efficient array
access (see "Accessing elements" below). The value of 4
means that each bucket will contain 2 to the 4th (that is, 16)
elements.
The constant bucketSize specifies the number of
elements per bucket and is automatically calculated using a bit-shift
to compute 2 to the power of log2BucketSize (again, 16 in this case).
The constants modBucketSize and
divBucketSize are used to accelerate the modulo and
division operations required to compute a bucket number and element
offset for a specified index (again see "Accessing elements" below).
See also: Exercise 2
The private member function Array::access(int index) is a utility function¤
used internally by the other members of Array to simplify access to
specific elements in the array. Its function is to map an integer
index to an element reference, and it is implemented as follows:
template <class ElementType>
inline ElementType&
Array<ElementType>::access(int index) const
{
return myElement[index>>divBucketSize][index&modBucketSize];
}
When invoked, access first computes an offset into
the vector¤ of buckets pointed to by myElement. This
offset is simply the requested index, integrally divided by the number
of elements per bucket. For example, if there are 8 elements per
bucket, the element with index 7 must be stored in bucket zero (since
7/8 -> 0), whilst the element with index 27 must be stored in bucket
3 (since 27/8 -> 3).
Of course, since the access member function will be invoked every time
an element is accessed, it would be intolerable to have to perform an
expensive division each time (note that it is inline'd for the
same reason). Fortunately, since buckets are guaranteed to be of sizes
which are some multiple of two, the division can be performed very
cheaply using a right-shift operation.
Once the correct bucket is determined, it is necessary to determine where in that bucket the requested element is located. This is achieved by taking the remainder when the original index is divided by the number of elements in each bucket. Again, this would normally be impractically expensive, except that the guaranteed power-of-two bucket size means that the modulo operation can be performed very cheaply by masking out the higher bits of the index.
For example, if there are 8 elements per bucket, the element with index 7 (somewhere in bucket 0) must be stored at offset 7 (since 7 is 111 (base 2) and the bottom three bits - 111 - have the value 7), whilst the element with index 27 (somewhere in bucket 3) must be stored at offset 3 (since 27 is 11011 (base 2) and the bottom three bits - 011 - have the value 3).
Once both the bucket number and offset have been computed, the function simply indexes into the bucket vector¤ and thence into the appropriate bucket and retrieves a reference to the requested element.
These calculations may seem mysterious at first. Another way of looking at them is to consider the vector¤ of buckets as a 2D table. The first index of this table is the bucket number in which the element is stored, the second is the offset of the element within that bucket.
The trick is that, by arranging for the table to have a width of 2 raised to some integer (W), we can encode both the bucket number and offset of an element in a single integer - the offset in the bottom W bits, and the bucket number in the remaining (top) bits.
The access member function then simply separates these values by
appropriate bit-shifting and bit-masking, and uses them to look-up
the table. The following diagram summarizes this way of thinking about
indices:
![[Diagram showing the bits of a binary representation of an index
being partitioned into separate (concatenated) binary representations
of a bucket number and an offset]](IndexEncoding.gif)
Array
The second private utility function¤ in the class is used to reallocate internal
memory on demand. The Array::reallocate(int) function must be invoked by any public
member function which is performing any operation which might cause extra
elements to be added to the array (for example: the constructors, assignment
operators, and Array::Append(...) member functions).
The reallocate member function is implemented as follows:
template <class ElementType>
void
Array<ElementType>::reallocate(int reqBucketCount)
{
if (reqBucketCount>0 && reqBucketCount>myBucketCount)
{
ElementType** newelement = new ElementType* [reqBucketCount];
int i;
for (i=0;i<myBucketCount;i++)
{
newelement[i] = myElement[i];
}
for (;i<reqBucketCount;i++)
{
newelement[i] = new ElementType [bucketSize];
}
delete [] myElement;
myElement = newelement;
myBucketCount = reqBucketCount;
}
}
The function first determines how many elements the Array object
will henceforth be required to store. This information is passed in via
the reqBucketCount parameter which specifies how many buckets will
be required (it is up to the member function which calls reallocate() to
work this out beforehand).
If the required bucket count is non-trivial and greater than the number of buckets currently available, then more space will have to be allocated.
if (reqBucketCount>0 && reqBucketCount>myBucketCount)
{
If more buckets are required the reallocation process proceeds as follows. First, a new vector¤ of the appropriate number of buckets will be allocated, and pointers to the existing buckets copied into it:
ElementType** newelement = new ElementType* [reqBucketCount];
int i;
for (i=0;i<myBucketCount;i++)
{
newelement[i] = myElement[i];
}
Then new buckets will be allocated for the remaining slots in the bucket vector¤:
for (;i<reqBucketCount;i++)
{
newelement[i] = new ElementType [bucketSize];
}
Finally, the old vector¤ of bucket pointers is deleted and replaced with the new vector¤, whilst the internal bucket count is updated appropriately:
delete [] myElement;
myElement = newelement;
myBucketCount = reqBucketCount;
After reallocate() has executed, the logical state of the Array
object (that is, how it appears to the rest of the program) is
unchanged. However, the object can now guarantee to be able to store
as many elements as space was requested for. Note however that
reallocate() can potentially fail if no free store memory is
available (in which case it would throw the standard exception
std::bad_alloc). Since the Array member functions don't
attempt to catch this exception, it must be handled by the code using
the relevant Array object.
Note too that reallocate() is structured so that an allocation
failure does not corrupt the logical state of the Array object in
which it occurred. That is, the Array object is still usable after
the memory exception is handled (although it may have leaked some memory if
the exception was thrown after the first call to new).
Array(void) constructor
The first public member of the Array template class is its
no-argument constructor. The constructor is implemented as:
template <class ElementType>
Array<ElementType>::Array(void)
: myBucketCount (0)
, myNextFree (0)
, myElement (0)
{}
The constructor initializes (to zero) the three private members of the the class and does nothing else. The purposes of the private members are:
myNextFree
myElement
myBucketCount
myElement.
void constructor
indicates that (1) no memory has yet been allocated within the array,
and (2) the next element will be inserted at index zero.
Array single-element constructor and copy constructor
The Array class implements the two other obvious constructors: a
constructor that builds a (one element) array from a single
ElementType object:
template <class ElementType>
Array<ElementType>::Array(const ElementType & elem)
: myBucketCount(0)
, myNextFree(1)
, myElement(0)
{
reallocate(1);
access(0) = elem;
}
and a copy constructor:
template <class ElementType>
Array<ElementType>::Array(const Array<ElementType> & array)
: myBucketCount(0)
, myNextFree(array.myNextFree)
, myElement(0)
{
reallocate(array.myNextFree+modBucketSize >> divBucketSize);
for (int i=0; i<array.myNextFree; i++)
{
access(i) = array.access(i);
}
}
The operation of both is straightforward. Each constructor simple
calls reallocate() to ensure sufficient memory is available, and
then copies the values passed in as arguments to the constructor into
the appropriate elements of the new Array.
Note that the copy constructor allocates only as much space in the new
Array object as is required to hold the elements actually stored
in the Array object (array) being copied.
If there were no mechanisms for "pre-allocating" space or removing
elements from a list (that is, if the Array(Array::Size...)
constructors and member functions Array::Reset() and
Array::RemoveLast(...) did not exist) it would suffice to use the value
of array.myBucketCount as the number of buckets required in the
copy. That is:
reallocate(array.myBucketCount);
instead of:
reallocate(array.myNextFree+modBucketSize >> divBucketSize);
However, because an Array object may have (pre-)allocated more
space than it is currently using, in some instances using
array.myBucketCount would cause an unnecessarily large amount of
space to be allocated. To prevent this, the copy constructor computes the
minimal number of buckets required.
The expression (array.myNextFree+modBucketSize >> divBucketSize)
representing this minimal bucket count is highly efficient but perhaps
equally highly obscure. The expression derives from the following
line of reasoning:
B = array.myNextFree/bucketSize + 1
= (array.myNextFree+bucketSize)/bucketSize
= (array.myNextFree+bucketSize) >> divBucketSize
B = array.myNextFree / bucketSize
= array.myNextFree >> divBucketSize
array.myNextFree % bucketSize
equals zero. But because bucketSize is an
integral power of two (specifically, 2 raised to
log2BucketSize), array.myNextFree % bucketSize
is equivalent to the bottom
log2BucketSize bits of array.myNextFree.
Hence the number of elements will be an exact
multiple of the number of buckets when the bottom
log2BucketSize bits of array.myNextFree
are all zero.
bucketSize
is to add 1 to the log2BucketSize'th bit of
array.myNextFree (and then propagate any carry
leftwards). In order to cater for both cases (a) and
(b), we would like to find a means of achieving this
goal, but only when log2BucketSize bits of
array.myNextFree are not all zero.
log2BucketSize bits of
array.myNextFree are not all zero, then adding
bucketSize-1 to array.myNextFree will still
increment the log2BucketSize'th bit. This is
because the bottom bits must have a value of at
least 1, so adding bucketSize-1 to them must
result in a value of at least bucketSize (as
required in (c)).
log2BucketSize bits of
array.myNextFree are all zero, then adding
bucketSize-1 to array.myNextFree will not
increment the log2BucketSize'th bit (recall that bit
indices start to at "zero'th" bit),
because the bottom bits must have a value of
zero, so adding bucketSize-1 to them must
result in a value of bucketSize-1 (which will be
insufficient to increment the log2BucketSize'th bit).
(array.myNextFree+bucketSize-1) >> divBucketSize
(array.myNextFree) >> divBucketSize
array.myNextFree is a multiple of bucketSize,
and:
(array.myNextFree+bucketSize) >> divBucketSize
modBucketSize is defined as
bucketSize-1, and the precedence of
operator+ is higher than that of operator>>,
the required expression can be simplified to:
array.myNextFree+modBucketSize >> divBucketSize
See also: Exercise 3
Array::Size nested class and associated Array constructors
The next component of the Array template class is a nested helper
class called Array::Size, which is used to pass information to
Array's two remaining constructors, informing them how much space
to initially allocate. This can be useful when we know in advance how
many elements are likely to be added to an Array object over the
course of its existence, since the required memory can be allocated
once (at construction) rather than in many increments during
successive insertions.
The obvious question is: Why bother with a special helper class instead of just providing constructors that take an integer, indicating the number of elements to reserve space for? The answer becomes clear when we consider the signature of such a constructor:
template <class ElementType>
explicit Array<ElementType>::Array(int initsize);
Everything works fine until we attempt to create an
Array<int> object. In that one case, the above constructor
becomes equivalent to the specialization¤:
template <>
explicit Array<int>::Array(int initsize);
But at the same time, the "single element constructor":
template <class ElementType>
Array<ElementType>::Array(const ElementType& elem);
would become equivalent to:
template <>
Array<int>::Array(const int& elem);
making calls to the two constructors ambiguous in most contexts. For
example, should the declaration: Array<int> array(10); cause
array to be initialized to store a single value (ie:
10), or to have capacity for ten uninitialized
values? By using the helper class instead, we can sidestep this issue.
The helper class also encourages better internal documentation of code, since
constructing an Array with space for 10 elements now looks like this:
Array<int> array (Array<int>:Size(10));
The nested class is implemented thus:
template <class ElementType>
class Array<ElementType>::Size
{
friend class Array<ElementType>;
public:
explicit Size(int s) : myElemCount(s) {}
private:
int myElemCount;
};
The constructor simply stores the requested element count in the
private member myElemCount. Note that the constructor
is marked explicit, since it is only ever intended to
be used as in the example above.
Note too that the surrounding Array class template is declared a
friend of the Size class. This is necessary to permit the
Array constructors to access the private member myElemCount,
because non-public members of nested classes are not automatically
accessible to their surrounding classes (TDCS, § Z.Z).
The "pre-allocating" constructors are implemented as follows:
template <class ElementType>
Array<ElementType>::Array(Array<ElementType>::Size initsize)
: myBucketCount(0)
, myNextFree(0)
, myElement(0)
{
reallocate(initsize.myElemCount+modBucketSize >> divBucketSize);
}
template <class ElementType>
Array<ElementType>::Array(Array<ElementType>::Size initsize,
const ElementType& initval)
: myBucketCount(0)
, myNextFree(initsize.myElemCount)
, myElement(0)
{
reallocate(initsize.myElemCount+modBucketSize >> divBucketSize);
for (int i=0;i<myNextFree;i++)
{
access(i) = initval;
}
}
The first Array(Array::Size...) constructor behaves much like the
Array(void) constructor, except that, after initializing the three
private members, it goes on to calculate the number of buckets
required (using a variant of the "add-then-shift" expression used in
the copy constructor);
This number of buckets is then passed to the reallocate() member
function, thereby allocating the requisite number of elements. Note
that the initialization of the three members in the constructor list
is essential, since reallocate() relies on this information to do
its job correctly.
The second Array(ArraySize...) constructor behaves just like the
first, except that, as well as allocating the required space, it then
initializes each requested element with the initial value specified by
initval. Note too that the member myNextFree is initialized to
the correct value.
See also: Exercise 4
~Array destructor
The Array destructor is non-trivial. In order to prevent memory leaks¤, it is
required to delete all the buckets its object has allocated (that is,
those pointed to by the pointers in each myElement[i] for all
values of i less than myBucketCount). Once the buckets have been
relinquished, the bucket vector¤ itself is deleted:
template <class ElementType>
Array<ElementType>::~Array(void)
{
for (int i=0; i<myBucketCount; i++)
{
delete [] myElement[i];
}
delete [] myElement;
}
See also: Exercise 5
Array
The Array class provides two "informative" members: Count() and
Contains(...). The Count() member function simply returns the
actual number of elements stored in the array, and is implemented thus:
template <class ElementType>
int
Array<ElementType>::Count(void) const
{
return myNextFree;
}
The Contains(...) function performs a linear search through the elements of the
array, looking for the first element which compares equal to its argument.
If a suitable element is found, the function returns an integer one greater
than the element's index. If no such element is found, zero is returned:
template <class ElementType>
int
Array<ElementType>::Contains(const ElementType& elem) const
{
for (int i=0;i<myNextFree;i++)
{
if (elem == access(i)) { return i+1; }
}
return 0;
}
Returning one more than the matching element's index is useful, because it enables the zero return value to be used to signify failure. This means that code like this:
if (array.Contains(searchValue))
{
doSomething();
}
works as expected. If we used some other (presumably negative) sentinel value, it would not.
The element which is found by the call to Contains(...) can be
accessed as follows:
if (int pos = array.Contains(searchValue))
{
doSomethingWith( array[pos-1] );
}
See also: Exercise 6
Array elements
Public access to individual elements stored in an Array is
provided by two operator[] member functions. These member
functions each perform two functions: (1) they check to see if the
requested element exists in the array and, if so, (2) they call the
private member access to provide a reference (or copy) to the
element.
Each member function throws an exception if the requested element is
not present in the array. To accomplish this without namespace
pollution, Array provides a publicly accessible nested struct
(Array::BoundsError) which can be used to transmit error
information through the exception (specifically: the index requested
and the upper bound that it transgressed):
template <class ElementType>
struct Array<ElementType>::BoundsError
{
BoundsError(int i, int m) : index(i) , max(m) {}
int index;
int max;
};
Run-time access errors can then be caught in the usual manner:
Array<string> names;
while (cin >> nextIndex)
{
try
{
cout << names[nextIndex] << endl;
}
catch (Array<string>::BoundsError b)
{
cout << b.index << " out of range 0.." << b.max << endl;
}
}
The actual access functions provide a means of retrieving or
modifying any element in the array. Note that both const and
non-const versions of Array::operator[] are provided. The
const version returns its value by copy to ensure that the
elements of const Array cannot be (improperly) changed by
subsequent assignment. Note however that the actual bodies of the
two versions are textually identical:
template <class ElementType>
ElementType&
Array<ElementType>::operator[] (int i)
{
if (i>=0 && i<myNextFree) { return access(i); }
throw BoundsError(i,myNextFree);
}
template <class ElementType>
ElementType
Array<ElementType>::operator[] (int i) const
{
if (i>=0 && i<myNextFree) { return access(i); }
throw BoundsError(i,myNextFree);
}
Array
The assignment operators of class Array replace the existing
elements of the array with values appearing on the right of the "="
(that is, values passed in to the member functions as their single
parameter).
Internally, the assignment operators for class Array closely
mirror the corresponding constructors. Whether assigning a single
element or an Array of elements, they perform three steps:
reallocate() to ensure sufficient space is made
available;
myNextFree counter.
template <class ElementType>
Array<ElementType>&
Array<ElementType>::operator= (const ElementType & elem)
{
reallocate(1);
access(0) = elem;
myNextFree = 1;
return *this;
}
template <class ElementType>
Array<ElementType>&
Array<ElementType>::operator= (const Array<ElementType>& array)
{
if (&array == this) { return *this; }
reallocate(array.myNextFree+modBucketSize >> divBucketSize);
for (int i=0; i<array.myNextFree; i++)
{
access(i) = array.access(i);
}
myNextFree = array.myNextFree;
return *this;
}
Note that, just as in the copy constructor, the second version is implemented so that it allocates only the minimum amount of space required to hold as many elements as are actually stored in the array.
Note too that the second version is optimized so as to "short circuit
on self-assignment". That is, any assignment equivalent to array = array
will have absolutely no effect on the object array.
Array
For convenience (and because Array::operator[] throws an
exception if an non-existent element is accessed), some other
mechanism is needed to allow us to explicitly add extra elements to
an existing array. The Array class provides two member functions
called Append(...) for this purpose. They may be used to append a
single element or an Array of elements to the end of an existing
Array object as follows:
Array<char> ac1, ac2;
ac1.Append('c'); // ac1 NOW ['c']
ac1.Append('a'); // ac1 NOW ['c'|'a']
ac1.Append('t'); // ac1 NOW ['c'|'a'|'t']
ac2.Append('c'); // ac2 NOW ['c']
ac2.Append('o'); // ac2 NOW ['c'|'o']
ac2.Append('n'); // ac2 NOW ['c'|'o'|'n']
ac2.Append(ac1); // ac2 NOW ['c'|'o'|'n'|'c'|'a'|'t']
The Array::Append(...) members are surprisingly similar to the
corresponding constructors and assignment operators:
template <class ElementType>
Array<ElementType>&
Array<ElementType>::Append(const ElementType& elem)
{
reallocate(myNextFree+1+modBucketSize >> divBucketSize);
access(myNextFree) = elem;
myNextFree++;
return *this;
}
template <class ElementType>
Array<ElementType>&
Array<ElementType>::Append(const Array<ElementType>& array)
{
reallocate(myNextFree+array.myNextFree+modBucketSize>>divBucketSize);
for (int i=0; i<array.myNextFree; i++)
{
access(myNextFree+i) = array.access(i);
}
myNextFree += array.myNextFree;
return *this;
}
Indeed the only difference is in the number of buckets requested when
calling reallocate(). In both cases, the number of extra elements
(1 or array.myNextFree) is added to the number of existing
element (myNextFree) to compute the total number of elements
which the Array object will store after the append. The required
number of buckets is then computed using the same approach as for the
copy constructor or array-to-array assignment operator.
See also: Exercise 7
Array
The Array class also provides two means of logically removing
elements from an array. In this context "logically" means that
although (viewed from outside the class) elements appear to be
removed from the array, no actual memory is deleted, nor are the
elements destructors called.
The first member function, Array::Reset(), logically removes the
entire collection of elements, by resetting the private myNextFree
counter to zero:
template <class ElementType>
Array<ElementType>&
Array<ElementType>::Reset(void)
{
myNextFree = 0;
return *this;
}
Array also provides a more selective mechanism, Array::RemoveLast(...),
for removing only the last n elements of the array:
template <class ElementType>
Array<ElementType>&
Array<ElementType>::RemoveLast(int n = 1)
{
if (myNextFree<=n) { myNextFree = 0; }
else if (n>=0) { myNextFree -= n; }
return *this;
}
Note that, by default, only the last element is removed. Note too that
RemoveLast is careful not to corrupt the element count if an attempt is
made to remove unreasonable numbers of elements (that is, removing a negative
number of elements, or more elements than are present).
See also: Exercise 8
Arrays for equality
In order to enable us to construct Arrays of Arrays, the
Array class must itself satisfy the constraints for its type
parameter ElementType. Hence we must provide an equality test
operator:
template <class ElementType>
bool
operator== (const Array<ElementType>& a1, const Array<ElementType>& a2)
{
if (&a1==&a2) { return true; }
if (a1.myNextFree!=a2.myNextFree) { return false; }
for (int i=0; i<a1.myNextFree; i++)
{
if (!(a1.access(i) == a2.access(i))) { return false; }
}
return true;
}
Note first that the operator is a friend of Array, rather than a member.
This ensures that implicit conversions can be applied to both operands.
Since an element-by-element comparison of two arrays is a potentially expensive operation, the equality test performs two inexpensive preliminary tests: checking for "comparison-to-self" (which guarantees equality) and for differing lengths of the arrays (which guarantees inequality).
If neither test is conclusive (that is, we are comparing two different arrays of the same length), it is necessary to step through corresponding elements of the two arrays, looking for a mismatch (which would confirm inequality). If no mismatch is found then the arrays are the same length and contain an identical sequence of values, so they must be equal.
See also: Exercise 9
Last updated: Fri Feb 18 11:16:58 2000