Dynamic Memory Management II
COSC1076 Week 08
Review: Linked Lists
Copyright By PowCoder代写 加微信 powcoder
Abstract Data Types (ADTs)
An Abstract Data Type (ADT) consists of: 1. An interface
• Asetofoperationsthatcanbeperformed.
• Usuallycontainedinaheaderfile 2. The allowable behaviours
• ThewayweexpectinstancesoftheADTtorespondtooperations.
The implementation of an ADT consists of: 1. An internal representation
• Datastoredinsidetheobject’sinstancevariables/members. 2. A set of methods implementing the interface.
• Usuallycontainedinacodefile
3. A set of representation invariants, true initially and preserved by all methods
Week 08 | Dynamic Memory Management II COSC1076
Linked List ADT
To use the list of nodes, a Linked List ADT is created which:
• Internally contains a pointer to the head (first node) of the list • Defines methods to interact with the linked list
– These methods are similar to those used on the ParticleList!
Linked List
Week 08 | Dynamic Memory Management II COSC1076
Linked List
A Linked List is a data types that:
• Stores elements of the same type
• Stores the elements as a sequential “chain” • The last element of the chain is “null”
Week 08 | Dynamic Memory Management II COSC1076
Linked Lists vs Arrays/Vectors
Array/Vector
Linked List
Element Types
All elements are same type
All elements are same type
Resizeable
Requires Copy
Storage Layout
Contiguous
Non-Contiguous
Cell lookup
Constant Time Random Access
Linear Time Random Access
Week 08 | Dynamic Memory Management II COSC1076
Linked Lists vs Arrays/Vectors
Array/Vector
Linked List
Insert at Front
Linear Time Requires Copy
Constant Time
Insert at Back
Constant Time
Linear Time (if no back ptr) Constant Time (back ptr)
Delete at Front
Linear Time Requires Copy
Constant Time
Delete at Back
Constant Time
Linear Time (if no back ptr) Constant Time (back ptr)
Week 08 | Dynamic Memory Management II COSC1076
Linked Lists Continued
More operations
Today we will look at:
• delete at index
• Double Ended Linked Lists
Remember, before starting on any method, draw the picture first!
Week 08 | Dynamic Memory Management II COSC1076
Double Ended Linked Lists
Double Ended Linked List
A Double Ended Linked List is a data types that:
• Is a linked list
• Has pointers for the chain of nodes in both directions
Node Node Node
Week 08 | Dynamic Memory Management II COSC1076
Double Ended Linked List
The Double Ended Linked List ADT:
• Has a pointer to the head and tail of the linked list • Defines methods to interact with the linked list
Double Ended Linked List
Week 08 | Dynamic Memory Management II COSC1076
Linked Lists vs Double Ended Linked List
Linked List
Double Ended Linked List
Element Types
All elements are same type
All elements are same type
Resizeable
Storage Layout
Non-Contiguous
Non-Contiguous
Cell lookup
Linear Time Random Access
Linear Time Random Access
Week 08 | Dynamic Memory Management II COSC1076
Linked Lists vs Double Ended Linked List
Linked List
Double Ended Linked List
Insert at Front
Constant Time
Constant Time
Insert at Back
Linear Time
Constant Time
Delete at Front
Constant Time
Constant Time
Delete at Back
Linear Time
Constant Time
Week 08 | Dynamic Memory Management II COSC1076
Scope describes where a name/label/entity exists and is usable.
Names include:
• Variables
• Constants and #define’s • Functions
• Class Methods & Fields
– Scope also includes the visibility of the class methods and fields
Scoping rules are programming language dependent
• While many of the following notes apply across languages there are important differences, especially with languages such as python!
Week 08 | Dynamic Memory Management II COSC1076
Variable Scope
Variables are typically scoped by: • Code block
– If/elseif
– While/for
– Manual blocks
• Functions/methods • Global scope
Local Variable scope is controlled by the program call stack
• A local variable is mapped to the block in which a local variable is created
– This happens when the variable is pushed onto the stack
• When the block is exited, the corresponding variables go out of scope
– The variables are popped off the stack
Week 08 | Dynamic Memory Management II COSC1076
Function Scope
Function are typically scoped by:
• Namespace
• C++ Source File & Header includes
Function Parameters
• Parameter Scope is from the beginning of the function to immediately after the function return point
• Parameters may be shadowed by local function variables
Week 08 | Dynamic Memory Management II COSC1076
Class Scope
Function are typically scoped by:
• Namespace
• C++ Source File & Header includes
Classes define three scope visibilities
• Public – May be accessed from any entity with a reference to the class • Protected – May only be accessed from the class, or any sub-class
• Private – May only be accessed from the class itself, not any sub-class
By default, class scope is private
Week 08 | Dynamic Memory Management II COSC1076
A Namespace defines a scope in to encapsulate
• Functions
• Namespace “Global” variables (outside of another scope) • Constants
Classes also define a namespace, of the name as the class
Week 08 | Dynamic Memory Management II COSC1076
Pre-processor statements
Pre-processor statements, such as #define, are handled before outside the syntax-tree is parsed
• Any #define value is processed before namespaces or scope apply • Thus, #define statements are “outside” of any scope
Week 08 | Dynamic Memory Management II COSC1076
Shadowing is where labels (such as variables, functions, etc.) in an inner- scope hide an entity with the identical label in an outer-scope
• For example:
In general,
• The entity from the inner-most scope is referenced by the label
• It is possible to reference entities from a outer-scope, generally through labels that the explicitly call that scope
– Most typically through namespace and class names
Week 08 | Dynamic Memory Management II COSC1076
Self Managed Objects
Review: Object Ownership
Ownership is the concept of who (which module/object/code) has responsibility for managing the life-cycle of memory allocated on the heap
• The owner manages how an object is accessed and modified • Importantly, the owner must “clean-up” memory
Ownership over an object may be transferred
Week 08 | Dynamic Memory Management II COSC1076
Self-Managed Objects
A self-managed object is responsible for managing it’s own lifecycle.
A self-managed objects decides:
• How other objects access, read and modify its contents • When to delete itself
Generally, an self-managed object tracks all references to itself
• When there are no more references to the self-managed object, then the object cleans-up its own memory
In C++, self-managed objects are implemented by so-called smart pointers • Also known as “auto” pointers
Week 08 | Dynamic Memory Management II COSC1076
Smart Pointer
A smart pointer is a class that wraps a pointer to an object that has been allocated on the heap
• The smart pointer controls all access to the object
• The smart pointer internally tracks references to itself • The smart pointer may delete the object if:
– There are no more references to the smart pointer
– The smart pointer goes entirely out of scope
– The smart pointer is told to manage a different object
C++ Provides two forms of smart pointers • unique_ptr
• shared_ptr
• weak_ptr (not covered in this course)
Week 08 | Dynamic Memory Management II COSC1076
Unique Pointer
A unique pointer is a smart pointer where:
• There may be only ONE unique pointer to the same object • The unique pointer cannot be copied
– It can be “moved” via C++ Move Semantics (see later this lecture)
– A unique pointer can be returned from a function/method • The object is deleted when:
– The unique pointer goes out of scope
– Another object is given to the unique pointer
A unique pointer is a generic object, and is given a type
A unique pointer is created using the special make_unique function
Week 08 | Dynamic Memory Management II COSC1076
Shared Pointer
A shared pointer is a smart pointer where:
• Multiple shared pointers may refer to the same object • The shared pointer can be copied
• The object is deleted when:
– There are no shared pointers with a reference to the object
A shared pointer is a generic object, and is given a type
A unique pointer is created using the special make_shared function
Week 08 | Dynamic Memory Management II COSC1076
Using Unique & Shared Pointers
In the
Must be created with special function, not a new statement
Syntactically, they work just like “raw” pointers • Dereference with “*” or “->” syntax
Work with dynamically allocated arrays as well
• Arrays values are accessed with “[]” syntax
• Calls correct version of delete to clean-up the array memory
Week 08 | Dynamic Memory Management II COSC1076
Why not just use Smart Pointers?
Actually, the C++ language specification recommends the user of smart pointers over manually managing “raw” pointers
• The C++ implementation of smart pointers is very lightweight and efficient
• Smart pointers resolve memory management issues with exception handling
However, smart pointers have limitations:
• Shared pointers are have issues with circular references, resulting in a memory leak
– This can be programatically “resolved” through a weak pointers, which you can look up for your own exercise
• Not every programming language supports smart pointers
– Thus, in this course, understanding “raw” pointers is an important skill
Week 08 | Dynamic Memory Management II COSC1076
Move Semantics
Overhead of Copying
What happens if copies are done out of necessity rather than intention? • Look at this function:
std::vector
std::vector
for (int i = 0; i != 10000; ++i) {
Card card(i);
values.push_back(card);
return values;
• Two copies – (1) copy to insert into vector; (2) Return copy the vector
Week 08 | Dynamic Memory Management II COSC1076
Overhead of Copying
To overcome this overhead, we have “work/hack” around it • Store a vector of Card pointers
– Creating card objects on the heap
– Requires us to ensure memory is cleaned-up • Take the vector as a parameter reference
• Potentially:
– Create the vector on the heap – Wrap it in a smart pointer
– Return the smart pointer
Week 08 | Dynamic Memory Management II COSC1076
Overhead of Copying
We could even ask what happens in this simple operation
• The value of x is still copied
• In generate assignment operator:
1. Evaluate rhs 1. Copy value
2. Evaluate lhs
1. Check valid lvalue
3. Update memory of lhs with copied value of rhs
1. Implicit type conversion
Even still, there are a huge number of details being skipped over
int x = 7; int y = x;
Week 08 | Dynamic Memory Management II COSC1076
Move Semantics
Move Semantics give us a programatic method to do what we really want • Create a vector of Cards
• Return the vector
• Without the unnecessary copying
Move semantics allow us to move or transfer memory between objects/ variables
• Provide a programmatic way for transferring objects
Before we look at move semantics, need a detour through l/r-values
Week 08 | Dynamic Memory Management II COSC1076
L/R Values (High-level)
int x = 7; int y = x;
The high-level, non-technical explanation
• A l-value is something that can be “assigned into”,
– That is, can go on the left-side of an assignment statement • A r-value is a temporary (or transient) entity/value
– Cannot be assigned into
– Can only go on the right-side of an assignment statement – Exists temporarily in memory until it is ‘bound’ to a variable
In the above, x & y are l-values, while 7 is a r-value
Week 08 | Dynamic Memory Management II COSC1076
Move Semantics
int x = 7;
int y = std::move(x);
Move semantics move or transfer a r-value between l-values
• Above, the 7 can be thought of as being ‘moved into’ the memory for x • The std::move operation, moves the 7 value from x to y
In general, move semantics allow us to:
• Write functions/methods that have r-values as a parameter • Create objects by moving memory rather than copying memory
– Thereby pass objects around by “moving them”
Week 08 | Dynamic Memory Management II COSC1076
Move Semantics – Simple Example
As a simple example:
int foo(int i) {
int j = i;
• The parameter i is an l-value
• This would require i to be copied into j • j is incremented, and returned.
• The return is also copied
Week 08 | Dynamic Memory Management II COSC1076
Move Semantics – Simple Example
As a simple example:
int foo(int&& i) {
int j = i;
• The && operator means that the parameter i is now an r-value! • The value i is moved into j which gives us one less copy!
• j is incremented, and returned.
• The return is still copied
Week 08 | Dynamic Memory Management II COSC1076
Move Semantics – Making R-Values
The std::move() function makes a l-value from a r-value indicating that it may be moved (of course it may not)
int foo(int&& i) {
int j = i;
int x = 7;
foo(std::move(x));
• Located in the
Week 08 | Dynamic Memory Management II COSC1076
WARNING – Move Semantic Effects
Once a value has been moved the original variable/ojbect may not be used
int foo(int&& i) {
int j = i;
int x = 7;
foo(std::move(x));
• Since x has been moved, we can’t call on it’s value anymore
• The C++11 specification says a moved-from object exists in a valid but unspecified state, so we cannot rely on it
Week 08 | Dynamic Memory Management II COSC1076
Review: Copy Constructors
A Move Constructor allows an object to be created by moving the contents of an r-value into the fields of the object
• The implementation ‘appears’ also identical to a shallow copy, except that r-values are used, thus move operations are invoked!
class Card {
Constructor
Copy Constructor
Move Constructor
Deconstructor
Card(int value);
Card(Card& other);
Card(Card&& other);
Week 08 | Dynamic Memory Management II COSC1076
Review with move semantics
Lets re-examine this with move semantics:
std::vector
std::vector
for (int i = 0; i != 10000; ++i) {
values.push_back(Card(i));
return values;
• STL vector has:
– A push_back method with move semantics, so the created card is moved – A move constructor so the returned vector is also moved!
Week 08 | Dynamic Memory Management II COSC1076
Move Semantics Summary
Using move semantics may not “appear” to be a whole lot different when looking directly at the code
• A slightly different type in functions/methods
• Classes add move contractors which are used by the compiler when it would be more efficient/appropriate to move memory around
However, there are significant consequence for performance and memory management.
Thus C++ has a best-practice rule for classes, which should always implement • Copy Constructor
• Move Constructor
• Deconstructor
Week 08 | Dynamic Memory Management II COSC1076
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com