Abstraction & Containers
COSC1076 Week 06
Copyright By PowCoder代写 加微信 powcoder
What is Analysis?
Related to the concept of Critical Thinking
• Your ability to reason
• You need to be active, not passive
• Go from being “told what to do” to “making your own decisions”
Analysis is about asking the question “Why?” • Why is the code correct?
• Why is the code well-designed?
• Why is the efficient?
Week 06 | Abstraction & Containers COSC1076
How do we go about Analysis
To conduct Analysis we look for:
• A statement of fact
• Conclusive evidence for the fact
• A cause or reason for the fact
• Assumptions, trade-offs or counter-arguments related to the face • Alternative points-of-views
• Where a choice is made by a “judgement call”
Bad Analysis:
• States an opinion
• States beliefs
• Does not acknowledge “judgement calls” but treats them as an absolute • Uses phrases like “believe me” or “trust me” or “I think”
Week 06 | Abstraction & Containers COSC1076
Keywords of analysis activates
These are some keywords that relate to the analysis tasks • Compare
• Contrast
• Differentiate
• Distinguish • Examine
• Illustrate
Week 06 | Abstraction & Containers COSC1076
Data Structures
Data Structures
Data Structures are a core component of good software design
• Choosing the right data structure makes significant difference to performance, execution, memory consumption, etc.
• It is necessary to have a very good understanding of the strengths and weakness of each of the structures
Week 06 | Abstraction & Containers COSC1076
Data Structures
There are only a small number of very fundamental data structures from which more complex structures are derived.
These structures are: • Arrays
You have probably been using a number of these structures
C++ Provides STL containers for a number these structures • Vector
Week 06 | Abstraction & Containers COSC1076
Data Structures
In COSC1076 we will cover in detail: • Array
• Linked Lists
C++ Provides STL containers for a number these structures • Array – Fixed sized array
• Vector – Dynamically sized array
• List – Linked List
• Deque – Double-ended Linked List
Other data structures will be examined in Algorithms & Analysis
Week 06 | Abstraction & Containers COSC1076
Primitive Arrays
So far we have used primitive arrays.
Advantages
• Direct Random Access
• Continuous sequential storage in memory
• Efficient retrieval from RAM, and efficient for Cache
Disadvantages
• Fixed Memory size. Array’s are not extensible and require new memory to be allocated if a large array is required
• Inefficient to add or remove elements from the array
Week 06 | Abstraction & Containers COSC1076
Abstract Data Types (ADTs)
Monolithic Code
At its most extreme, monolithic code consists of one giant main function! • This is clearly not a good thing to do!
The essential algorithm for the application is intermixed with the algorithms for the data structures used by the program.
• Even if multiple functions have been used, the program may still be characteristically monolithic as the essential algorithm and the data structure algorithms are intermixed.
This makes it difficult to:
• Modify or reuse a data structure. • Maintain software
• Understand any of the software
Week 06 | Abstraction & Containers COSC1076
Modular Software
Modular software separates: • Algorithms
• Data Structures
• Third-party tools
The modular approach divides a large program into small components
The modular approach assists with: • Managing complexity of solution • Maintainability
• Correctness!
• Reusability
• Distribution of workload (team of programmers)
Week 06 | Abstraction & Containers COSC1076
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 06 | Abstraction & Containers COSC1076
An interface specifies what a user can do with the module.
It defines available:
• Constants
• Methods/Functions
• Plus, any restrictions and/or assumptions.
The user must use the module only via the provided interface
• Doing otherwise compromises the ability of the module author to change the module implementation.
Week 06 | Abstraction & Containers COSC1076
C++ STL Containers
Fixed sized array
• Wrapper around a primitive C++ array
• Provides generic accessor methods
• Provides iterators (discussed Week 11)
• Provides compatibility with C++ STL features
Documentation: https://en.cppreference.com/w/cpp/container/array
Week 06 | Abstraction & Containers COSC1076
Dynamically sized array
• Starts with a fixed sized array
• Grows if the array “runs-out” of space
• Provides generic accessor methods
• Provides iterators (discussed Week 11)
• Provides compatibility with C++ STL features
Documentation: https://en.cppreference.com/w/cpp/container/vector
Week 06 | Abstraction & Containers COSC1076
Vector Resizing
To resize requires:
• Creating a new larger memory space
• Then copying the contents of the old array into the new array
Week 06 | Abstraction & Containers COSC1076
Measuring Efficiency
“Work” that a program “does”
There are many ways to measure the efficiency of a program • Time to execute code
• Memory Usage
• Number of Disk Read/Write’s
• Number of CPU operations performed • Parallel and Concurrent Programs
We will informally discuss execution efficiency.
• This is the “work” a program does
• This is covered in more detail in Algorithms & Analysis
Week 06 | Abstraction & Containers COSC1076
“Work” that a program “does”
The “work” a program (or ADT) does is:
• The number of operations/steps in a program/algorithm • Approximately:
– The number of CPU operations
– The number of lines of code that is executed
What we are really concerned with is:
• How the “work” increases in relation to the size of the input to the program or ADT
Week 06 | Abstraction & Containers COSC1076
Constant/Linear Time
If the size of the input is given by the value ’n’ then:
• If the number of operations, the “work” is a factor (multiple) of n, we call this
linear time
• If the number of operations, the “work” is unrelated to n, and remains the same regardless of n, this is constant time
Constant vs Linear Time:
• Constant is faster, because the work does not change • Linear is slower
• Constant time is therefore better than Linear time.
(Advanced) The “work” is notated using Big-O notation: • Constant Time: O(k) – for k constant
• Linear: O(n)
Week 06 | Abstraction & Containers COSC1076
Vector Resizing
What is the “work” of resize a vector?
• What is the “size” of the input?
• Creating a new larger memory space
• Then copying the contents of the old array into the new array
Week 06 | Abstraction & Containers COSC1076
Vector Resizing
What is the “work” to change a value of a vector? • What is the “size” of the input?
• Just assign a value
Week 06 | Abstraction & Containers COSC1076
Arrays vs Vectors
Element Types
All elements are same type
All elements are same type
Resizeable
Requires Copy
Storage Layout
Contiguous
Contiguous
Cell lookup
Constant Time Random Access
Constant Time Random Access
Week 06 | Abstraction & Containers COSC1076
Arrays vs Vectors
Insert Front
Linear Time Requires Copy
Linear Time Requires Copy
Insert Back
Constant Time
“Mostly” Constant Time Copy
Remove Front
Linear Time Requires Copy
Linear Time Requires Copy
Remove Back
Constant Time
Constant Time
Week 06 | Abstraction & Containers COSC1076
C++ Generics
To use many of the C++ STL containers, you need to be familiar with how C++ Implements Generics
• It is similar to Java generics
A generic class (or function) has incomplete and parameterised type(s) in its declarations and definition
• The parameterised type(s) are instantiated when an object of the generic class is declared
• The parameterised type(s) are placed inside angle-brackets < >
• Unlike Java, any valid type may be used including:
– Primitive types
– Pointers & References – Classes
vector
vector
vector
Week 06 | Abstraction & Containers COSC1076
Linked Lists
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 06 | Abstraction & Containers COSC1076
Linked List – Node sequence
The core of a linked is a sequence (or “chain”) of nodes
• Stores a single element
• Has a pointer to the “next” node in the sequence/chain
Week 06 | Abstraction & Containers COSC1076
Node Class
A Node is represented as:
class Node {
Node(int data, Node* next);
Node(Node& other);
int data; Node* next;
• Which specifies a sequence/chain, that is list, of integers
Week 06 | Abstraction & Containers 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 06 | Abstraction & Containers COSC1076
LinkedList ADT
A Linked List is represented as:
class LinkedList {
• Which specifies the head (first node) of the list
LinkedList();
~LinkedList();
Node* head;
Week 06 | Abstraction & Containers COSC1076
LinkedList ADT
The ADT methods for a Linked List may include:
class LinkedList {
int size();
void clear();
int get(int i);
void addFront(int data);
void addBack(int data);
Week 06 | Abstraction & Containers COSC1076
Linked List ADT
This is the simplest form of a linked list. More complex lists might also: • Store a count of the number of nodes in the list
• Have a pointer to the end of the list
• And much more!
Linked List
Week 06 | Abstraction & Containers COSC1076
Implementing Linked List ADT
In the rest of this lecture we will implement some of the ADT methods
The golden rule:
• Draw the diagram first!
• If you can draw the diagram, then it makes it easier to implement the code
Week 06 | Abstraction & Containers 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 06 | Abstraction & Containers 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 06 | Abstraction & Containers COSC1076
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com