CS计算机代考程序代写 data structure compiler Java c++ algorithm Memory Management and Copy Control

Memory Management and Copy Control
Overview
• Types of memory
• Copy constructor, assignment operator, and destructor • Reference counting with smart pointers
References
• Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo: C++ Primer. 4th Edition. Addison-Wesley (2006)
• Bruno R. Preiss: Data Structures and Algorithms with Object-Oriented Design Patterns in C++. John Wiley & Sons, Inc. (1999)
• Andrew W. Appel with Jens Palsberg: Modern Compiler Implementation in Java. 2nd Edition, Cambridge University Press (2002).
• Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman: Compilers – Principles, Techniques, and Tools. Addison-Wesley (1988)
270
© Dr Markus Lumpe, 2021

Static Read-Write Memory
• C++ allows for two forms of global variables: • Static non-class variables,
• Static class variables.
• Static variables are mapped to the global memory. Access to them depends on the visibility specifiers.
• We can find a program’s global memory in the so- called read-write .data segment.
271
© Dr Markus Lumpe, 2021

The Keyword static
• The keyword static can be used to
mark the linkage of a variable or function internal, retain the value of a local variable between
declare a class instance variable, define a class method.


function calls,
• •
272
© Dr Markus Lumpe, 2021

Read-Write Static Variables
Static class variables must be initialized outside the class.
273
© Dr Markus Lumpe, 2021

Static Read-Only Memory
• In combination with the const specifier we can also define read-only global variables or class variables:
274
© Dr Markus Lumpe, 2021
Const variables are often stored in the program’s read-only .text segment.

Program Memory: Stack
• All value-based objects are stored in the program’s stack.
• The program stack is automatically allocated and freed.
•References to stack locations are only valid when passed to a callee. References to stack locations cannot be returned from a function.
275
© Dr Markus Lumpe, 2021

Stack Frames (C)
temporaries save registers
arguments
return address
temporaries save registers
arguments
incoming arguments stack pointer
outgoing arguments
higher addresses
previous frame
current frame next frame
276
© Dr Markus Lumpe, 2021

Program Memory: Heap
•Every program maintains a heap for dynamically allocated objects.
• Each heap object is accessed through a pointer.
• Heap objects are not automatically freed when pointer variables become inaccessible (i.e., go out of scope).
•Memory management becomes essential in C++ to reclaim memory and to prevent the occurrences of so- called memory leaks.
277
© Dr Markus Lumpe, 2021

List::~List()
Release memory associated with list node object on the heap.
278
© Dr Markus Lumpe, 2021

The Dominion Over Objects
• Alias control is one of the most difficult problems to master in object-oriented programming.
• Aliases are the default in reference-based object models used, for example, in Java and C#.
• To guarantee uniqueness of value-based objects in C++, we are required to define copy constructors.
279
© Dr Markus Lumpe, 2021

The Copy Constructor
• Whenever one defines a new type, one needs to specify implicitly or explicitly what has to happen when objects of that that type are copied, assigned, and destroyed.
• The copy constructor is a special member, taking just a single parameter that is a const reference to an object of the class itself.
280
© Dr Markus Lumpe, 2021

A simple String class
281
© Dr Markus Lumpe, 2021

SimpleString
282
© Dr Markus Lumpe, 2021

SimpleString: Constructor & Destructor
283
© Dr Markus Lumpe, 2021

SimpleString: The Operators
284
© Dr Markus Lumpe, 2021

Implicit Copy Constructor
285
© Dr Markus Lumpe, 2021
On Windows you may not see anything.

What Has Happened?
Shallow copy:
s2.fCharacters == s1.fCharacters
286
© Dr Markus Lumpe, 2021
Double free:
delete s2.fCharacters, which was called in s2 + ‘B’.

We need an explicit copy constructor!
287
© Dr Markus Lumpe, 2021

The Explicit Copy Constructor
• When a copy constructor is called, then all instance variables are uninitialized in the beginning.
288
© Dr Markus Lumpe, 2021

Explicit Copy Constructor in Use
289
© Dr Markus Lumpe, 2021

What Has Happened?
Deep copy:
s2.fCharacters != s1.fCharacters
290
© Dr Markus Lumpe, 2021

That’s it. No more problems, or?
291
© Dr Markus Lumpe, 2021

A Simple Assignment
292
© Dr Markus Lumpe, 2021

What Has Happened?
Shallow copy:
s2.fCharacters == s1.fCharacters
293
© Dr Markus Lumpe, 2021
Double free:
delete s2.fCharacters, which is the same as s1.fCharacters.

Rule Of Thumb
• Copy control in C++ requires three elements: • a copy constructor
• an assignment operator • a destructor
• Whenever one defines a copy constructor, one must also define an assignment operator and a destructor.
• C++ also supports move constructor and move assignment operator. They work similarly, but steal the memory for its r-value source. Moreover, while the compiler still synthesizes missing l-value copy constructors and assignment operators, their r-value counterparts are not synthesized if the programmer does specify either but not both.
294
© Dr Markus Lumpe, 2021

We need an explicit assignment operator!
295
© Dr Markus Lumpe, 2021

The Explicit Assignment Operator
protection against accidental suicide
• When the assignment operator is invoked, then all instance variables are initialized in the beginning. We
need to release the memory first!
296
© Dr Markus Lumpe, 2021

Explicit Assignment Operator in Use
297
© Dr Markus Lumpe, 2021

What Has Happened?
Deep copy:
s2.fCharacters != s1.fCharacters
298
© Dr Markus Lumpe, 2021

Cloning: Alias Control for References
299
© Dr Markus Lumpe, 2021

Copying Pointers
300
© Dr Markus Lumpe, 2021

What Has Happened?
Shallow copy:
ps2. == ps1
301
© Dr Markus Lumpe, 2021
Double free:
delete ps2, which is the same as ps1.

Solution: A clone() Method
Destructor must be virtual!
• It is best to define the destructor of a class virtual
always in order to avoid problems later. © Dr Markus Lumpe, 2021 302

The Use of clone()
303
© Dr Markus Lumpe, 2021

Problems With Cloning
• The member function clone() must be defined virtual to allow for proper redefinition in subtypes.
• Whenever a class contains a virtual function, then its destructor is required to be defined virtual as well.
• The member function clone() can only return one type. When a subtype redefines clone(), only the super type can be returned.
304
© Dr Markus Lumpe, 2021

Non-virtual Cloning Does Not Work!
• One could define clone() non-virtual and use overloading. But this does not work as method selection starts at the static type of the pointer.
SimpleString* pToString = new SubtypeOfSimpleString(); SimpleString* c1 = pToString->clone(); // SimpleString::clone()
305
© Dr Markus Lumpe, 2021

Reference-based Semantics: When Do We Destroy Objects?
306
© Dr Markus Lumpe, 2021

Reference Counting
• A simple technique to record the number of active uses of an object is reference counting.
• Each time a heap-based object is assigned to a variable the object’s reference count is incremented and the reference count of what the variable previously pointed to is decremented.
• Some compilers emit the necessary code, but in case of C++ reference counting must be defined (semi-)manually.
307
© Dr Markus Lumpe, 2021

Smart Pointers: Handle
308
© Dr Markus Lumpe, 2021

The Use of Handle
• The template class Handle provides a pointer-like behavior: • Copying a Handle will create a shared alias of the underlying
object.
• To create a Handle, the user will be expected to pass a fresh,
dynamically allocated object of the type managed by the Handle.
• The Handle will own the underlying object. In particular, the Handle assumes responsibility for deleting the owned object once there are no longer any Handles attached to it.
309
© Dr Markus Lumpe, 2021

Handle: Constructor & Destructor
310
© Dr Markus Lumpe, 2021
Decrement reference count
Create a shared counter

Handle: addRef & releaseRef
Increment reference count
Decrement reference count and delete object if it is no longer referenced anywhere.
311
© Dr Markus Lumpe, 2021

Handle: Copy Control
312
© Dr Markus Lumpe, 2021

Handle: Pointer Behavior
313
© Dr Markus Lumpe, 2021

Using Handle
314
© Dr Markus Lumpe, 2021

Reference Counting Limits
Reference Count == 1 Reference Count == 1
• Reference counting fails on circular data structures like double-linked lists.
• Circular data structures require extra effort to reclaim allocated memory. Know solution: Mark-and-Sweep
315
© Dr Markus Lumpe, 2021