9 Array Data Structures9.1 Allocation and Deallocation of Arrays.9.2 The Flexible Array Data Structure9.2.1 Implementation in C++9.2.2 Implementation in C9.3 Ragged Arrays9.3.1 Dynamic Ragged Arrays9.4 The StringStore Data Structure9.4.1 The StringStore and Pool Classes.9.5 The StringArray9.6 Hashing9.6.1 The Hash Table Array9.6.2 Hash Functions.9.7 Example: Combining Several Data Structures9.7.1 The Main Program9.7.2 The Dictionary Class9.7.3 The FlexArray and StringStore Classes9.7.4 A Better WayChapter 9: Array Data StructuresA fundamental principle of good construction and good programming:Function dictates form. First, get the right blueprints.This chapter covers some major array-based data structures that have been or will be used in the sampleprograms and/or assignments in this course. These are:1. Arrays of objects and arrays of pointers.2. The resizeable array.3. The stringstore, an efficient way to store dynamically allocated strings.4. The hashtable.At the end of the chapter, these data structures are combined in a hashing program that uses an array ofpointers to resizeable arrays of string pointers.General Guidelines. Common to all data structures in C++ are some fundamental rules and guidelinesabout allocation and deallocation. Here are some guidelines, briefly stated: The method of deallocationshould imita te the method of creation.• If you allocate memory with new (and no []), you should free memory with delete.• If you allocate memory with new in a loop, you should free memory with delete in a loop.• If you allocate memory with new and [], you should free memory with delete [].Basic Rules. The guidelines are derived from more fundamental rules about how C++ memory managementworks:• If you allocate memory with a declaration, is is allocated on the run-time stack and is freed automaticallywhen control leaves the block that contains the declaration.• Dynamic memory is allocated using new and freed using delete. It is allocated in a memory segmentcalled “the heap”. If it is not freed, it continues to exist in the heap until program termination.• If the base type of an array is a class type, you must use delete[] to free it. This automatically calls thebase-type destructor function for each element of the array, to free the dynamic extensions attached to it.• As a general habit, use delete [] to free arrays, even when the [] are not needed. Some programming toolsand IDE’s become confused when you omit the []. Note, however, that if the base type of an array is apointer type or a non-class type, it does not matter whether you use delete or delete[] because there areno destructors to run. Dynamic memory attached to the elements of an array of pointers must be freedby explicit calls on delete.• In one common data structure, the flexible array, an array “grows” by reallocation, as needed. Aftergrowth, the array contents are copied from the old array to the new, longer array. In this case, you mustfree the old array but you must not free anything more than that, so delete must be used without thebrackets.Which should I use? A fundamental dat modeling decision is whether to create the program’s objects usingdeclarations (stack allocation) or using pointers and dynamic (heap) allocation. Even in a simple data structure,such as an array of structures, four basic combinations of dynamic and stack allocation are possible, and all arecommonly used. We look at these next.9394 CHAPTER 9. ARRAY DATA STRUCTURES9.1 Allocation and Deallocation of Arrays.In this section, we will be using arrays of a representative class type named Item, which has three data members,as shown below.part_name costquantclass Item {char part_name[20];int quant;float cost;public:Item();~Item();};Four array data structures are presented, all of which implement some form of two-dimensional structure.However, they have different storage requirements and dynamic possibilities. It is important for you to under-stand how they differ theoretically and practically, how to create and use each one, and when each one mightbe preferred.A diagram is given of the storage allocated for each data structure. Core portions of these objects areallocated on the run-time stack and are colored gray. Extensions are allocated in the heap and are coloredwhite. To the right of each diagram is a code fragment that shows how to use new and delete to create anddeallocate the structure.The first data structure given is a simple array of Items whose size is fixed at compile time. Each succeedingexample adds one level of dynamic allocation to the data structure, until the last is fully dynamic. For thesake of comparison, these four data structures are implemented as uniformly as possible. All are five slots longand have offboard end pointers to assist in sequential array processing. (Note: inventory+5 is the same as&inventory[5].)1. A declared array. This data structure is used if the length of the array is known at the time controlenters the block containing the declarations. All storage is allocated by the array declaration, so no “new”is necessary. For an array of class objects, a default constructor must be provided and will be used toinitialize the array.No “delete” is necessary and using “delete” or “delete[]” is a fatal error because this storage will beautomatically deallocated at the end of the function that contains the declarations and storage must notbe deallocated twice.inventory part_name costquant[4][1][2][3][0]endscan?Item inventory[5]; // Allocate array.Item* end = &inventory[5]; // Connect end pointer.Item* scan; // Processing pointer.2. A single dynamic array of class objects. This data structure is used if the length of the array isnot known at compile time but is known at run time, before any data is stored in the array. It could becombined with automatic reallocation to store data sets that might grow larger than the initially allocatedsize. However, this requires that all data in the array be copied into the reallocated memory area, apotentially large cost.The core portion of this object is created by declaring two Item pointers. The extension is created by acall on “new”, often in the constructor for some class that contains the array. A default Item constructormust be present and will be used to initialize the array. Dynamic arrays of non-class base types cannotbe initialized.Since “new” was used with [] to create this array, “delete[]” must be used to