Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
Program 
gives the definition of the
default constructor for the OpenScatterTable::Entry class.
It shall always be the case that an unoccupied entry will have
its object pointer set to zero
and the default state of all entries is initially empty.
The default constructor initializes the two
corresponding member variables accordingly.
Program: OpenScatterTable Class Constructor and Destructor and OpenScatterTable::Entry Class Constructor Definitions
The OpenScatterTable constructor takes a single argument of type unsigned int which specifies the size of scatter table desired. The constructor initializes the HashTable base class and the array member variable as required. Initializing the array variable requires setting all of the entries to the empty state. Consequently, the running time for the OpenScatterTable constructor is O(M) where M is the size of the scatter table.
The OpenScatterTable destructor calls the Purge
member function.
The Purge function must delete any contained objects
if the scatter table is the owner of those objects.
The Purge function traverses the array looking for occupied
entries and deletes objects as the are found.
If there are n contained objects
and the length of the array is M,
then the running time of the Purge function is 
.
Since 
, if we assume that 
the running time becomes O(M)
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.