程序代写代做代考 Java flex c++ algorithm data structure INFO3220: Object Oriented Design

INFO3220: Object Oriented Design

20
18

S1INFO3220: Object Oriented Design
Bernhard Scholz

Bernhard.Scholz@sydney.edu.au

School of Information Technologies, University of Sydney

Semester 1, 2018

20
18

S1Copyright WarningCOMMONWEALTH OF AUSTRALIACopyright Regulations 1969WARNING
This material has been reproduced and communicated to you by or on
behalf of the University of Sydney pursuant to Part VB of the Copyright Act
1968 (the Act).

The material in this communication may be subject to copyright under the
Act. Any further copying or communication of this material by you may be
the subject of copyright protection under the Act.

Do not remove this notice.

20
18

S1
1 Lecture 12: Decoupled Design

Adapter
Decorator
Façade
Similarities and differences between the Adapter, Decorator and
Façade Design Patterns

2 Lecture 13: Introducing the Standard Template Library
The STL Containers

20
18

S1Topic 12: Decoupled Design
Introducing Structural Design Patterns

20
18

S1What is a Structural Design Pattern?Structural Design patterns consider the relationships between the entitieswithin a class. This is different to creational design patterns which are
concerned with the way in which objects are created or behavioural
patterns which consider the way in which objects can change, or the
communication between objects.

As a result the Structural design patterns which will be discussed over the
next few weeks will be concerned with the way in which we can design
classes which are easier to maintain and debug, along with also developing
classes which conform with the SOLID design principles.

20
18

S1Your first structural design patterns
The Wrappers

20
18

S1Our first structural design patternsThe first set of structural design patterns which we will consider are thethree wrappers.
the Adapter / Adaptor
the Decorator
the Façade

These three design patterns have a number of similarities in terms of what
they aim to achieve but their implementations are quite different.

20
18

S1The Adapter Design Pattern
aka The Static Wrapper

20
18

S1Design Pattern: AdapterPurpose/Intent: Give a class a new look-and-feelMotivation: Sometimes existing code that has the functionality we want(the semantics) doesn’t have the right interface we want touse (the syntax)
Applicability: You want to use an existing class but its interface doesn’t

match what you need, or you want to create a resuable class
that cooperates with unrelated / unknown classes — so they
don’t necessarily have compatible interfaces

Benefits: Code reuse!
Limitations: None listed

See Also: Bridge, Decorator

20
18

S1ExampleConsider the case where we have a class IntList. This class has an
interface similar to that of an ArrayList in Java. Our task is
to design a Stack class which contains Integers.

For those that forget a Stack is a First in Last out (FILO) data structure.

20
18

S1ExampleThe header file for our IntClass is as follows1 class IntList
2 {
3 public :
4 IntList ();
5 IntList ( const IntList & intList );
6
7 IntList & operator =( const IntList & intList );
8
9 void add(int value );

10
11 void remove (int index );
12
13 unsigned int size () const ;
14
15 int& operator []( unsigned int index );
16
17 const int& operator []( unsigned int index ) const ;
18
19 };

20
18

S1Exampleand the Stack interface which we must conform to is:1 # ifndef STACK_H
2 # define STACK_H
3
4 class Stack
5 {
6 public :
7 Stack () {};
8
9 virtual int pop () = 0;

10 virtual void push(int value ) = 0;
11
12 virtual unsigned int size () const = 0;
13 };
14
15 # endif // STACK_H

Any ideas how we might implement this . . .

20
18

S1Inheritance VS Object CompositionThere are two approaches that we might apply to implement our newclass. The first is to use a class adapter, which uses multiple inheritance,while the second approach is to use a object adapter which leverages,
object composition.

If we use inheritance then the functionality of the class which we wish to
adapt is inherited (often using private inheritance). This functionality is
then accessed through an alternate (adapted) method.

Object composition is a way to combine simple objects or data types into
more complex ones. Using object composition we encapsulate the class we
wish to adapt.

20
18

S1Structure (Class Adapter)
Request()

Target
Client

Request()
Adapter

Speci�cRequest()
Adaptee

Speci�cRequest()

20
18

S1Structure (Object Adapter)
Request()

Target
Client

Request()
Adapter

Speci�cRequest()
Adaptee

adaptee->Speci�cRequest()

20
18

S1ParticipantsBoth methods treat the participants the same where the:
Target defines the domain-specific interface that Client uses.
Client collaborates with objects conforming to the Target interface.

Adaptee defines an existing interface that needs adapting.
Adaptor adapts the interface of the Adaptee to the Target interface.

20
18

S1Class or Object AdapterA class adapter:adapts the Adaptee to the Target using a concrete implementation of
a class Adapter (one specific derived class of Adapter must be
applied). This is often not ideal, introducing a tight coupling between
the Adapter and the specific Adaptee instance.
lets the Adapter override some of the Adaptee’s behaviour, since
Adapter is know a subclass of Adaptee.
introduces only one object, and no additional pointer indirection is
need to get to the Adaptee.

20
18

S1Class or Object Adapterwhile an object adapter:
lets a single Adapter work with many Adaptees, that is the Adaptee
itself and all its subclasses (if any).
makes it harder to override Adaptee behaviour. It will require
subclassing the Adaptee and making Adapter refer to this subclass
rather than the Adaptee itself. Your almost writing an Adapter for
your Adapter.

20
18

S1What does all this look like in practiceThe Class Adapter approach . . .
1 # ifndef STACKMULTIPLEINHERITANCE_H
2 # define STACKMULTIPLEINHERITANCE_H
3
4 # include ” IntList .h”
5 # include ” Stack .h”
6
7 class StackWithMultipleInheritance : public Stack , private IntList
8 {
9 public :

10 StackWithMultipleInheritance ();
11
12 int pop ();
13 void push(int value );
14
15 unsigned int size () const ;
16 };
17
18 # endif // STACKMULTIPLEINHERITANCE_H

20
18

S1What does all this look like in practice1 # include ” StackInheritance .h”23 StackWithMultipleInheritance :: StackWithMultipleInheritance () : Stack (), IntList ()4 {56 }
7
8 int StackWithMultipleInheritance :: pop ()
9 {

10 if (this ->size () > 0)
11 {
12 int value = this -> operator []( this ->size () -1);
13 this -> remove (this ->size () -1);
14 return value ;
15 }
16 }
17
18 void StackWithMultipleInheritance :: push(int value )
19 {
20 this ->add( value );
21 }
22
23 unsigned int StackWithMultipleInheritance :: size () const
24 {
25 return this -> IntList :: size ();
26 }

20
18

S1What does all this look like in practiceThe Object Adapter approach . . .1 # ifndef STACKOBJECTCOMPOSITION_H2 # define STACKOBJECTCOMPOSITION_H
3
4 # include ” IntList .h”
5 # include ” Stack .h”
6
7 class StackObjectComposition : public Stack
8 {
9 public :

10 StackObjectComposition ();
11
12 int pop ();
13 void push(int value );
14
15 unsigned int size () const ;
16
17 private :
18 IntList m_list ;
19 };
20
21 # endif // STACKOBJECTCOMPOSITION_H

20
18

S1What does all this look like in practice1 # include ” StackObjectComposition .h”23 StackObjectComposition :: StackObjectComposition () : Stack (), m_list ()4 {56 }
7
8 int StackObjectComposition :: pop ()
9 {

10 if ( m_list .size () > 0)
11 {
12 int value = m_list [this ->size () -1];
13 m_list . remove (this ->size () -1);
14 return value ;
15 }
16 }
17
18 void StackObjectComposition :: push(int value )
19 {
20 m_list .add( value );
21 }
22
23 unsigned int StackObjectComposition :: size () const
24 {
25 return m_list .size ();
26 }

20
18

S1What does all this look like in practice1 # include 23 # include ” Stack .h”4 # include ” StackInheritance .h”5 # include ” StackObjectComposition .h”67 int main ()
8 {
9 {

10 Stack * stack = new StackWithMultipleInheritance ();
11 for (int i = 1; i <= 64; i *= 2) 12 { 13 stack ->push(i);
14 }
15 while (stack ->size () > 0)
16 {
17 std :: cout << stack ->pop () << std :: endl; 18 } 19 } 20 { 21 Stack * stack = new StackObjectComposition (); 22 for (int i = 1; i <= 64; i *= 2) 23 { 24 stack ->push(i);
25 }
26 while (stack ->size () > 0)
27 {
28 std :: cout << stack ->pop () << std :: endl; 29 } 30 } 31 } © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 22 / 69 20 18 S1What does all this look like in practice~> g++ AdapterStackExample.cc -o adapterStackExample~> ./adapterStackExample
64
32
16
8
4
2
1
64
32
16
8
4
2
1

20
18

S1Related PatternsTwo related patterns include:
The Bridge design pattern has a structure similar to an object Adaptor,
but Bridge has a different intent. It is meant to separate an interface from
its implementation so that they can be varied easily and independently
while an adaptor aims to change the interface of an existing class.

The Decorator which we will talk about next, is also quite similar
although its aims to add additional functionality without changing the
Adaptee interface and is therefore often referred to as a dynamic wrapper.

20
18

S1The Decorator Design Pattern
aka The Dynamic Wrapper

20
18

S1Design Pattern: DecoratorPurpose/Intent: Attach additional responsibilities to an objectdynamically, providing an alternative to subclassingMotivation: Sometimes we want to add capabilities to individual objects,not to a whole class: inheritance is not very flexible for this.
Applicability: Any time you want to add (or remove) responsibilities to an

object without affecting any others of the same type, and
when subclassing is impractical such as when combinations
of new responsibilities explode

Benefits: More flexible than inheritance, avoids feature-ridden classes
high up in the hierarchy

Limitations: The decorator isn’t the same type as the component, and
there can be a multitude of little objects that look alike but
differ in their decorator connections, which is confusing and
can be hard to debug

See Also: Adapter, Composite, Strategy
© Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 26 / 69

20
18

S1ExampleSuppose you have a TextView object that displays text in a window; it isvery simple with no scroll bars or other annotations, because we will notalways need them.
Sometimes though, we want the whole shebang, with scroll bars and
borders: we would then make a decorated TextView by creating say a
ScrollDecorator that contains the TextView, and then a BorderDecorator
that containts the ScrollDecorator.

Source: GoF

20
18

S1Structure Operation()Component
Operation()
ConcreteComponent

Operation()
Decorator

addedState
Operation()
ConcreteDecoratorA

Operation()
AddedBehaviour()

ConcreteDecoratorB

component->Operation()

Decorator::Operation();
AddedBehaviour();

component

20
18

S1Participants Operation()ComponentOperation()ConcreteComponent Operation()Decorator
addedState
Operation()
ConcreteDecoratorA

Operation()
AddedBehaviour()

ConcreteDecoratorB

component->Operation()

Decorator::Operation();
AddedBehaviour();

component

Component defines the interface for objects that can have responsibilities
added to them dynamically.

ConcreteComponent implements that interface.
Decorator maintains a reference to a Component object and defines an

interface that conforms to that of Component.
ConcreteDecorator adds the desired responsibilities to the component

20
18

S1How is this a wrapper then?This approach is a wrapper as the Decorator takes ownership of theConcreteComponent class. It then appends the functionality to theconcrete class using ConcreteDecorators.
When implementing a Decorator it is always important to remember that
the Decorator conforms to the Component interface and contains a pointer
to a Component object, what will be the ConcreteComponent which we
decorate.

Therefore, the Decorator wraps the Component along with inheriting from
it and yes I found that confusing the first time I starting working with this
design pattern.

20
18

S1ImplementationIt’s important to remember some details here:Interface conformance: the decorator’s object must conform to theinterface of the component it is decorating: that meansConcreteDecorator must inherit from a common class (in
C++ at least!)

Omitting the abstract Decorator class is fine if you only want to ever
add one responsibility.

Lightweight components are best: the common Component class should
focus on functionality, not storing data, else the decorators
will get very heavy; further, there should not be too much
functionality in the common class because it may not be
needed in all subclasses.

Skins: the decorator is like a “skin” : it adds a little functionality
only, not the “guts” of the object it is decorating. For a
pattern that changes the “guts” see Strategy.

20
18

S1Decorator Example1 // file: decorator .h2 # pragma once3 # include 4 class Widget // Component class5 {6 public :7 virtual void draw () = 0;
8 virtual ~ Widget () { }
9 };

10 class TextView : public Widget // Concrete Component
11 {
12 public :
13 void draw () override {
14 std :: cout << "\ tdraw text -view" << std :: endl; 15 } 16 }; 17 class Decorator : public Widget // Decorator 18 { 19 Widget * m_widget ; 20 public : 21 Decorator ( Widget * widget ) : m_widget ( widget ) {} 22 void draw () override { 23 m_widget ->draw (); // draw by delegation
24 }
25 };

20
18

S1Decorator Example1 // file: concreteDecorator .h2 # pragma once3 # include ” decorator .h”4 class BorderDecorator : public Decorator5 {6 public :7 BorderDecorator ( Widget * widget ): Decorator ( widget ){} // Concrete Decorator
8 void draw () override {
9 Decorator :: draw ();

10 std :: cout << "\ tdraw border - decorator " << std :: endl; 11 } 12 }; 13 class ScrollDecorator : public Decorator // Concrete Decorator 14 { 15 public : 16 ScrollDecorator ( Widget *w): Decorator (w){} 17 void draw () override { 18 Decorator :: draw (); 19 std :: cout << "\ tdraw scroll - decorator " << std :: endl; 20 } 21 }; © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 33 / 69 20 18 S1Decorator Example1 // file: decorator .cpp2 # include " decorator .h"3 # include " concreteDecorator .h"4 int main ()5 {6 // construct text -view with border and sroll - decorator7 std :: cout << "My text -view" << std :: endl; 8 Widget *mine = new BorderDecorator (new ScrollDecorator (new TextView ())); 9 mine ->draw ();

10 // construct text -view with sroll – decorator only
11 std :: cout << "Your text -view" << std :: endl; 12 Widget * yours = new ScrollDecorator (new TextView ()); 13 yours ->draw ();
14 }

~> g++ decorator.cc -o decorator
~> ./decorator
My text-view

draw text-view
draw scroll-decorator
draw border-decorator

Your text-view
draw text-view
draw scroll-decorator

20
18

S1The Façade Design Pattern
aka The Library Wrapper

20
18

S1Design Pattern: FaçadePurpose/Intent: Provide a unified interface to a set of interfaces in asubsystem. Façade defines a higher-level interface thatmakes the subsystem easier to use.Motivation: Simplify the interaction of clients with multiple classes
through a single interface

Applicability: Any time a simple interface is sought between a (set of)
client(s) and a complex subsystem (other interfaces can be
provided for clients that need custom access)

Benefits: Shields the clients from the subsystem, promotes weak
coupling between subsystem and clients; reduces compilation
dependencies; still permits applications direct access to the
subsystem

Limitations: None listed
See Also: Abstract Factor, Mediator

20
18

S1Structure
Facade

client

The structure is very
simple: within the
collection of subsystems
there can be any number of
interactions, and the
subsystems do not “know”
about the facade. The
facade knows how to
interact with each of the
subsystems that clients
need.

20
18

S1Participants
Facade

client

Façade delegates requests to the
correct subsystem components
subsystem components
implement the subsystem
functionality, handle work
assigned by the Façade, but keep
no reference to it.

20
18

S1Facade Example1 struct Pump {2 void pump () { }3 };4 struct Heater {5 void heatWater () { }6 };7 struct Grinder {
8 void grind () { }
9 };

10 class CoffeeMachine // facade
11 {
12 private :
13 Grinder grinder ;
14 Pump pump;
15 Heater heater ;
16 public :
17 void makeCoffee () {
18 grinder . grind ();
19 heater . heatWater ();
20 pump.pump ();
21 }
22 };

20
18

S1Implementation notesImplementing a Façade is very easy as it is never a required method toaccess the subsystem components: it can be added to gradually as asystem develops.
Implementing a good Façade can be challenging as the aim of the Façade
is to hide the complexity of the subsystem and provide a simplified way in
which to use the system. This often requires expert knowledge of the
system and how it is going to be extended.

C++ : The Façade needs to have access to the subsystem components
but it may be that the subsystem should be otherwise private: the use of
namespaces can help here.

20
18

S1Examples of where one would use a FaçadeAs the Façade provides a simplified interface to a larger body of code it is
often used to:

make a software library easier to use, understand and test.
reduce dependencies of outside code on the inner workings of a library.
wrap a poorly designed collection of libraries into a single (hopefully)
well-designed library

20
18

S1Related patternsAbstract Factory can be used with Façade to provide an interface forcreating subsystem objects; alternatively it could be used instead ofFaçade to explicitly hide the platform-specifics.
Mediator is a similar pattern to Façade in that it also forms a conduit
through which clients talk to subsystems; the difference being that the
purpose of Mediator is to abstract arbitrary communication between
objects and possibly handle functionality that doesn’t belong in any one of
them. It’s a bit more coupled than the Façade in this way.

It’s rare to want more than one Façade so the may be implemented as a
Singleton.

20
18

S1Comparing the Wrapper Design Patterns
Similarities and differences between the
Adapter, Decorator and Façade Design

Patterns

20
18

S1SimilaritiesThe Adapter, Decorator and Façade all rely on inheritance for theirimplementations, even in the case where the adapter is implemented using
Object Composition.

All three wrappers conform with at least one SOLID design principles. The
Adaptor design pattern conforms with the Dependency inversion principles,
the Decorator Design pattern conforms with the Open-Closed Principle
and all three patterns conform to the Single Responsibility Principle.

All three Design patterns aim to provide a simple interface.

20
18

S1DifferencesWhile all three Design Patterns wrap a class or classes they all aim toprovide a different set of functionality. The Adapter aims to provide a new
interface for an existing class using with Object Composition or Multiple
Inheritance while the Façade aims to provide a new interface for a
complete subsystem without using either Object Composition or Multiple
Inheritance. Rather than encapsulate the entire subsystem it aims to
delegate responsibility. The Decorator unlike either the Façade or the
Adapter does not provide a new interface rather dynamically adds
properties to an instance of a class rather than the class itself.

20
18

S1DifferencesTherefore the best way to remember their differences is that:
The Adapter provides a new interface for an existing class which is
more well suited for the current task.
The Decorator dynamically adds additional functionality to the
instance of a class
The Façade provides a new simplified interface for a complex
subsystem.

20
18

S1Topic 13: Introducing the Standard TemplateLibrary
. . . cause who wants to have to rewrite the

wheel

20
18

S1Containers
Containers in the Standard Library

20
18

S1Before we beginThere is disagreement over what “the STL” is.
Some say it’s the entire standard C++ library, which includes things aren’t
templated.

Some say that it’s just the library of templated containers and algorithms
that were invented by Alexander Stepanov.

Some don’t care.

20
18

S1We consider the STL as . . .For our purposes we consider the STL as a set of templatedContainers
Algorithms
Iterators
Functors

Today we are going to start with containers but we will look at all four
throughout the semester.

20
18

S1The Standard LibraryThe Standard (Template) Library has a great collection of containers.We will look first at the simpler containers, in particular the sequential
containers

vector
list
deque

and the sequential container adapters
stack
queue
priority_queue

20
18

S1ContainersWhat is a container? Just a thing to hold items.
The containers are similar in intention to the Collection Classes in Java,
and have some similar behaviours: you can

add to them
get their size
find things in them
clear them
construct and delete them

20
18

S1The containers are templatedWhat does this mean? For the moment, the only consequence of this is
that for each container you must specify the type it will store.

1 std :: vector values ; // a vector of ints
2 std :: list messages ; // a list of strings
3 std :: deque means ; // a double -ended – queue of floats

20
18

S1Containers know how to allocate storage for themselves
All containers are Allocator-aware: The container uses an allocator object
to dynamically handle its storage needs. We’re not going to get into this.

20
18

S1The container interface
There is a common interface in a sense for all the containers: some
operations are supported by every container.

20
18

S1Sequential ContainersAs mentioned the sequential containers arestd::vector: #include
std::list: #include std::deque: #include

Where

a std::vector is equivalent to an ArrayList in Java.
a std::list is equivalent to an LinkedList in Java.
a std::deque is equivalent to an Deque in Java.

20
18

S1Declare and InitialiseSequential containers are declared as you’d expect, and can be initialisedin several ways: here’s a quick run-down:Container Constructors
C c Create an empty container c of elements of type

T. C is a container, e.g., vector, list, deque.
C c(o) calls the copy constructor of c

C c(begin,end) c is created by providing a range of iterators from
begin to end, not including end.

C c(n, init) Create container c with n copies of init
C c(n) Create c as n “value-initialised” items.

The last two of these can only be used to construct sequential containers –
but they can be used for any sequential container, so that’s pretty good.

20
18

S1Operations on vectorAside from constructing them, sequential containers can all be operated onwith these commands (I’ll use vector just as a handy example):Consider the vectors v1 and v2
v1.empty() returns true iff v1 is empty
v1.size() returns the number of elements in v1

v1.push_back(value) adds element value to the end of v1
v1.back() accesses the last element of the v1

v1.pop_back() removes the last element of the v1
v1[n] accesses the n-th element of v1

v1 = v2 copies the value of v2 to v1
v1 == v2 compares sizes and then elements in order

20
18

S1vector demo1 # include 2 # include 3 # include 45 bool isPrime (int number )6 {7 for (int i = 2; i <= sqrt( number ); ++i) 8 { 9 if ( number % i == 0 && i != number ) 10 { 11 return false ; 12 } 13 } 14 return number > 1;
15 }
16
17 int main ()
18 {
19 std :: vector dynamicArray ;
20 for (int i = 1; i <= 100; ++i) 21 { 22 if ( isPrime (i)) 23 { 24 dynamicArray . push_back (i); 25 } 26 } 27 for ( size_t i = 0; i < dynamicArray .size (); ++i) 28 { 29 std :: cout << dynamicArray [i] << std :: endl; 30 } 31 } © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 59 / 69 20 18 S1vector demo~> g++ VectorDemo.cc -o vectorDemo~> ./vectorDemo2357
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

20
18

S1The subscript []This permits you to treat the (sequential) container as though it were an
array: you give it the index i and access the i-th item in the container
exactly as you would a pointer.

For example the code that we would rewrite if we used a dynamic pointer
array looks very similar.

20
18

S1The subscript []1 # include 2 # include 34 bool isPrime (int number )5 {6 for (int i = 2; i <= sqrt( number ); ++i)7 { 8 if ( number % i == 0 && i != number ) 9 { 10 return false ; 11 } 12 } 13 return number > 1;
14 }
15
16 int main ()
17 {
18 int* dynamicArray = new int [100];
19 int lastAllocatedIndex = 0;
20 for (int i = 1; i <= 100; ++i) 21 { 22 if ( isPrime (i)) 23 { 24 dynamicArray [ lastAllocatedIndex ++] = i; 25 } 26 } 27 for (int i = 0; i < lastAllocatedIndex ; ++i) 28 { 29 std :: cout << dynamicArray [i] << std :: endl; 30 } 31 } © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 62 / 69 20 18 S1The other sequential containers Before we move on let’s look at the other sequential containers . . . © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 63 / 69 20 18 S1Operations on listConsider the lists l1 and l2l1.empty() returns true iff l1 is empty l1.size() returns the number of elements in l1 l1.push_front(value) adds element value to the front of l1 l1.front() accesses the first element of l1 l1.pop_front() removes the first element of l1 l1.push_back(value) adds element value to the end of l1 l1.back() accesses the last element of the l1 l1.pop_back() removes the last element of l1 l1 = l2 copies the value of l2 to l1 l1 == l2 compares sizes and then elements in order © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 64 / 69 20 18 S1Operations on dequeConsider the lists d1 and d2d1.empty() returns true iff d1 is empty d1.size() returns the number of elements in d1 d1.push_front(value) adds element value to the front of d1 d1.front() accesses the first element of d1 d1.pop_front() removes the first element of d1 d1.push_back(value) adds element value to the end of d1 d1.back() accesses the last element of the d1 d1.pop_back() removes the last element of d1 d1[n] accesses the n-th element of d1 d1 = d2 copies the value of d2 to d1 d1 == d2 compares sizes and then elements in order © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 65 / 69 20 18 S1Picking the write container for the right jobIt is important that we don’t become to reliant on the STL to the point that we forget what we have learnt from previous courses. For example if I were to substitute a std::list instead of a std::vector then do
we improve or degrade efficiency?

What about a std::deque?

20
18

S1Picking the write container for the right jobIf we were to rewrite the previous class so that the list does not degradecomplexity and actually works then we would need to write it as follows oruse could use an iterator which we will discuss in the lectures next week.
1 # include
2 # include 3
4 int main ()
5 {
6 {
7 std :: list hardDriveSet ;
8 hardDriveSet . push_back ( SolidStateDrive ());
9 hardDriveSet . push_back ( HardDiscDrive ());

10 hardDriveSet . push_back ( HardDiscDrive ());
11 while (! hardDriveSet . empty ())
12 {
13 std :: cout << hardDriveSet . front (). getPartInformation () << std :: endl; 14 hardDriveSet . pop_front (); 15 } 16 } 17 } © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 67 / 69 20 18 S1Picking the write container for the right jobSo in the previous example the std::vector was the bestchoice, let’s try another example.
You are provided a sorted list of doubles which will be stored in your new
data structure. This values will need to stored such that you can return
the smallest and largest items in O(1), along with removing these items in
O(1). Which of the STL containers we have seen today is most
appropriate and why?

Is there more than one choice?

20
18

S1Picking the write container for the right jobThe final task today is to think which of the underlying containers youwould use to implement a data structure that conforms to the interfaces of
both a Stack (FILO) and a Queue (FIFO). This is your tutorial exercise
next week where you will be implementing a StringStackQueue using an
object Adapter and a STL container.

For your interest this is a (rather) common interview question.

Lecture 12: Decoupled Design
Adapter
Decorator
Façade
Similarities and differences between the Adapter, Decorator and Façade Design Patterns

Lecture 13: Introducing the Standard Template Library
The STL Containers

Related Posts