程序代写代做代考 python algorithm c++ Java flex chain cache compiler 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 14: Abstracting away tight coupling

Bridge
Composite
Proxy

2 Lecture 15: Associative Containers and STL Algorithms
Associative Containers

20
18

S1Topic 14: Abstracting away tight coupling
The Bridge, Composite and Proxy

20
18

S1The Bridge Design Pattern
separating responsibilities into different classes

20
18

S1Design Pattern: BridgePurpose/Intent: Decouple an abstraction from its implementation so thetwo can vary independentlyMotivation: The usual way to have multiple implementations of aninterface is inheritance, but this is sometimes not flexible
enough

Applicability: Use this pattern when you want to decouple the binding
between interface and implementation, when both should be
extensible through inheritance, when changes in the
implementation should have no impact on clients

Benefits: Much better decoupling and flexibility, better extensibility,
and implementation is hidden from clients

Limitations: Has to be constructed up front
See Also: Abstract Factory (to create and configure a Bridge), Adapter

20
18

S1ExampleSuppose you have a Window abstraction that permits you to displaywindows on multiple platforms: you might then subclass it withPhoneWindow and PCWindow.
Window

PCWindow PhoneWindow

20
18

S1Example (cont.)Suppose you then have a subclass of Window that permits a fancy display,e.g. extra with icons: IconWindow.In this situation you’d have to implement subclasses of IconWindow forboth PCWindow and PhoneWindow:
Window

PCWindow PhoneWindow IconWindow

PCIconWindow PhoneIconWindow

20
18

S1Example (cont.)The Bridge gets around this by separating the abstract and concretehierarchies. In the above case we might end up with something more likethis:
bridgeDrawText()DrawRect()

Window
DeviceDrawText()
DeviceDrawLine()

WindowImplementation

imp->DeviceDrawLine()
imp->DeviceDrawLine()
imp->DeviceDrawLine()
imp->DeviceDrawLine()

DrawBorder()
IconWindow

DrawCloseBox()
TransientWindow

DrawRect()
DrawText()

DrawRect()

DeviceDrawText()
DeviceDrawLine()

PhoneWindowImp
DeviceDrawText()
DeviceDrawLine()

PCWindowImp

PhoneDrawLine()

PhoneDrawString()

implementation

20
18

S1Example
In this example all operations on Window subclasses are implemented in
terms of abstract operations from the WindowImplementation interface.
This separates / decouples the window abstractions from the
platform-specific implementations, so we can vary the two independently.

20
18

S1Structure
Operation()
Abstraction

RefinedAbstraction
OperationImp()
ConcreteImplementorA

OperationImp()
Implementor

imp->OperatorImp()

OperationImp()
ConcreteImplementorB

imp

Client

20
18

S1Participants Operation()Abstraction
RefinedAbstraction

OperationImp()
ConcreteImplementorA

OperationImp()
Implementor

imp->OperatorImp()

OperationImp()
ConcreteImplementorB

imp

Client

Abstraction defines the abstraction’s interface and maintains a reference
to an object of type Implementor.

Refined Abstraction extends the Abstraction classes interface.
Implementor defines the interface for the implementing classes: it can be

quite different from the interface of Abstraction: usually
Implementor’s interface is very primitive and Abstraction has
higher level operations based on these primitives.

ConcreteImplementor implements the Implementor interface and defines
the concrete implementation.

20
18

S1ImplementationAlthough in C++ we can use multiple inheritance to combine an interfacewith its implementation, e.g., by inheriting publicly from Abstraction and
privately from ConcreteImplementation, this permanently binds the
implementation to its interface.

This means that you can’t implement a true Bridge with multiple
inheritance in C++.

If there’s only one implementation, then you don’t really need the full
Bridge: the abstract Implementor class isn’t necessary.

20
18

S1More implementationIf Abstraction knows about all the ConcreteImplementor clases then it caninstantiate one of them in its constructor and construct different concreteobjects based on input parameters such as getting a list size (sometimes a
linked list is fine).

(Another idea is to change implementation on the fly if the situation
demands it, e.g., if a list gets bigger so a previous implementation is no
longer adequate.)

Alternatively one could delegate such responsibilities to another object like
a Factory to create the correct platform-specific objects.

20
18

S1Another exampleIn the previous example we considered a broad use for the application of aBridge which was rather abstract. In the next example we will consider a
more low level implementation of a Bridge so that we can see some code.

Consider the case where we have a base class Shape and a Circle class
which implements Shape. In this example these are the Abstraction and
Concrete Abstraction respectively.

20
18

S1Another exampleIn this system we have three approaches to render a shape using differentrendering libraries. Our aim is to take these three approaches and decouple
them from the Shape classes.

To do this we will create three new classes RendererImplementation1,
RendererImplementation2, and RendererImplementation3 which all
implement the Renderer interface. There are our ConcreteImplementers
and our Implementer respectively.

20
18

S1The Implementers1 class Renderer2 {3 public :4 virtual void drawCircle ( double x, double y, double radius ) = 0;5 };67 class RendererImplementation1 : public Renderer
8 {
9 public :

10 void drawCircle ( double x, double y, double radius )
11 {
12 std :: cout << " Calling RendererImplementation1 drawCircle function " << std :: endl; 13 } 14 }; 15 16 class RendererImplementation2 : public Renderer 17 { 18 public : 19 void drawCircle ( double x, double y, double radius ) 20 { 21 std :: cout << " Calling RendererImplementation2 drawCircle function " << std :: endl; 22 } 23 }; 24 25 class RendererImplementation3 : public Renderer 26 { 27 public : 28 void drawCircle ( double x, double y, double radius ) 29 { 30 std :: cout << " Calling RendererImplementation3 drawCircle function " << std :: endl; 31 } 32 }; © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 16 / 62 20 18 S1The Abstractions1 class Shape2 {3 public :4 Shape ( Renderer * renderer ) : m_renderer ( renderer ) {}5 virtual ~ Shape () {};67 virtual void draw () = 0; 8 virtual void resizeShape ( double percentage ) = 0; 9 protected : 10 Renderer * m_renderer ; 11 }; 12 13 class Circle : public Shape 14 { 15 public : 16 Circle ( double x, double y, double radius , Renderer * renderer ) 17 : Shape ( renderer ), m_xCoordiante (x), m_yCoordiante (y), m_radius ( radius ) {} 18 virtual ~ Circle () { } 19 20 void draw () 21 { 22 m_renderer -> drawCircle ( m_xCoordiante , m_yCoordiante , m_radius );
23 }
24 void resizeShape ( double percentage )
25 {
26 m_radius *= percentage ;
27 }
28 private :
29 double m_xCoordiante ;
30 double m_yCoordiante ;
31 double m_radius ;
32 };

20
18

S1All together1 int main ()2 {3 std :: vector < Shape *> vector ;4 vector . push_back (new Circle (1, 2, 4, RendererFactory :: getRendererImpl1 ()));5 vector . push_back (new Circle (11 , 21, 6, RendererFactory :: getRendererImpl2 ()));6 vector . push_back (new Circle (-1, -2, 3, RendererFactory :: getRendererImpl3 ()));7
8 for ( size_t i = 0; i < vector .size (); ++i) 9 { 10 vector [i]->draw ();
11 // cleaning up
12 delete vector [i];
13 }
14 }

~> g++ BridgeExample.cc -o bridgeExample
~> ./bridgeExample
Calling RendererImplementation1 drawCircle function
Calling RendererImplementation2 drawCircle function
Calling RendererImplementation3 drawCircle function

20
18

S1Isn’t a Bridge just a fancy Adapter?The Bridge design pattern has a structure similar to an object Adapter,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 Adapter aims to change the interface of an existing class.

Therefore, the Bridge works well if we want to extend an existing class,
decoupling the implementation details of a specific feature of the class
from its implementation. The Adapter is more suited if we wish to reuse
an existing class for a new purpose but apply a new (often more relevant)
interface.

20
18

S1The Composite Design Pattern
describes groups of objects which should

treated in a common fashion

20
18

S1Design Pattern: CompositePurpose/Intent: Compose objects into tree structures, so individualyobjects and compositions of objects can be treated the samewayMotivation: Creating graphical objects that contain other graphical
objects can get unweildy with several levels of more and
more specialised items contained

Applicability: Whenever you want to represent part-whole hierarchies of
objects, and client code to treat objects uniformly

Benefits: A short inheritance hierarchy gives rise to an arbitrarily large
composition hiearchy; client can be very simple

Limitations: Can make the design too general: ease of adding new
components means it’s hard to restrict what components a
composite has, which can’t be constrained using the type
system

See Also: Chain of Responsibility, Decorator, Flyweight, Iterator, Visitor
© Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 21 / 62

20
18

S1Example

20
18

S1ExampleSuppose you’re writing a calculation machine. You need to form arbitraryexpressions like r1,r2 = −b±pb2−4ac2a
Each expression needs to be
evaluable somehow, and the
complete expression can be
evaluated only when all of its
components have been
evaluated.
This is a very common place you
would use the composite design.
The other is in the design of
GUIs.
How would you minimally
transform the composite object
represented by the tree on the
right to get the other root?

In this example the expression tree for r1
would be

Divide

Add

Negate

Square Root

MultiplySquare

Subtract

Multiply4

a c

Multiply

2 a

20
18

S1StructureClient Operation()Add(Component)Remove(Component)GetChild(int)Component
Operation()

Leaf
Operation()
Add(Component)
Remove(Component)
GetChild(int)

Composite

for all g in children
g.Operation()

children

20
18

S1ParticipantsComponent declares the interface for objects in the composition, andimplements common behaviour; declares an interface formanaging its children.Leaf has no children, defines behaviour for primitive objects
Composite defines behaviour for components having children and stores

those children, implements the operations defined in
Component;

Client manages the objects in the composition only through the
Component interface.

20
18

S1ImplementationSome useful notes on how to implement this:Parent references It’s often useful to navigate back up a composition treeusing references to the parent: these references have to bemaintained as a class invariant though, so should only be
changed when adding a component to a composite.

Sharing components This doesn’t work well with having parent references!
But it’s sometimes useful when you have components that
can be contained in more than one composite item (like ‘b’
above).

Maximizing the Component interface seems a good way to go, to ensure
that the client doesn’t have to care about which component
object is being called, but that doesn’t sit well with the
“don’t implement interface you don’t need” paradigm. A
little creativity is often needed to reconcile these. . .

20
18

S1Implementation (cont.)Managing the children is always an issue (trust me); and in this case itmanifests as a conflict between putting the implementationof child management at the base or in the derived classes: ifthey’re in the base, then derived classes might attempt to dothe impossible or meaningless such as adding components to
a leaf; if they’re in the Composite objects only then you lose
transparency as then Leaf and Composite have different
interfaces.

Containment of child objects as a set in a Component takes up space
which you might not want to waste if you have many Leaf
objects.

Ordering may be important: if it is, as with the expression tree
example, then you need to ensure that the ordering is
maintained correctly in whatever containers you use for the
children (e.g., not a set!).

20
18

S1Implementation (cont.)Destruction of a composite should cause the destruction of its children(think about the order in which these should occrur!), atleast in the cases where Leaf objects cannot be shared.
© Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 28 / 62

20
18

S1The Proxy Design Pattern
. . . delegating responsibilities

20
18

S1Design Pattern: ProxyPurpose/Intent: (a.k.a. Surrogate) Provide a surrogate or placeholder foranother object to control access to itMotivation: Use a stand-in object in place of one that is expensive tocreate, until the expensive one is really needed
Applicability: Whenever there is a need for a more sophisticated reference

to an object than just a simple pointer (types next)
Benefits: Can enable optimizations such as creation only when needed

and copy only when altered
Limitations: May have issues with how to refer to the subject of the proxy

before it’s instantiated
See Also: Adapter, Decorator

20
18

S1More on ApplicabilityThere are a few different varieties of proxy with slightly differentapplicability:remote proxy provides a local representative for an object that is in adifferent address space;
virtual proxy only creates expensive objects on demand, such as keeping a

file name of an image and then only instantiating the image
when needed;

protection proxy controls access to the original object: useful when objects
should have differing access rights;

smart reference replaces a pointer and has additional functionality such as
reference counting, loading expensive objects into memory
when first referenced, etc.

20
18

S1ExampleSuppose you have a WYSIWYG document preparation system (not LATEXthen) that can include images in the documents. The images could behuge so it’s not a great idea to have to load them all in at once intomemory before they’re displayed: perhaps in a multi-page document they’d
not be observed even once through an editing session.

The Proxy pattern helps here because it makes a surrogate or placeholder
in case the image needs to be displayed.

aTextDocument
image anImageProxy

filename anImagedata

in memory on disc

20
18

S1WYSIWYG Example StructureDocumentEditor Draw()GetExtent()Store()Load()Graphic
imageImp
extent

Draw()
GetExtent()
Store()
Load()

Image

imageImp
extent

Draw()
GetExtent()
Store()
Load()

ImageProxy
image

if (image == nullptr) {
image = LoadImage(fileName);
}
image->Draw();

if (image == nullptr) {
return extent;
}
return image->GetExtent();

The document editor accesses images through Graphic interface; ImageProxy
maintains a filename as the reference to the image, which is passed to the
ImageProxy’s constructor.
ImageProxy stores the extent (bounding box) and a reference to the real image,
which will only be non-null if the image needs to be displayed (knowing the extent
without displaying it helps with the page formatting).

20
18

S1Structure Request()… Subject
Request()
…

RealSubject
Request()
…

Proxy …
realSubject->Request();
…

realSubject

20
18

S1ParticipantsProxy maintains a reference to the real subject, through whichaccess is granted; may refer to a Subject if the interfaces arethe same, and may handle creation and destruction. Otherresponsibilities of Proxy are specific to the different varieties:
remote proxies encode requests and their arguments and
pass them to Subject;
virtual proxies may cache information about the Subject
to delay accessing the real thing;
protection proxies handle access appropriately for
different clients

Subject defines the common interface for both the RealSubject and
the Proxy

RealSubject defines the real / concrete object that the proxy represents.

20
18

S1A design pattern updateWe have now looked at six of the seven structural design patterns we willconsider in this course and twelve of the twenty four design patterns wewill look at in varying detail (including RAII).
We will consider the Flyweight, the last of the structural design patterns
together with the Observer Behavioural design pattern when we discuss
the STL smart pointer in Week 11.

Before then, however, you will be introduced to a number of Behavioural
design pattern starting next week with the Iterator and the Template
Method.

20
18

S1
Topic 15: Associative Containers and STL

Algorithms

20
18

S1The Associative Containers
set, map, multimap, bitset and multiset

20
18

S1Associative Containers
set, map, multimap, bitset and multiset.

We will look at the pair class first, then map and set. The others you can
investigate yourself.

20
18

S1pairA pair is a templated type that joins two items into a convenient object.This turns out to be an important class for associative containers.pair is in the std namespace, and it’s used in the obvious ways. Some ofthe common ones are:
constructors

1 pair p; // default constructor , elements value – initialised
2 pair q(p);
3 pair grade (“M. Reynolds “, ‘P’);

make_pair(v1,v2) creates a pair from the values v1, v2, with the types
inferred from those of the arguments.

return from map::find() the iterator returned from map::find() refers
to a (key,value) pair

return from map::insert() this returns a pair whose first element is an
iterator referring to the position of the thing just inserted,
and the second element is a bool marked true if the insertion
really happened and false if there was already an element
present.

20
18

S1Associative ContainersThese containers have a restricted set of operations defined on them:constructors The first three constructors as for vector;relational operators <, <=, >, >=;end operators begin, end, rbegin, rend;
typedefs size_type, iterator, const_iterator,

reverse_iterator, const_reverse_iterator,
difference_type, value_type, reference,
const_reference;

swap and simple = assignment swap is a very quick way to swap the
contents of two collections;

clear and erase removing everything or everything-in-a-range (defined
by iterators);

size to tell how many items there are in the container.

20
18

S1mapA map is probably what you’re most likely to imagine is an associativecontainer. It’s also known as a dictionary (Python) or a hashmap (Java) orassociative array (Perl).
A map is similar to a mathematical map, which associates with each
unique key, some kind of value. Hence we talk about (key, value) pairs.
Remember, keys are unique in a map.

Maps are declared and manipulated quite simply (don’t forget to
#include

1 map marks ;
2 marks [“A Rimmer “] = 0;
3 marks [“M Reynolds “] = 47;
4 // threatening behaviour ensues
5 marks [“M Reynolds “] += 5;

20
18

S1map (cont.)The above example demonstrates how we can create a map and subscriptit.The type returned from this subscript operation is of the value type — inthis case, int.Note! If there isn’t an element with the given key in code such as that
above, a new item will be added. That means we can have quite succinct
code if we know what we’re doing:

1 map word_count ;
2 string word;
3 while (cin >> word)
4 ++ word_count (word );

Another note! When we use the subscript like this, the value part of the
item we’re adding is value-initialised, and we very frequently immediately
then assign a new value to it, so we’re doing extra work. It’s more efficient
to use a different approach. . .

20
18

S1Aside: value-initialised? zero-initialised?Let’s just consider a couple of cases. I’m setting up some very simpleclasses (calling them structs so everything’s public by default), to showsome things you should be careful of:1 struct A { int m; }; // Plain Old Data or “POD”
2 struct B { ~B (){}; int m; }; // non -POD , compiler generated default ctor
3 struct C { C() : m() {}; ~C (){}; int m; }; // non -POD , default – initialising m
4 struct D { D (){}; ~D (){}; int m; }; // non -POD , default – initialising m

1 A a; // this happens if I use A* a = new A; too
2 cout << "A a yields " << a.m << " ( indeterminate value )" << endl; 3 A* a2 = new A(); 4 cout << "new A() yields " << a2 ->m << " (zero - initialised because it 's POD)" << endl; 5 B b; 6 cout << "B b yields " << b.m << " ( default initialises as no ctor called )" << endl; 7 B* b2 = new B(); 8 cout << "new B() yields " << b2 ->m << " (value - initialises b2 , so zero initialises its field )" << endl; 9 C c; 10 cout << "C c yields " << c.m << " (default - initialises , so calls default ctor which we wrote )" << endl; 11 C* c2 = new C(); 12 cout << "new C() yields " << c2 ->m << " (value - initialises , so calls default ctor as before )" << endl; 13 D d; 14 cout << "D d yields " << d.m << endl; The output from the above is, at least on my machine, © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 44 / 62 20 18 S1Aside: value-initialised? zero-initialised? (cont.)A a yields 1610479016 (indeterminate value)new A() yields 0 (zero-initialised because it's POD)B b yields 1610479424 (default initialises as no ctor called)new B() yields 0 (value-initialises b2, so zero initialises its field)C c yields 0 (default-initialises, so calls default ctor which we wrote)new C() yields 0 (value-initialises, so calls default ctor as before)D d yields 1602358376 Confused? Bottom line: always initialise things. © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 45 / 62 20 18 S1 Ok, back to maps © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 46 / 62 20 18 S1map1 map marks ;2 marks . insertProperties: maps
are Associative: Elements in associative containers are referenced by their

key, and not by their absolute position in the container.
are Ordered: The elements in the container follow a strict order at all

times. All inserted elements are given a position in this
order. This has consequences for performance, of course!

are Maps: Each element associates a key to a mapped value: Keys are
meant to identify the elements whose main content is the
mapped value. These associations are stored as (key, value)
pairs.

have Unique keys: In a map, no two elements in the container can have
equivalent keys (though they could have equivalent values).

20
18

S1Adding items to a mapOn the other hand we can add elements using a more open approach thanthis subscripting (which hides lots of detail):1 map m;
2 m. insert (e)

where e is a value of the right value_type for m. If e.first is not in the
map, then e is added; otherwise m is unchanged.

Interesting factoid: the pair returned by an insert operation like this is
of the form (e.first, b) where b is a bool variable that’s true if and
only if the element was added.

We can also add ranges of things using iterators. These don’t have the
nice “it was inserted ok” flag.

20
18

S1The type of eIn the above code the type is kind of awkward:1 map :: value_type
so adding an element could look like this:

1 word_count . insert (map :: value_type (” River “, 27));

This can be tidied either with an appropriate typedef like this:
1 typedef map :: value_type valType ;
2 word_count . insert ( valType (” River “, 27));

or using the built-in make_pair:
1 word_count . insert ( make_pair (” River “, 27));

— either is fine.

20
18

S1Interrogating without damageIf you’re attempting to find an item in a map without adding the item, youneed to do something else.The count and find methods are your friend here:1 map m;
2 m.add( make_pair (” clones “, 2500));
3 m. count (” clones “); // returns 0 (not in the container ) or 1

count(k) returns 0 or 1 to mean the item is not, or is, in the container
respectively.

find(k) returns an iterator to the element in the container indexed by
k. Note that this is a pair.

20
18

S1setA set of objects is a convenient mechanism for storing elements that mustbe different: they must have different key values according to some
comparator.

Sets are as simple to create and use as vectors (remembering to
#include of course):

1 set myNumbers ;
2 myNumbers . insert (2);
3 myNumbers . insert (54);
4 cout << myNumbers .size (); © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 51 / 62 20 18 S1set (cont.)To see if an element is in the set we have two options: find and count.find returns an iterator to the item in the collection if it is present,and the one-past-the-end iterator otherwise. What happensif we dereference that? Yes, the behaviour is undefined. count returns the number of times the item occurs in the container: 0 or 1 for a set. (For multiset the number can be more than one.) Note that we cannot change the values directly in a set — this is not permitted: 1 set S;
2 S. insert (3);
3 *S.find (3) = 5; // the dereferenced iterator is not an lvalue

20
18

S1Consequences of uniquenessUnlike a vector the elements in a set — just like the key values in a map— are always unique.
1 vector vals;
2 for (vector :: size_type i = 0; i != 10; ++i) {
3 vals. push_back (i);
4 vals. push_back (i); // duplicates are allowed !
5 }
6 cout << vals.size (); 7 set uniqueVals (vals. begin (), vals.end ());
8 cout << uniqueVals .size (); The above has output |vals| = 20 |uniqueVals| = 10 © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 53 / 62 20 18 S1What just happened?I constructed a set using two iterators of a vector object. 7 set uniqueVals (vals. begin (), vals.end ());

This is a great example of how the STL algorithms can take
advantage of the common concepts of the containers and their
iterators: it does not matter that the originating iterators (in this
case vector::iterator come from vector at all, just that

they are iterating over some container of ints.

20
18

S1Other associate containers
Very briefly

20
18

S1multimapkey1key1key1 value1.1value1.2value1.3
key2 value2.1

key3 value3.1

key3 value3.2

(
(
(
(
(
(

)
)
)
)
)
)

The keys are no longer
unique but are kept in
order, which means
algorithms for finding and
counting can be efficiently
implemented.

20
18

S1unordered_setAn unordered set stores elements in no particular order, based on a hash
function, allowing for very fast retrieval of items if their key is known.

They are rather inefficient for range queries such as “bring me all the items
whose score is between 45 and 55”.

20
18

S1bitset1 bitset s(5); // constructs a bitset with capacity for 5 elements2 bool b = s[0]; // gets the first value in the bitsetBitsets are optimised arrays of binary values.
They provide access through the subscript operator [] to the i-th bit in
the “array” of bits.

Bitset operations:
to_ulong, to_string conversion to ulong and string;

count returns the number of 1s in the set;
size returns the number of bits in the set

test(i) returns the bool value of whether bit i is set (true);
any returns true iff any bit is set;

none returns true iff no bit is set;

20
18

S1Iterator RangesAn important concept in the STL is the idea of the iterator range: thebegin() and the end() semiopen interval mentioned before.
Knowing where you can begin, and where you end, you can do a lot:

iterate through a container
find a single element
count elements
sort elements

Now we have generic looking containers and generic ways of referring to
them. . . we can maybe think about generic algorithms to operate on them.

20
18

S1STL AlgorithmsWe will look in detail at two algorithms: find and sort.Think about the iterators we’ve come to know (and love) – they havesome simple mechanisms like “move forward” and “are these equal” and“dereference” – which are in many cases sufficient to write a whole
algorithm:

find(b, e, k)

/∗ Find item k in a container beginning at iterator position b and ending
at position just before e ∗/
2 iter ← b // iter is an iterator of the right type
3 while (iter < e) do // iterators can be compared with < 4 · if (∗iter = k) then // iterators can be dereferenced 5 · · return(iter) 6 · iter ← iter +1 // iterators can be incremented 7 return(e) © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 60 / 62 20 18 S1sortThere are two ways to invoke the sort algorithm:1 // default :2 template 3 void sort ( RandomAccessIterator first , RandomAccessIterator last );4 // custom :5 template
6 void sort ( RandomAccessIterator first , RandomAccessIterator last ,
7 Compare comp );

where first, last are iterators as we’ve seen before, and comp is a binary
function that accepts two elements in the range as arguments, and returns
a value convertible to bool.
The value returned indicates whether the element passed as first argument
is considered to go before the second in the specific strict weak ordering it
defines.
The ordering is not stable: that is, it does not guarantee that items that
are equivalent will remain in the same relative position once sorting is
complete.

20
18

S1sort (cont.)1 bool myfunction (int i,int j) { return (i myvector (myints , myints + 8); // 32 71 12 45 26 80 53 33

10
11 // using default comparison ( operator <): 12 std :: sort( myvector . begin (), myvector . begin () + 4); // (12 32 45 71)26 80 53 33 13 14 // using function as comp 15 std :: sort( myvector . begin () + 4, myvector .end (), myfunction ); // 12 32 45 71(26 33 53 80) 16 17 // using object as comp 18 std :: sort( myvector . begin (), myvector .end (), myobject ); // (12 26 32 33 45 53 71 80) 19 20 // print out content : 21 std :: cout << " myvector contains :"; 22 for (std :: vector :: iterator it = myvector . begin (); it != myvector .end ();
23 ++ it)
24 std :: cout << ' ' << *it; 25 std :: cout << '\n'; 26 } © Drinkwater, Charleston, Scholz (USyd.SIT) INFO3220: Object Oriented Design 2018 S1 62 / 62 Lecture 14: Abstracting away tight coupling Bridge Composite Proxy Lecture 15: Associative Containers and STL Algorithms Associative Containers

Related Posts