Dynamic Arrays动态数组

1、Classes / holds maximum of 10 int and there is possible wasted space nUsing dynamic memory allocation, we can size the list during execution of the program IntPtr a = new int10; 4 Operator new Syntax new DataType new DataType IntExpression If memory is available, in an area called the heap (or free

2、store) new allocates the requested object or array, and returns a pointer to (address of ) the memory allocated. Otherwise, program terminates with error message. The dynamically allocated object exists until the delete operator destroys it. 5 Dynamic Array Allocation char *ptr; / ptr is a pointer v

3、ariable that / can hold the address of a char ptr = new char 5 ; / dynamically, during run time, allocates / memory for a 5 character array / and stores the base address into ptr ptr 6000 6000 6 Operator delete Syntax delete Pointer delete Pointer If the value of the pointer is 0 there is no effect.

4、 Otherwise, the object or array currently pointed to by Pointer is deallocated, and the value of Pointer is undefined. The memory is returned to the free store. Square brackets are used with delete to deallocate a dynamically allocated array. 7 A Simple Dynamic List Type nWhat we want An integer lis

5、t data type DynArray that allows run-time specification of size. Also prevents indexes from going out of bounds and aggregate array copying and initialization nFeatures and abilities True object Can be passed by value and reference Can be assigned and copied Inspect and mutate individual elements In

6、spect list size Print and read a list 8 Sample DynArray Usage DynArray beta(5);/create array of 5 elements beta.Store (75, 2);/ store value 75 at location 2 DynArray gamma(4,1);/ create array of 4 elements gamma.Store (-8, 2);/ store value -8 at location 2 cout gamma.ValueAt(2);/ print value at loca

7、tion 2 for (int i = 0, i gamma.Size( ); i+) beta.Store(gamma.ValueAt(i), i); cout beta = 1 / Copy constructor. / POST: this DynArray is a deep copy of otherArr DynArray( ); / Destructor. / POST: Memory for dynamic array deallocated. int Size( ) const; / Inspector for size of list / POST: Number of e

8、lements of list is returned. int ValueAt (/*in*/ int i ) const; / PRE: i is assigned. / POST: IF 0 = i size of this array THEN / FCTVAL = value of array element at index i / ELSE error message. void Store (/*in*/ int val, /*in*/ int i ) / PRE: val and i are assigned / POST: IF 0 = i size of this arr

9、ay THEN val is / stored in array element i ELSE error message. 11 DynArray / Assignment Operator. / POST: IF enough memory THEN current values of array are /deallocated. new array created (as deep copy) with size /and contents same as otherArr ELSE error message. private: int *arr ;/ pointer to elem

10、ents int size ;/ size of list ; / overload input and output operators ostream 12 class DynArray 80 40 90 0 0 Private data: size 5 arr 6000 Free store 6000 DynArray Store ValueAt DynArray DynArray DynArray = Size 13 DynArray beta(5); /constructor 0 0 0 0 0 Private data: size 5 arr 2000 Free store 200

11、0 DynArray Store ValueAt DynArray DynArray beta DynArray = Size 14 DynArray:DynArray(/*in*/ int arrSize, /*in*/ int val) int i; if ( arrSize 1 ) cerr “DynArray constructor - invalid size: “ arrSize endl; exit(1); arr = new intarrSize ; / allocate memory size = arrSize; for (i = 0; i size; i+) arri =

12、 val; Default Constructor 15 beta.Store (75, 2); 0 0 75 0 0 Private data: size 5 arr 2000 Free store 2000 DynArray Store ValueAt DynArray DynArray beta DynArray DynArray = Size 16 int DynArray:Size ( ) return size; void DynArray:Store ( /* in */ int val, /* in */ int i ) if ( i = size ) cerr “Store

13、- invalid index : “ i endl; exit(1) ; arri = val ; Size /constructor DynArray Store ValueAt DynArray DynArray = DynArray ValueAt DynArray DynArray = DynArray Size DynArray Store Size 18 1 1 -8 1 Private: size 4 arr 3000 3000Private: size 5 arr 2000 2000 0 0 75 0 0 gamma beta gamma.Store(-8,2); DynAr

14、ray Store ValueAt DynArray DynArray = DynArray ValueAt DynArray DynArray = DynArray Size DynArray Store Size 19 1 1 -8 1 Private: size 4 arr 3000 3000Private: size 5 arr 2000 2000 0 0 75 0 0 gamma beta cout gamma.ValueAt (2); / -8 DynArray Store ValueAt DynArray DynArray = DynArray ValueAt DynArray

15、DynArray = DynArray Size DynArray Store Size 20 int DynArray:ValueAt ( /* in */ int i ) const if ( i = size ) cerr “ValueAt - invalid index : “ i endl; exit(1) ; return arri; ValueAt 21 1 1 -8 1 Private: size 4 arr 3000 3000Private: size 5 arr 2000 2000 1 1 -8 1 0 gamma beta for (int i=0; i gamma.Si

16、ze( ); i+) beta.Store (gamma.ValueAt(i), i); DynArray Store ValueAt DynArray DynArray = DynArray ValueAt DynArray DynArray = DynArray Size DynArray Store Size 22 Gang of Three Rule If a class has a data member that points to dynamic memory then that class needs a library-defined Destructor An anti-c

17、onstructor that typically uses delete on the data members that point to dynamic memory Copy constructor Constructor that builds an object out of an object of the same type Member assignment operator Resets an object using another object of the same type as a basis 23 CONSTRUCTOR COPY CONSTRUCTOR DES

18、TRUCTOR ASSIGNMENT OP (=) Classes with Data Member Pointers Need 24 Why is a destructor needed? When a DynArray class variable goes out of scope, the memory space for data members size and pointer arr is deallocated. But the dynamic array that arr points to is not automatically deallocated. If there

19、 is nothing planned, then we would have a memory leak A class destructor is used to deallocate the dynamic memory pointed to by the data member to prevent the memory leak. 25 Destructor Rules nSame name as class, preceded by tilde () ncannot return anything, has no arguments nMust be public nA class

20、 object going out of scope automatically has its destructor invoked 26 DynArray:DynArray( ) delete arr ; size = 0; class DynArray Destructor 27 Making Copies of Objects There are three ways to make a copy of an object: nexplicitly upon declaration Rational p(1,2), r(p); npass by value argument void

21、add (Rational r); nreturn object from function Rational a_func( ) return Rational(3,4); 28 Default Copy Constructor nSuppose we use the default copy constructor DynArray A(3, 1); DynArray B(A); nAnd then A1 = 2; nThen B1 is changed! Not what a client would expect nImplication Must use tailored copy

22、constructor 29 What happens . . . When a function is called that uses pass by value for a class object of DynArray type? 0 0 75 0 0 Private: size 5 arr 2000 2000 DynArray Store ValueAt DynArray DynArray DynArray Size = 30 / FUNCTION CODE void SomeFunc( DynArray someArr ) / Uses pass by value . . . .

23、 Passing a Class Object by Value 31 By default, Pass-by-value makes a shallow copy DynArray beta(5); / CLIENT CODE . . . . . . SomeFunc( beta ); / function call beta someArr 0 0 75 0 0 2000DynArray . . . Private: size 5 arr 2000 DynArray . . . Private: size 5 arr 2000 shallow copy 32 Shallow Copy vs

24、. Deep Copy na shallow copy copies only the class data members, and does not make a copy of any pointed-to data na deep copy copies not only the class data members, but also makes a separate stored copy of any pointed-to data 33 Whats the difference? na shallow copy shares the pointed to dynamic dat

25、a with the original class object na deep copy makes its own copy of the pointed to dynamic data at different locations than the original class object 34 / FUNCTION CODE void SomeFunc( DynArray someArr ) / Uses pass by value someArr.Store(290, 2); . . . WHAT HAPPENS IN THE SHALLOW COPY SCENARIO? Supp

26、ose SomeFunc calls Store 35 DynArray beta(5); / CLIENT CODE . . . . . . SomeFunc( beta); beta.arr2 has changed beta someArr 0 0 290 0 0 2000DynArray . . . Private: size 5 arr 2000 DynArray . . . Private: size 5 arr 2000 shallow copy 36 beta.arr2 has changed NOTICE THAT NOT JUST FOR THE SHALLOW COPY,

27、 BUT ALSO FOR ARGUMENT beta, THE DYNAMIC DATA HAS CHANGED! beta someArr 0 0 290 0 0 2000DynArray . . . Private: size 5 arr 2000 DynArray . . . Private: size 5 arr 2000 shallow copy 37 At the end of SomeFunc nWhen SomeFunc ends, what method is called? nWhat happens to the shared data? 38 0 0 75 0 0 4

28、000DynArray . . . Private: size 5 arr 4000 beta someArr deep copy 0 0 75 0 0 2000DynArray . . . Private: size 5 arr 2000 Making a (Separate) Deep Copy 39 Initialization of Class Objects nC+ defines initialization to mean initialization in a variable declaration passing an object argument by value re

29、turning an object as the return value of a function nby default, C+ uses shallow copies for these initializations 40 As a result . . . nwhen a class has a data member pointer to dynamically allocated data, you should write what is called a copy constructor nthe copy constructor is implicitly called

30、in initialization situations and makes a deep copy of the dynamic data in a different memory location 41 More about Copy Constructors nwhen there is a copy constructor provided for a class, the copy constructor is used to make copies for initialization nyou do not always call the copy constructor ex

31、plicitly nlike other constructors, it has no return type nbecause the copy constructor properly defines pass by value for your class, it must use pass by reference in its definition 42 Copy Constructor ncopy constructor is a special member function of a class that is implicitly called in these 3 sit

32、uations: passing object parameters by value initializing an object variable in its declaration returning an object as the return value of a function 43 0 0 75 0 0 Private: size 5 arr 2000 2000Private: size 5 arr 4000 4000 0 0 75 0 0 beta someArr SomeFunc(beta); / copy-constructor / beta passed by va

33、lue DEEP COPY DynArray Store ValueAt DynArray DynArray DynArray Store ValueAt DynArray DynArray DynArray = Size DynArray = Size 44 DynArray:DynArray( const DynArray size = otherArr.Size( ) ; arr = new intsize ; / allocate memory for copy for ( i = 0; i size ; i+ ) arri = otherArr.arri ; / copies arr

34、ay Copy Constructor 45 What about the assignment operator? nthe default method used for assignment of class objects makes a shallow copy nif your class has a data member pointer to dynamic data, you should overload the assignment operator to create a deep copy of the dynamic data nassignment operato

35、r function must be a member function 46 gamma = beta; 0 0 75 0 0 Private: size 5 arr 3000 3000Private: size 5 arr 2000 2000 0 0 75 0 0 gamma beta DEEP COPY DynArray Store ValueAt DynArray DynArray DynArray Store ValueAt DynArray DynArray DynArrayDynArray = Size = Size 47 First Assignment Attempt nAl

36、gorithm Return existing dynamic memory. Acquire sufficient new dynamic memory. Copy the size and the elements of the source object to the target element. 48 Initial Implementation DynArray size = A.Size( ); arr = new int size; for (int i = 0; i size; 51 Member Assignment Operator DynArray/ delete cu

37、rrent array size = otherArr.Size( ); arr = new int size ;/ allocate new array for (int i = 0; i size ; i+) / deep copy array arri = otherArr.arri ; return *this; Why the asterisk? 52 Implementing Friend ostream for (int i = 0; i A.size; i+) sout A.arri ; sout ; return sout; 53 Proper Implementation

38、ostream for (int i = 0; i A.Size( ); i+) sout A.ValueAt(i) ; sout Implementation istream for (int i = 0; i input; A.Store(input, i); return sin; 55 Converting Store and ValueAt nInstead of using Store and ValueAt, we may want to use the operators instead cout beta.ValueAt(2);cout beta2; beta.Store(1

39、2, 4);beta4 = 12; 56 / In the Specification File (dynarray.h) class DynArray public: const int / Inspector for element of list. / PRE: i is assigned / POST: IF 0 = i size of this array THEN / FCTVAL = value of array element at index i / ELSE error message. int / Mutator for element of list. / PRE: i is assigned / POST: IF