DATA STRUCTURES CSCI 1200
Popular in Course
Popular in ComputerScienence
This 128 page Class Notes was uploaded by Ransom Blanda on Monday October 19, 2015. The Class Notes belongs to CSCI 1200 at Rensselaer Polytechnic Institute taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/224865/csci-1200-rensselaer-polytechnic-institute in ComputerScienence at Rensselaer Polytechnic Institute.
Reviews for DATA STRUCTURES
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/19/15
CSCI1200 Computer Science II Spring 2006 Lecture 11 Problem Solving Part 1 Review from Lecture 10 0 Merge sort 0 Nonlinear word search Today7s Class 0 First of three lectures on problem solving 0 Today we will focus on the design and implementation of relatively short algorithms 0 Welll consider three steps or stages to solving problems 1 Generating and Evaluating Ideas 2 Mapping ldeas into Code 3 Getting the Details Right 111 Generating and Evaluating Ideas 0 Most importantly play with examples Can you develop a strategy for solving the problem You should try any strategy on several examples ls it possible to map this strategy into an algorithm and then code 0 Try solving a simpler version of the problem rst and either learn from the exercise or generalize the result 0 Does this problem look like another problem you know how to solve o If someone gave you a partial solution could you extend this to a complete solution 0 What if you split the problem in half and solved each half recursively separately 0 Does sorting the data help 0 Can you split the problem into different cases and handle each case separately 0 Can you discover something fundamental about the problem that makes it easier to solve or makes you able to solve it more ef cient y 0 Once you have an idea that you think will work you should evaluate it will it indeed work are there other ways to approach it that might be better faster if it doesn7t work why not 112 Mapping Ideas Into Code 0 How are you going to represent the data What is most ef cient and what is easiest We will expand on this discussion substantially during our 2nd lecture on problem solving 0 Can you use classes to organize the data What data should be stored and manipulated as a unit What information needs to be stored for each object What operations beyond simple accessors might be helpful 0 How can you divide the problem into units of logic that will become functions Can you reuse any code youlre previously written Will any of the logic you write now be re usable o Are you going to use recursion or iteration What information do you need to maintain during the loops or recursive calls and how is it being carried along 0 How effective is your solution ls your solution general How is the performance What is the order notation of the number of operations Can you now think of better ideas or approaches 0 Make notes for yourself about the logic of your code as you write it These will become your invariants that is what should be true at the beginning and end of each iteration recursive call 113 Getting the Details Right 0 ls everything being initialized correctly including boolean ag variables accumulation variables max min variab es 0 ls the logic of your conditionals correct Check several times and test examples by hand 0 Do you have the bounds on the loops correct Should you end at n n 7 l or n 7 2 o Tidy up your notes to formalize the invariants Study the code to make sure that your code does in fact have it right When possible use assertions to test your invariants Remember sometimes checking the invariant is impossible or too costly to be practical 0 Does it work on extreme cases eg when the answer is on the extreme end of the data when there are repeated values in the data or when the data set is very small or very large 114 Exercises Practice using these Techniques on Simple Problems 0 A perfect number is a number that is the sum of its factors The rst perfect number is 61 Lets write a program that nds all perfect numbers less than some input number n int main 39C std cout ltlt quotEnter a number quot int n stdcin gtgt 11 0 Given a sequence of n oating point numbers nd the two that are closest in value int main 39C float f while stdcin gtgt f 0 Now let s write code to remove duplicates from a sequence of numbers int main 39C int 2 while stdcin gtgt 2 1 15 Example BoxPacking o Homework 5 asks you to write a program to solve simple boxpacking problems I hope everyone has started to Generate and Evaluate Ideas 0 Instead of thinking about how to code it up7 think about how you would solve it by hand Would you just randomly try things or would you organize your strategy somehow 116 Example Merge Sort 0 ln Lecture 107 I gave you the basic framework for the merge sort algorithm and we nished the implementation of the merge helper function How did we Map Ideas Into Code 0 What invariants can we write down within the mergejort and merge functions Which invariants can we test using assertions Which ones are too expensive ire7 will affect the overall performance of the algorithm We split the vector in half recursively sort each half and merge the two sorted halves into a single sorted interval template ltclass Tgt void mergesortint low int high vectorltTgtamp values vectorltTgtamp scratch if low gt high return int mid low high 2 mergesortlow mid values scratch mergesortmid1 high values scratch mergelow mid high values scratch Nonrecursive function to merge two sorted intervals low mid amp mid1high of a vector using quotscratchquot as temporary copying space template ltclass Tgt void mergeint low int mid int high vectorltTgtamp values vectorltTgtamp scratch int ilow jmid1 klow while there s still something left in one of the sorted subintervals while i lt mid ampamp j lt high look at the top values grab the smaller one store it in the scratch vector if valuesi lt valuesjl scratchk valuesi i ese scratchk valuesj j k Copy the remainder of the interval that hasn t been exhausted for iltmid i k scratchk valuesi low interval for jlthigh j k scratchk valuesj high interval Copy from scratch back to values for ilow ilthigh i valuesi scratchi 117 Example Nonlinear Word Search 0 What did we need to think about to Get the Details Right when we nished the implementation of the nonlinear word search program What did we worry about when writing the rst draft code aka pseudo code When debugging what test cases should we be sure to try Let7s try to break the code and write down all the corner cases77 we need to test bool searchfromlocloc position const vectorltstringgtamp board const stringamp word vectorltlocgtamp path start by adding this location to the path pathpushbackposition BASE CASE if the path length matches the word length we re done if pathsize wordsize return true search all the places you can get to in one step for int i positionrow1 i lt position row1 i for int j positioncol1 lt position col1 j don t walk off the board though if i lt 0 II i gt board size continue if j lt 0 II j gt board0 size continue don t consider locations already on our path if onpathlocijpath continue if this letter matches recurse if wordpathsize boardij if we find the remaining substring we re done if searchfromloc locijboardwordpath return true We have failed to find a path from this loc remove it from the path pathpopback return false 118 Exercise Maximum Subsequence Sum 0 Problem Given is a sequence of n values a0 an1 nd the maximum value of 22 ai over all possible subsequences j k 0 For example given the integers l4 74 6 79 78 8 7316 7412 77 4 The maximum subsequence sum is 8 73 16 74 12 29 o Let7s write a rst draft of the code and then talk about how to make it more ef cient int main std vectorltintgt v int x while std cin gtgt x vpushbackx CSCI1200 Computer Science II Spring 2006 Lecture 24 C Inheritance and Polymorphism Review from Lecture 23 o csZset operations insert destroy printing erase tree height 0 Increment and decrement operations on iterators can be accomplished through use of parent pointers 0 Our tree implementation is limited because even though the averagecase behavior is Olog n for insert erase and nd operations the worstcase can be as bad as Today7s Class 0 Inheritance is a relationship among classes Examples bank accounts polygons stack amp list 0 Basic mechanisms of inheritance 0 Types of inheritance o lsA Has A AsA relationships among classes 0 Polymorphism 241 Motivating Example Bank Accounts 0 Consider different types of bank accounts 7 Savings accounts 7 Checking accounts 7 Time withdrawal accounts like savings accounts except that only the interest can be withdrawn o If you were designing C classes to represent each of these what member functions might be repeated among the different classes What member functions would be unique to a given class 0 To avoid repeating common member functions and member variables we will create a Class hierarchy where the common members are placed in a base Class and specialized members are placed in derived Classes 242 Accounts Hierarchy 0 Account is the base class of the hierarchy o SavingsAccount is a derived class from Account SavingsAccount has inherited member variables amp functions and ordinarilyde ned member variables amp functions 0 The member variable balance in base class Account is protected which means 7 balance is NOT publicly accessible outside the class but it is accessible in the derived classes 7 if balance was declared as private then SavingsAccount member functions could not access it 0 When using objects of type SavingsAccount the inherited and derived members are treated exactly the same and are not distinguishab e o CheckingAccount is also a derived class from base class Account o TimeAccount is derived from SavingsAccount SavingsAccount is its base class and Account is its indirect base 0 ass 243 Exercise Draw the Accounts Class Hierarchy include ltiostreamgt using namespace std Note we ve inlined all the functions even though some are gt 1 line of code class Account public Accountdouble bal 00 balancebal void depositdouble amt balance amt double getbalance const return balance protected double balance account balance class SavingsAccount public Account public SavingsAccountdouble bal 00 double pct 50 Accountbal ratepct1000 double compound computes and deposits interest double interest balance rate a anc interest return interest double withdrawdouble amt if overdraft gt return 0 else return amount if amt gt balance return 00 return amt protected double rate periodic interest rate class CheckingAccount public Account public CheckingAccountdouble bal 00 double lim 5000 double chg 05 Accountbal limit lim charge chg double cashcheckdouble amt assert amt gt 0 if balance lt limit ampamp amt charge lt balance balance amt charge return amt char else if balance gt limit ampamp amt lt balance balance amt return amt else return 00 protected double limit double charge y lower limit for free checking per check charge class TimeAccount public SavingsAccount public TimeAccountdouble bal 00 double pct 50 SavingsAccountbal pct fundsavail 00 redefines 2 member functions from SavingsAccount double compound double interest SavingsAccountcompound fundsavail interest return interest double withdrawdouble amt if am fundsavail fundsavail amt balance amt return amt else return 00 double getavail const return fundsavail protected double fundsavail amount available for withdrawal v 244 Constructors and Destructors o Constructors of a derived class call the base class constructor immediately before doing ANYTHING else The only thing you can control is Which constructor is called an What the arguments Will be Thus When a TimeAccount is created 3 constructors are called the Account constructor then the SavingsAccount con structor and then finally the TimeAccount constructori o The reverse is true for destructors derived class constructors do their jobs rst and then base class destructors are called at the automatically Note destructors for classes which have derived classes must be marked virtual for this chain of calls to happen 245 Overriding Member Functions in Derived Classes 0 A derived class can redefine member functions in the base class The function prototype must be identical not even the use of const can be different otherwise both functions Will be accessib e l o For example see TimeAccount compound and TimeAccount withdrawi 0 Once a function is redefined it is not possible to call the base class function unless it is explicitly called as in TimeAccount compoundi 246 Public Private and Protected Inheritance 0 Notice the line class SavingsAccount public Account This speci es that the member functions and variables from Account do not change their public protected or private status in SavingsAccounti This is called public inheritance o protected and private inheritance are other options 7 With protected inheritance public members becomes protected and other members are unchanged 7 With private inheritance all members become privatei 247 Stack Inheriting from List 0 For another example of inheritance let s reimplement the stack class as a derived class of std list template ltclass Tgt class stack private stdlistltTgt public stack 339 stackstackltTgt consth other stdlistltTgtother 339 virtual stackO 339 void pushT consth value thisgtpushbackvalue 339 void popo thisgtpopback 339 T consth top const return thisgtback 339 int size return std listltTgt sizeO bool emptyO return std listltTgt empty 339 y Private inheritance hides the std list ltTgt member functions from the outside world However these member functions are still available to the member functions of the stackltTgt class 0 Note no member variables are de ned 7 the only member variables needed are in the list class When the stack member function uses the same name as the base class list member function the name of the base class followed by must be provided to indicate that the base class member function is to be used The copy constructor just uses the copy constructor of the base class without any special designation because the stack object is a list object as well 248 IsA HasA AsA Relationships Among Classes 0 When trying to determine the relationship between hypothetical classes Cl and C2 try to think of a logical relationship between them that can be written 7 Cl is a C2 7 Cl has a C2 or 7 Cl is implemented as a C2 If writing Cl is a C2 is best for example a savings account is an account then Cl should be a derived class a subclass of C2 If writing Cl has a C2 is best for example a cylinder has a circle as its base then class Cl should have a member variable of type C2 0 In the case of Cl is implemented as a C2 for example the stack is implemented as a list then Cl should be derived from C2 but with private inheritance This is by far the least common case 249 Exercise 2D Geometric Primitives Create a class hierarchy of geometric objects such as triangle isosceles triangle right triangle quadrilateral square rhombus kite trapezoid circle ellipse etc How should this hierarchy be arranged What member variables and member functions should be in each class 2410 Note Multiple Inheritance 0 When sketching a class hierarchy for geometric objects your may have wanted to specify relationships that were more complex in particular some objects may wish to inherit from more than one base class 0 This is called multiple inheritance and can make many implementation details signi cantly more hairy Different programming languages offer different variations of multiple inheritance 2411 Introduction to Polymorphism o Let7s consider a small class hierarchy version of polygonal objects class Polygon 39C public PolygonO 339 virtual PolygonO 339 int NumVertsO return vertssize virtual double Area 0 virtual bool IsSquareO return false protected vectorltPointgt verts y class Triangle public Polygon public TrianglePoint pts3 39C for int i O i lt 3 i vertspushbackptsi 339 double Areao y class Quadrilateral public Polygon public QuadrilateralPoint pts4 fo t i O i lt 4 i vertspushbackptsi double Area ou le LongerDiagonal bool IsSquare return SidesEqual ampamp AnglesEqual private bool SidesEqual bool AnglesEqual 0 Functions that are common at least have a common interface are in Polygonl 0 Some of these functions are marked virtual which means that when they are rede ned by a derived class this new de nition will be used even for pointers to base class objects 0 Some of these virtual functions those whose declarations are followed by O are pure virtual which means they must be rede ned in a derived class 7 Any class that has pure virtual functions is called abstract 7 Objects of abstract types may not be created 7 only pointers to these objects may be created 0 Functions that are speci c to a particular object type are declared in the derived class prototype 2412 A Polymorphic List of Polygon Objects 0 Now instead of two separate lists of polygon objects we can create one polymorphic list std listltPolygongt polygons o Objects are constructed using new and inserted into the list Polygon pptr new Triangle polygons pushback pptr pptr new Quadrilateral polygons pushback pptr Triangle tptr new Triangle polygonspushback tPtr Note We7ve used the same pointer variable pptr to point to objects of two different types 2413 Accessing Objects Through a Polymorphic List of Pointers o Let7s sum the areas of all the polygons double area O for stdlistltPolygongtiterator i polygonsbegin ipolygonsend i area igtArea Which Area function is called If i points to a Triangle object then the function de ned in the Triangle class would be called If i points to a Quadrilateral object then Quadrilateral Area will be called 0 Here s code to count the number of squares in the list int count O for stdlistltPolygongtiterator i polygonsbegin ipolygonsend i count 1 gtIsSquare lf Polygon IsSquare had not been declared virtual then the function de ned in Polygon would always be called In general7 given a pointer to type T we start at T and look up the hierarchy for the closest function de nition If that function has been declared virtual7 we will look down the hierarchy stopping at the actual object type to see if the function has been rede ned in a derived class To use a function in Quadr ilat eral that is not declared in Polygon7 you must cast the pointer The pointer q will be NULL if i is not a Quadrilateral object for stdlistltPolygongtiterator i polygonsbegin ipolygonsend i Quadrilateral q dynamiccastltQuadrilateralgt i if q stdcout ltlt quotdiagonal quot ltlt qgtLongerDiagonal ltlt stdendl 2414 Exercise What is the output of the following program class Base public Base virtual void A cout ltlt IIBase Anquot void B cout ltlt IIBase Bnquot y class One public Base public OneO 339 void A cout ltlt IIOne Anquot void B cout ltlt IIOne Bnquot class Two public Base public Two 339 void A cout ltlt quotTwo Anquot void B cout ltlt quotTwo Bnquot y int main for unsigned int i0 ilt3 i ai gtA ai gtB return 0 Computer Science II 7 CSci 1200 Lecture 18 Templated Classes and Vectors Announcement 7 Two Weeks Before Thanksgiving 0 Today s lecture will cover the implementation of vectors 0 The scheduled material on operators is covered instead in a separate handout 7 You will not be tested directly on this material 7 You may nd some of it useful for HW 77 especially the input and output stream operators 7 Some material on operators will be worked into other lecture notes 7 you will be responsible for this material 0 Test 3 review material will be available on line by Friday7 November 0 Test 3 is Friday7 November 18 o Homework 7 is due Tuesday7 November 22 c There will be NO CLASS on Tuesday7 November 22 Review from Lecture 17 o Arrays and pointers 0 Different types of memory 0 Dynamic allocation of arrays Todayls Lecture 0 Designing our own container classes 0 Vectors o Templated classes 0 Copy constructors7 assignment operators and destructors 0 Implementation Designing Our Own Containers o Mimic the interface of standard library containers 0 Study the design of memory management code and iterators 0 Move toward eventually designing our own7 more sophisticated classes Vector Public Interface In creating our own version of the vector class we will start by considering the public interface public Member functions and other operators Tamp operator sizetype i const Tamp operator sizetype i const void pushbackconst Tamp t void clear bool empty const iterator erase iterator p sizetype size const void resize sizetype n public Iterator operations iterator beginO constiterator beginO const iterator end constiterator end 0 This is an excerpt from the Vec h header le handed out with these notes 0 This appears to be quite simple and in fact it is c We will focus on each piece but especially on the use of templates on the underlying representation and on memory management Templated Class Declarations and Member Function De ni tions In terms of just the layout of the code in Vec h the biggest difference is that this is a templated class 0 The keyword template and the template type name must appear be fore the class declaration as in template ltclass Tgt class Vec 0 Within the class declaration T is used as a type and all member func tions are said to be templated over type T o In the actual text of the code les templated member functions are often de ned written inside the class declaration o The templated functions de ned outside the template class declaration must be preceeded by the phrase template ltclass Tgt and then when Vec is referred to it must be VecltTgt 0 Therefore for member function create two versions we have template ltclass Tgt void VecltTgtz create Syntax and Compilation 0 Templated classes and templated member functions are not created compiled until they are needed 0 Compilation of the class declaration is triggered by a line of the form Vecltintgt v1 with int replacing T This also compiles the default constructor for Vecltintgt 7 because it is used here 0 Other member functions are not compiled unless they are used c When a different type is used with Vec for example in the declaration Vecltdoublegt z the template class declaration is compiled again this time with double replacing T instead of int Again however only the member functions used are compiled o This is very different from ordinary classes which are usually compiled separately and all functions are compiled regardless of whether or not they are needed o The code of templated classes AND the member functions must be available where they are used c As a result member functions de nitions are often included in the class declaration or attached below but still in the h le If member function de nitions are placed in a separate cpp le this le must be included just like the h le because the compiler needs to see it to generate code Member Variables Now looking inside the VecltTgt class at the member variables 0 mdata is a pointer to the start of the array after it is allocated 7 Recall the near equivalence between pointers and arrays o msize indiciates the number of locations currently in use in the vector as indicated by the size member function 0 malloc is the number of entries in the dynamically allocated block of memory the actually allocated array Drawing a picture which we will do in class will help clarify this especially the distinction between msize and malloc Typedefs Iterators and Pointers o A number of types are created through typedef statements in the rst public area of Vec 0 Once created the names are used as ordinary class type names There fore Vecltintgtz iterator is an iterator type de ned by the Vecltintgt class It is just a T 0 Also Vecltintgtz sizetype is the size type de ned here as an unsigned int 0 Thus internal to the declarations and member functions T and iterator may be used interchangeably o lmportantly the and operators on pointers automatically apply to iterators operator 0 Access to the individual locations of the string is provided through operator 7 Syntactically use of this operator is translated by the compiler into a call to a function called operator D For example if v is a Vecltintgt then vi 5 translates into voperator i 5 o In most classes there are two versions of operator 7 A non const version returns a reference to mdatai which can then be treated as either an l value and therefore modi ed or an r value 7 A const version is the one called for const str objects This also returns mdatai but as a const reference so it can not be modi ed As a result it can not be treated as an l value o The compiler automatically determines which one to use Default Versions of Assignment Operator and Copy Construc tor Are Dangerous 0 Before we write the copy constructor and the assignment operator we consider what would happen if we didn t write them 0 C compilers provide default versions of these if they are not pro vided 0 These defaults just copy the values of the member variables one by one For example the default copy constructor just like the following template ltclass Tgt VecltTgt Vec const VecltTgtamp v mdatavmdata msizevmsize mallocvmalloc In other words7 it would construct each member variable from the corresponding member variable of v o This can be dangerous7 as the following exercise illustrates Exercise Suppose we used the default version of the assignment operator and copy constructor in our VecltTgt class What would be the output of the following program Assume all of the operations except the copy constructor behave as they would with a std Vectorltintgt Vecltintgt v4 O O VO 131 v2 314 Vecltintgt uv u2 65 u3 48 for unsigned int i0 ilt4 i cout ltlt ui ltlt quot quot ltlt vi ltlt endl Explain why this happens by drawing a picture of the memory of both 11 and v Classes With Dynamically Allocated Memory 0 Each object must do its own dynamic memory allocation We must be careful to keep the memory of each object instance sepa rate from all others 0 This requires that we write very carefully our own 7 Copy constructor 7 Assignment operator 0 Dynamic memory should be released when an object is nished with it This is done through what s called a destructor Copy Constructor 0 These two functions must allocate a new array for the current object this7 copy the contents ofthe array ofthe passed object7 and adjust pointers appropriately o The assignment operator must also 7 Make sure that this is not a self assignment This is absolutely crucial 7 Delete the current array before copying o The actual copying is done in a private member function called copy Exercise Write the private member function copy Aside 1 the this pointer o All class objects have a special pointer de ned called this 0 The this pointer simply points to the class object It may not be changed 0 The expression this is a reference to the class object o The this point is used in several ways 7 Make it clear when member variables of the current object are being used 7 Check to see when an assignment is self referencing 7 Return a reference to the current object Aside 2 Assignment operators generally speaking 0 Assignment operators of the form v1 v2 are translated by the compiler as v1 operatorv2 o Cascaded assignment operators of the form v1 v2 v3 are translated by the compiler as v1 operatorv2 operatorv3 Therefore7 the value of the assignment operator v2 v3 must be suitable for input to a second assignment operator This in turn means the result of an assignment operator ought to be a reference to an object Assignment operator for Vec The implementation of an assignment operator usually takes on a very spe ci c form as illustrated for VecltTgt 0 Do real work if there is a self assignment 0 Otherwise destroy the contents of the current object then copy the passed object 0 Return a reference to the copied current object using the this pointer Destruct or o Called implicitly when an automatic object goes out of scope or a dynamic object is deleted 7 It can never be called explicitly 0 Must delete the dynamic memory owned by the class 0 The syntax of the function de nition is a bit weird 7 The quot has been used as a logic negation in other contexts Increasing the Size of the Vec pushback T constamp x o Adds to the end of the array increasing dataend by one T location 0 But wait what if msize malloc already which means the allo cated array is full 0 We need to increase the size of the array Therefore we need to H to rPPJ Allocate a new larger array The best strategy is generally to double the size of the current array If the array size was originally O doubling does nothing We must be sure that the resulting size is at least 1 Then we need to copy the contents of the current array Finally we must delete current array make the datastart pointer point to the start of the new array and adjust the other two pointers We already did something very similar to this in Lecture 17 0 Only when we are sure there is enough room in the array or we ve made enough room should we actually add the new object to the back of the array Final exercise Write the member function pushback and erase These form the rst checkpoint in lab Computer Science II i CSci 1200 Lecture 17 i Trees Part 2 Review from Lecture 16 o Binary trees and binary search trees They have a close tie to recursion 0 Tree nodes Basic tree algorithms traversals Overview of tree implementation of csZset class Implementation of begin and find We will complete the discussion of begin and find in this lecture Review in more detail cs2set class overview The classes are templated There is an auxiliary TreeNode class The only member variables of the csZset class are the root pointer and the size number of tree nodes The iterator class is declared internally and is effectively a wrapper on TreeNode pointers 7 Note that operator returns a const reference because the keys may not be changed 7 The increment and decrement operators are missing These will be discussed more later in the lecture The main public member functions just call a private and often recursive member function passing the root pointer that does all of the work Because the class stores and manages dynamically allocated memory it must provide a copy constructor an operator and a destructor in order to work correctly T0day7s Lecture csZset operations insert destroy printing erase Tree height lncrement and decrement operations on iterators Limitations of our implementation Insert Major components of the insert algorithm 0 Move left and right down the tree based on comparing keys The goal is to nd the single location to do an insert that preserves the binary search tree ordering property 0 lnserting at an empty pointer location 0 Passing pointers by reference ensures that the new node is truly inserted into the tree This is subtle but important 0 Note how the return value pair is constructed Printing There are two output methods 0 One outputs one key per line of output based on an in order traversal o The second prints the tree sideways 7 rotated counter clockwise by 90 degrees 0 This is accomplished by a reversed in order traversal while keeping track of the tree height 0 We will look at a few examples in class to get a feel for how this works Exercise Write the destroytree member function This should effectively be a post order traversal7 with a node being destroyed after its left and right subtrees are destroyed Erase o The rst step is nding the node to remove 0 Once it is found7 the actual removal is easy if the node has no children or only one child o It is harder if there are two children The trick is to 7 Find the node with the greatest value in the left subtree or the node with the smallest value in the right subtree 7 The value in this node may be safely moved into the current node because of the tree ordering 7 Then we recursively apply erase to remove that node 7 which is guaranteed to have at most one child 0 Exercise Write a recursive version of erase Height and Height Calculation Algorithm The following is not used in the csZset class7 but is an important exercise in understanding trees and recursion o The height of a node in a tree is the length of the longest path down the tree from the node to a leaf node 7 The height of a leaf is therefore 0 7 We will think of the height of a null pointer as 1 o The height of the tree is the height of the root node7 and therefore if the tree is empty the height will be 1 c We will write a simple recursive algorithm in class to calculate the height of a tree Tree Iterators Revisited o The increment operator should change the iterator s pointer to point to the next TreeNode in an in order traversal 7 the in order successor 7 while the decrement operator should change the iterator s pointer to point to the in order predecessor Unlike the situation with lists and vectors7 these predecessors and successors are not necessarily nearby either in physical memory or by following a link in the tree7 as examples we draw in class will illustrate c There are two common solution approaches 7 Each iterator maintains a list of pointers representing the path down the tree to the current node 7 Each node stores a parent pointer Only the root node has a null parent pointer We will focus on the parent pointer version of the implementation 0 Implementing this requires that the insert and erase member functions correctly adjust parent pointers 7 Handling all of the special cases involved is made easier if there is a dummy node at the root of the tree7 just as with some linked list implementations We will focus our remaining discussion on the algorithm for nding the in order suc cessor of a node 0 Although this will look expensive in the worst case for a single application of operator7 it is fairly easy to show that iterating through a tree storing n nodes requires 0n operations overall Limitations of Our BST Implementation 0 The efficiency of the main insert7 nd and erase algorithms depends on the height of the tree the height of the root 0 The best case and average case heights of a binary search tree storing n nodes are both Ologn o The worst case7 which often can happen in practice7 is We will think about what causes this 0 Developing more sophisticated algorithms to avoid the worst case behavior will be covered in Data Structures and Algorithms CSCI1200 Computer Science II Fall 2006 Lecture 11 Operators 85 iends Review from Lecture 10 0 String operations 0 Character operations 0 Word count Today7s Lecture 7 Operators and Friends 0 Review of operators as nonmember functions 0 Operators as member functions 0 Example the Complex class 0 Friend functions and classes 0 Stream operators Koening amp Moo Chapter 12 111 Review of NonMember Function Operators 0 We have already written our own operators7 especially operatorlt7 as nonmember functions We used this operator to sort objects stored in STL containers and to create our own keys for maps bool operatorlt Name constamp left Name constamp right return left lastltrightlast II leftlastrightlast ampamp left firstltrightfirst o The expression n1 lt n2 is translated by the compiler into the function call operatorlt n1 n2 0 The operator does not need to be a member function because it can access all of the information it needs through the public interface to the Name class 112 Operators As Member Functions 0 Operators can also be written as member functions The syntax is a bit different7 so we need to be careful Letls rewrite operatorlt as a member function of the Name class class Name public Namestring constamp first string constamp last firstfirst lastlast const stringamp first const return first const stringamp last const return last bool operatorlt Name constamp right const private string first string last 0 Then in the name cpp le the operator function would be de ned as bool Name operatorlt Name constamp right cons 1 return lastltrightlast I I lastrightlast ampamp firstltrightfirst And the expression n1 lt n2 is translated by the compiler into n1operatorlt n2 1 This shows that the version of operatorlt called is the member function of n17 since n1 appears on the lefthand side of the operator Observe that the function called now has only one argumentl 0 There are several important properties of the implementation of operatorlt as a member function 7 It is within the scope of class Name so private member variables can be accessed directly 7 The member variables of n1 whose member function is actually called are referenced by directly by name 7 The member variables of n2 are accessed through the parameter right 7 The member function is const which means that n1 will not and can not be changed by the function 113 Complex Numbers 7 A Brief Review 0 We use implementation of a complex number class to to explore operators in more depth showing how to make our own classes act and feel like builtin types 0 Complex numbers take the form 2 a bi where i 71 and a and b are real a is called the real part b is called the imaginary part 0 lfw cdi then 7 w2 acbdi 7 w7za7cb7di and 7 w X 2 ac7bdadbci o The magnitude of a complex number is x a2 122 114 Example Complex Class 0 The class has two private member variables to represent the real and imaginary parts There are several constructors and functions to access amp modify the data 0 Several different operators have been provided Some of these are member functions some are nonmember functions and some are special nonmember functions called friend functions 0 We will discuss the following in turn arithmetic operators assignment operators friend functions and operators as friend functions and stream operators 115 The Complex Class Declaration class Complex u Complexdouble xO double y0 Constructor with default arguments ComplexComplex constamp old Copy constructor Complexamp operator Complex constamp rhs Assignment operator double Real const return real void SetRealdouble x real x void SetImaginarydouble y imag double Magnitude const Complex operator Complex constamp rhs const as a member function Complex operator const unary operator negates a complex number Input and output stream operators can not be member functions They can be friends or they can be nonmember functions if their work can be accomplished through the public interface to the class Note that the complex object passed to the istream gtgt operator MUST be passed as a nonconst reference friend istreamamp operatorgtgt istreamamp istr Complexamp c private double real imag y ordinary nonmember operators Complex operator Complex constamp left Complex constamp right ostreamamp operatorltlt ostreamamp ostr Complex constamp c 116 Binary Arithmetic Operators o operator is de ned as a member function while operator is de ned as a nonmember function 0 Just like in the Name class this difference determines how they access the contents of the Complex objects the work on operat or accesses contents directlyl operat or accesses contents indirectly through public member functions 0 This difference also determines how the compiler calls the functions 7 z w becomes 2 operator w 7 z w becomes operator 2 w 0 Both return Complex objects so both must call Complex constructors to create these objects Calling construc tors for Complex objects inside functions especially member functions that work on Complex objects seems somewhat counterintuitive at rst but it is common practice 117 Implementation of Complex Class The values for the default arguments only appear in the class declaration Complex Complexdouble x double y realx imagy Copy constructor Complex ComplexComplex constamp old realoldreal imagoldimag Assignment operator Complexamp Complex operator Complex constamp rhs real rhsreal imag rhsimag return this Compute and return the magnitude of the complex number double Complex Magnitude const return sqrtrealreal imagimag Addition operator as a member function Complex Complex operator Complex constamp rhs const double re real rhsreal double im imag rhsimag return Complexre im Subtraction operator as a nonmember function Complex operator Complex constamp lhs Complex constamp rhs return ComplexlhsRealrhsReal lhsImaginaryrhsImaginary Unary negation operator Note that there are no arguments Complex Complex operator const return Complexreal imag Input stream operator as a friend function istreamamp operatorgtgt istream amp istr Complex amp c istr gtgt creal gtgt cimag return istr Output stream operator as an ordinary nonmember function ostreamamp operatorltlt ostream amp ostr Complex constamp c if cImaginary lt O ostr ltlt cReal ltlt quot quot ltlt cImaginary ltlt quot iquot else ostr ltlt cReal ltlt quot quot ltlt cImaginary ltlt quot iquot return ostr 118 Exercises 1 Write operator for Complex numbers as a member function of the Complex class Show the additions to Complex h and Complex cpp 2 Write operat or for Complex numbers as an ordinary function instead of as a member function of the Complex class Show the additions to Complexh and Complexcpp 119 Testing Complex Class Complex Z1 cout ltlt quotZ1 39 ltlt zl ltlt endl Complex Z2 34 cout ltlt quotZ2 quot ltlt Z2 ltlt endl Complex Z3 45 2 cout ltlt quotZ3 quot ltlt Z3 ltlt endl Complex Z4 cout ltlt quotZ4 quot ltlt Z4 ltlt endl N to v Z1 2 How does this work cout ltlt quotZ1 is now quot ltlt Z1 ltlt endl cout ltlt quotZ2 s real part is quot ltlt Z2Real ltlt quot and its imaginary part is quot ltlt Z2Imaginary ltlt endl Z2SetReal 1O Z2SetImaginary 2O cout ltlt quotZ2 is now quot ltlt Z2 ltlt endl cout ltlt quotThe magnitude of Z2 is quot ltlt Z2Magnitude ltlt endl Complex w Z2 Z4 cout ltlt quot w Z2 Z4 so w is quot ltlt w ltlt endl Complex a Z2 Z4 cout ltlt quot a Z2 Z4 so a is quot ltlt a ltlt endl Complex d cout cin cout ltlt quotnThe number input is quot ltlt d ltlt endl quotInput your own complex number as two consecutive floats quot ltlt gtgt d Complex b Z2 Z4 cout ltlt quot b Z2 Z4 so b is quot ltlt b ltlt endl Complex c Z2 Z4 cout ltlt quotoperator bc quot ltlt bc ltlt quot should be 1II ltlt endl cout ltlt quotoperato ac quot ltlt ac ltlt quot should be 0quot ltlt endl a b cout ltlt quota b a is now quot ltlt a ltlt endl w b cout ltlt quotw b w is now quot ltlt w ltlt endl 1 110 Assignment Operators o The assignment operator Z1 Z2 becomes a function call Z1operatorZ2 And cascaded assignments like Z1 Z2 Z3 are really 21 Z2 Z3 Which becomes Z1operator Z2operator Z3 Studying these helps to explain how to Write the assignment operator7 Which is usually a member function 0 The argument the right side of the operator is passed by constant reference lts values are used to change the contents of the left side of the operator7 Which is the object Whose member function is called A reference to this object is returned7 allowing a call to p Z17s p in the example above The identi er this is reserved as a pointer inside class scope to the object Whose member function is called Therefore7 this is a a reference to this object o The fact that operator returns a reference allows us to write code of the form 21 Z2 real 1 11 1 Exercise Write an operator as a member function of the Complex class To do so you must combine what you learned about operator and operator In particular the new operator must return a reference this 1112 Returning Objects vs Returning References to Objects 0 In the operator and operator functions we create new Complex objects and simply return the new object The return types of these operators are both Complex 0 Technically we don7t return the new object which is stored only locally and will disappear once the scope of the function is exited Instead we create a copy of the object and return the copy This automatic copying happens outside of the scope of the function so it is safe to access outside of the function Good compilers can minimize the amount of redundant copying without introducing semantic errors 0 When you change an existing object inside an operator and need to return that object you must return a reference to that object This is why the return types of operator and operator are both Complexamp This avoids creation of a new object o A common error made by beginners and some nonbeginners is attempting to return a reference to a locally created object This results in someone having a pointer to stale memory The pointer may behave correctly for a short while until the memory under the pointer is allocated and used by someone else 1 113 Friend Classes 0 We7re now going to shift gears slightly and discuss friend classes and functions This will lead to the third method of writing an operator Friendship is often used for closely related interdependent classes but should be used sparingly 0 In the example below the Foo class has designated the Bar to be a friend This must be done in the public area of the declaration of Foo class Foo public friend class Bar This allows member functions in class Bar to access the private member functions and variables of a Foo object as though they were public but not vice versa 0 Note that Foo is giving friendship access to its private contents rather than Bar claiming it What could go wrong if we allowed friendships to be claimed 1114 Friend Functions 0 Within the de nition of the class we can designate speci c functions to be friend77s which grants these functions access similar to that of a member function 0 Within the scope of the de nition of these friend functions private member functions and variables of Foo objects can be accessed directly as though they were public 0 The most common example of this is operators and especially stream operators 1115 Friend Operators o Letls rewrite operat or as a friend function First the declaration is moved from outside the class declaration to inside it and the keyword friend is added to the front friend Complex operator Complex constamp lhs Complex constamp rhs 0 Now that it is a friend it can access private member variables directly just as though it were within class scope The operator de nition inside Complex cpp becomes Complex operator Complex constamp lhs Complex constamp rhs return Complexlhs real rhs real lhsimag rhs imag 1 116 Stream Operators o The operators gtgt and ltlt are de ned for the Complex class These are binary operators A notation like cout ltlt 23 is really operatorltlt cout 23 Recall that the consecutive calls to the ltlt operator such as cout ltlt quot23 quot ltlt 23 ltlt endl are really cout ltlt quot23 quot ltlt 23 ltlt endl Each application of the operator returns an ostream object so that the next application can occur 0 If we wanted to make this function a member function it would have to be a member function of the ostream class because this is the rst argument We cannot make it a member function of the Complex class This is why stream operators are never member functions 0 Stream operators are either ordinary nonmember functions if the operators can do their work through the public class interface or friend functions if they need non public access Welve written one stream operator as a friend and one as an ordinary nonmember function for the Complex class 1117 Summary of Operator Overloading 0 Many operators can be overloaded including operators we havenlt discussed such as operator operator operator operator Yes we can even overload the function call operator In fact we can overload 42 different operators There are only 5 operators that can not be overloaded The most important syntactic rule is that overloading can never change the number of arguments or the form of an operator The only exception to this is the function call operator which already has a variable number of arguments 0 There are three different ways to overload an operator 7 Nonmember function 7 Member function 7 Friend function When there is a choice skilled programmers may disagree about which of the above is preferred In this class we recommend trying to write operators as a nonmember rst then member then friend 0 The most important rule for clean class design involving operators is to NEVER Change the intuitive meaning of an operator The whole point of operators is lost if you do One bad example would be de ning the increment operator on a Complex number 1 118 Extra Practice 0 Implement the following operators for the Complex class or explain why they cannot or should not be imple mented Think about whether they should be nonmember member or frien negation operator operator operatorlt CSCI1200 Computer Science II Fall 2008 Lecture 4 Classes II Sort Nonmember Operators Review from Lecture 3 0 C classes member variables and member functions class scope public and private 0 Nuances to remember 7 Within class scope within the code of a member function member variables and member functions of that class may be accessed without providing the name of the class object 7 Within a member function when an object of the same class type has been passed as an argument direct access to the private member variables of that object is allowed using the 7 7 notationi 0 Classes vsi structs 0 Designing classes Today7s Lecture 0 Extended example of student grading program 0 Passing comparison functions to sort 0 Nonmember operators 41 Example Student Grades Our goal is to write a program that calculates the grades for students in a class and outputs the students and their averages in alphabetical order The program source code is broken into three parts 0 Re use of statistics code that we wrote in Lecture 2 0 Class Student to record information about each student including name and grades and to calculate averagesi o The main function controls the overall ow including input calculation of grades and output File mainstudentcpp Purpose Compute student averages and output them alphabetically include ltalgorithmgt include ltfstreamgt include ltiomanipgt include ltiostreamgt include ltvectorgt include quotstudent hquot unsigned int maxunsigned int x unsigned int y I return xgty x y int mainint argc char argv I if argc 3 std cerr ltlt IIUsage n quot ltlt argvO ltlt quot infilestudents outfilegradesnquot return 1 stdifstream instrargv1 if instr I std cerr ltlt quotCould not open quot ltlt argv1 ltlt quot to readnquot return 1 stdofstream outstrargv2 if outstr I std cerr ltlt quotCould not open quot ltlt argv2 ltlt quot to writenquot return 1 int numhomeworks numtests double hwweight instr gtgt numhomeworks gtgt numtests gtgt hwweight std vectorltStudentgt students Student onestudent Read the students one at a time whileonestudentreadinstr numhomeworks numtests 39C students pushback onestudent Compute the averages At the same time determine the maximum name length unsigned int i unsigned int maxlength O for i0 iltstudentssize i 39C studentsi computeaverageshwweight maxlength max maxlength studentsi firstname size studentsi lastname sizeo maxlength 2 account for the output padding with quot Sort the students alphabetically by name std sortstudents begino studentsend lessnames Output a header outstr ltlt quotnIIere are the student semester averagesnquot const stdstring header quotNamequot stdstringmaxlength4 7 quot const std string underlineheadersize 7quot outstr ltlt header ltlt n ltlt underline ltlt std endl HW Test Finalquot Output the students for i0 iltstudentssize i 39C unsigned int length studentsi lastnamesize studentsi firstname size 2 studentsi outputnameoutstr outstr ltlt stdstringmaxlength length 7 7 ltlt quot quot studentsi outputaveragesoutstr return 0 everything fine 42 Declaration of Class Student 0 Stores names7 id numbers7 scores and averages The scores are stored using a vectorl Member variables of a class can be other classesl Functionality is relatively simple input7 compute average7 provide access to names and averages7 and output No constructor is explicitly provided Student objects are built through the read function Overall7 the Student class design differs substantially in style from the Date class design We Will see different styles of class designs throughout the semester Note the helpful convention used in this example all member variable names end With the character The special preprocessor directives ifndef studentnh7 def ine studenth7 and endif ensure that this les is included at most once per cpp le File student h Purpose Header for declaration of student record class and associated functions ifndef studenth define studenth include ltiostreamgt include ltstringgt include ltvectorgt class Student public ACCESSORS const stdstringamp firstname const return firstname const stdstringamp lastname const return lastname const stdstringamp idnumber const return idnumber double hwavg const return hwavg double testavg const return testavg double finalavg const return finalavg bool readstdistreamamp instr unsigned int numhomeworks unsigned int numtests void computeaveragesdouble hwweigh st ostream utputnamestdostreamamp outstr const stdostreamamp outputaveragesstdostreamamp outstr const private REPRESENTATION std string firstname stdstring lastname stdstring idnumber stdvectorltintgt hwscores double hwav stdvectorltintgt testscores double te tavg double finalavg y bool lessnamesconst Studentamp stu1 const Studentamp stu2 endif 43 Automatic Creation of Two Constructors By the Compiler 0 Two constructors are created automatically by the compiler because they are needed and used 0 The rst is a default constructor which has no arguments and just calls the default constructor for each of the member variables The prototype is Student The default constructor is called when the main function line Student onestudent is executed If you wish a different behavior for the default constructor you must declare it in the h le and provide the alternate implementation 0 The second automaticallycreated constructor is a copy constructor whose only argument is a const reference to a Student object The prototype is Student const Student ampS This constructor calls the copy constructor for each member variable to copy the member variables from the passed Student object to the corresponding member variables of the Student object being created If you wish a different behavior for the copy constructor you must declare it an provide the alternate implementation The copy constructor is called during the vector pushback function in copying the contents of onestudent to a new Student object on the back of the vector students 0 The behavior of automaticallycreated default and copy constructors is often but not always what s desired When they do what s desired the convention is to not write them explicitly 0 Later in the semester we will see circumstances where writing our own default and copy constructors is crucial 44 Implementation of Class Student 0 The read function is fairly sophisticated and depends heavily on the expected structure of the input data It also has a lot of error checking 7 In many class designs this type of input would be done by functions outside the class With the results passed into a constructor We generally prefer this style because it separates elegant class design from clunky lO details The accessor functions for the names are de ned Within the class declaration in the header le In this course you are allowed to do this for oneline functions only For complex classes including long definitions Within the header le has dependency and performance implications 0 The computation of the averages uses some but not all of the functionality from stats h and stats cpp not included in your handout 0 Output is split across two functions Again stylistically it is sometimes preferable to do this outside the class 0 We Will discuss the nonmember function lessnames later in this lecture File studentcpp Purpose Implementation of the class Student include ltiostreamgt include quotstudenthquot include quotstddevhquot Read information about a student returning true if the information was read correctly bool Studentreadstdistreamamp instr unsigned int numhomeworks unsigned int numtests If we don t find an id we ve reached the end of the file amp silently return false if instr gtgt idnumber return false Once we have an id number any other failure in reading is treated as an error read the name if instr gtgt firstname gtgt lastname std cerr ltlt IIFailed reading name for student quot ltlt idnumber ltlt std endl return false unsigned int i int score Read the homework scores hwscoresclear for i0 iltnumhomeworks ampamp instr gtgt score i hwscorespushbackscore if hwscoressize numhomeworks std cerr ltlt quotPremature end of file or invalid input reading quot ltlt IIhw scores for quot ltlt idnumber ltlt std endl return false Read the test scores testscoresclear for i0 iltnumtests ampamp instr gtgt score i testscorespushbackscore if testscoressize numtests std cout ltlt quotPremature end of file or invalid input reading quot ltlt IItest scores forquot ltlt idnumber ltlt std endl return false return true everything was fine Compute and store the hw test and final average for the student void Student computeaveragesdouble hwweight double dummystddev avgandstddevhwscores hwavg dummystddev avgandstddevtestscores testavg dummystddev finalavg hwweight hwavg 1 hwweight testavg 339 std ostreamamp Studentoutputnamestdostreamamp outstr const outstr ltlt lastname ltlt quot quot ltlt firstname return outstr std ostreamamp Studentoutputaveragesstdostreamamp outstr const outstr ltlt std fixed ltlt std setprecision1 outstr ltlt hwavg ltlt quot quot ltlt testavg ltlt quot return outstr quot ltlt finalavg ltlt std endl Boolean function to define alphabetical ordering of names The vector sort function requires that the objects be passed by CONSTANT REFERENCE bool lessnamesconst Studentamp stu1 const Studentamp stu2 return stu1lastname lt stu2lastname II stu1lastname stu2lastname ampamp stu1firstname lt stu2firstname 45 New C in the main function 7 manipulating strings o The following statement creates a constant string by adding concatenating existing strings const string header quotNamequot stringmaxlength4 7 quot HW Test Finar39 o The expression stringmaxlength4 within this statement creates a temporary string but does not associate it with a variable 0 This is done again during the output of each individual student to create an evenly spaced table 46 Exercise Add code to the end of the main function to compute and output the average of the semester grades and to output a list of the semester grades sorted into increasing order 47 Providing Comparison Functions to Sort Consider sorting the students vector o If we used sortstudentsbegin studentsend the sort function would try to use the lt operator on student objects to sort the students7 just as it earlier used the lt operator on doubles to sort the grades However7 this doesnlt work because there is no such operator on Student objects 0 Fortunately7 the sort function can be called with a third argument7 a comparison function sort students begin students end lessmames lessnames7 de ned in student cpp7 is a function that takes two const references to Student objects and returns true if and only if the rst argument should be considered less than the second in the sorted order lessnames uses the lt operator de ned on string objects to determine its ordering 48 Exercise Write a function greateraverages that could be used in place of lessnames to sort the students vector so that the student with the highest semester average is rst 49 Operators As NonMember Functions 0 A second option for sorting is to de ne a function that creates a lt operator for Student objects At rst this seems a bit weird but it is extremely use o Lets start with syntax The expressions a lt b and x y are really function calls Syntactically they are equivalent to operatorlt a b and operator x y respectively 0 When we want to write our own operators we write them as functions with these weird names 0 For example if we write bool operatorlt const Studentamp stu1 const Studentamp stu2 return stu1lastname lt stu2 lastname I stu1lastname stu2 lastname ampamp stu1firstname lt stu2 firstname then the statement sort studentsbegin studentsend will sort Student objects into alphabetical order 0 Really the only weird thing about operators is their syntax 0 We will have many opportunities to write operators throughout this course Sometimes these will be made class member functions but that comes later 410 A Word of Caution about Operators o Operators should only be de ned if their meaning is intuitively clear 0 operatorlt on Student objects fails the test because the natural ordering on these objects is not clear 0 By contrast operatorlt on Date objects is much more natural and clear 411 Exercise Write an operatorlt for comparing two Date objects 412 Another Class Example Alphabetizing Names namemain cpp Demonstrates another example with the use of classes including an output stream operator include ltalgorithmgt include IIname hquot int main std vectorltNamegt names std string first last std cout ltltquotnEnter a sequence of names first and last and this program will alphabetize themnquot while std cin gtgt first gtgt last names pushbackNamefirst last std sortnames begin namesend std cout ltlt IInHere are the names in alphabetical ordernquot for int i O i lt names size i std cout ltlt namesi ltlt quotnquot return 0 413 Name Class Declaration amp Implementation nameh include ltiostreamgt include ltstringgt class Name public CONSTRUCTOR Nameconst std stringamp fst const std stringamp lst ACCESSORS Providing a const reference to the string allows the string to be examined and treated as an rvalue without the cost of copying it const std stringamp first const return first const std stringamp last const return last MODIFIERS void setfirstconst std string amp fst first fst void setlastconst std stringamp 1st last lst private REPRESENTATION std string first last operatorlt to allow sorting bool operatorlt const Nameamp left const Nameamp right operatorltlt to allow output std ostreamamp operatorltlt stdostreamamp ostr const Nameamp n namec include quotnamehquot Here we use special syntax to call the string class copy constructors instead of calling the default constructor and then performing an assignment in the body of the constructor function NameNameconst stdstringamp fst const std stringamp lst firstfst lastlst Name Nameconst stdstringamp fst const std stringamp 1st H fh f last lst operatorlt bool operatorlt const Nameamp left const Nameamp right return leftlastltrightlast II leftlastrightlast ampamp leftfirstltrightfirst operatorltlt is the output stream operator It takes two arguments the stream such as cout and the object to be output The ltlt operator should always a reference to the output stream to allow a sequence of outputs in a single statement std ostreamamp operatorltlt stdostreamamp ostr const Nameamp n ostr ltlt nfirst ltlt quot quot ltlt nlast return ostr CSCI1200 Computer Science II Spring 2006 Lecture 17 Pointers Dynamic Memory and CommandLine Arguments Review from Lecture 16 o Pointer variables arrays character arrays and pointers as array iterators Today7s Lecture 7 Pointers and Dynamic Memory 0 K amp M rest of Chapter 10 Malik 753 781 0 Arrays and pointers different types of memory and dynamic allocation of arrays 171 Three Types of Memory 0 Automatic memory memory allocation inside a function when you create a variable This allocates space for local variables in functions and deallocates it when variables go out of scope For example int x double y 0 Static memory variables allocated statically with the keyword static They are are not eliminated when they go out of scope They retain their values but are only accessible within the scope where they are de ned We will not be discussing these much static int counter 0 Dynamic memory explicitly allocated as needed This is the focus of today7s lecture 17 2 Dynamic Memory 0 Dynamic memory is 7 created using the new operator accessed through pointers and removed through the delete operator 0 Here7s a simple example involving dynamic allocation of integers int p new int p 17 cout ltlt p ltlt endl int q q new int q P p 27 cout ltlt p ltlt quot quot ltlt q ltlt endl int temp q q P P temp cout ltlt p ltlt quot quot ltlt q ltlt endl delete p delete q o The expression new int asks the system for a new chunk of memory that is large enough to hold an integer Therefore the statement int p new int allocates a new chunk of memory large enough to hold an integer and stores the memory address of the start of this memory in the pointer variable p o The statement delete p takes the integer memory pointed by p and returns it to the system for re use 0 In between the new and delete statements the memory is treated just like memory for an ordinary variable except the only way to access it is through pointers Hence the manipulation of pointer variables and values is similar to the examples covered in Lecture 16 except that there is no explicitly named variable other than the pointer variable 0 Dynamic allocation of primitives like ints and doubles is not very interesting or signi cant What7s more important is dynamic allocation of arrays and objects 173 Exercise 0 Whats the output of the following code Be sure to draw a picture to help you gure it out double p new double 351 double q p cout ltlt p ltlt quot quot ltlt q ltlt endl p new double p 271 cout ltlt p ltlt quot quot ltlt q ltlt endl q 125 cout ltlt p ltlt quot quot ltlt q ltlt endl delete p delete q 174 Dynamic Allocation of Arrays o Declaring the size of an array at compile time doesn7t offer much exibility Instead we can dynamically allocate an array based on data This gets us part way toward the behavior of a vector Here7s an example int main cout ltlt quotEnter the size of the array quot int n cin gtgt n double a new double n 1 int i for i0 iltn i ai sqrt i for i0 iltn i if doubleintai ai cout ltlt 1 ltlt quot is a perfect square quot ltlt endl delete a return 0 l 0 Consider the line double a new double n i The expression new double n asks the system to dynamically allocate enough consec utive memory to hold 71 doubles usually 871 bytes What7s crucially important is that n is a variable Therefore its value and as a result the size of the array are not known until the program is executed When this happens the memory must be allocated dynamically The address of the start of the allocated memory is assigned to the pointer variable a 0 After this7 a is treated as though it is an array For example ai sqrt i ln fact7 the expression ai is exactly equivalent to the pointer arithmetic and dereferencing expression ai which we have seen several times before 0 After we are done using the array7 the line delete a releases the memory allocated for the entire array Without the l7 only the rst double would be released 0 Since the program is ending7 releasing the memory is not a major concern In more substan tial programs it is ABSOLUTELY CRUCIAL If we forget to release memory repeatedly the program can be said to have a memory leak Long running programs with memory leaks will eventually run out of memory and crash 175 Exercises 1 Write code to dynamically allocate an array of n integers7 point to this array using the integer pointer variable a7 and then read 71 values into the array from the stream Cin 2 Now7 suppose we wanted to write code to double the size of array a without losing the values This requires some work First allocate an array of size 2n7 pointed to by integer pointer variable temp which will become a Then copy the n values of a into the rst 11 locations of array temp Finally delete array a and assign temp to a Why dont you need to delete temp Note The code for part 2 of the exercise is very similar to what happens inside the resize member function of vectors 176 Dynamic Allocation Arrays of Class Objects 0 We can dynamically allocate arrays of structs and class objects include ltiostreamgt class Foo public F000 static int counter 1 a counter 1000 counter double value const return ab private long long int a double b int main int n gtgt n things Foo i new Foo n things i lt thingsn i cout ltlt IIFoo stored at quot ltlt inti ltlt quot has value quot ltlt igtvalue ltlt endl delete things For class objects7 the default constructor the constructor that takes no arguments must be de ned Vectors do not require default constructors 7 another advantage of vectors over arrays 177 Dynamic Allocation Example The Sieve of Eratosthenes Revisited 0 We return to the problem of nding all primes The rst time we did this we used a list Now we use a dynamically allocated array Using Sieve of Eratostenes determine all prime numbersless than or equal to an integer provided on the command line include ltiostreamgt include lt mathgt include ltcstdlibgt using namespace std int mainint argc char argv Check usage Take n from the 1st argument Make sure it is positive if argc 2 cerr ltlt IIUsage n quot ltlt argv0 ltlt quot nnquot ltlt IIwhere n is a positive integernquot return 0 int n atoiargv1 if n lt 0 cerr ltlt IIUsage n quot ltlt argv0 ltlt quot nnquot ltlt IIwhere n is a positive integernquot return Create and initialize a dynamically allocated array bool isprimesieve isprimesieve new booln1 int i isprimesieveO isprimesieve false for i2 iltn i isprimesievei true Check each integer up to n to see if it is prime Output those that are int primecount O for i 2 i lt n i If a number is not prime then we can skip it if isprimesievei cout ltlt 1 ltlt quot is primenquot primecount No multiples of i are prime Mark these multiples in the array for int j 21 j lt n j 1 isprimesievej false cout ltlt quotnThere are quot ltlt primecount ltlt quot primes lt quot ltlt n ltlt endl Release the dynamic memory through the delete operator delete isprimesieve return 0 0 Once n is taken from the command line7 we de ne a bool pointer and then make it point to the start of a dynamically allocated array of bools Each entry from 0 to n is used to indicate whether or not the index value is prime 0 After this7 islprimelsieve is treated like an ordinary array 0 The dynamic memory is deleted at the end 178 Exercise Dynamic Allocation Arrays vs Vectors o Rewrite the previous example using vectors instead of arrays Computer Science II 7 CSci 1200 Lecture 20 Hash Table Implementation Review from Lecture 19 0 Summary of data structures we have studied thus far 0 Stacks and queues7 a quick introduction 0 Hashing 7 Idea 7 Hash functions 7 Hash tables 7 Collision resolution T0day7s Class 0 We will complete our discussion of collision resolution 0 Using a hash table to implement a set 7 Function objects 7 Overall design 7 lterators 7 Fundamental operations nd7 insert and erase A Set As a Hash Table 0 The class is templated over both the key type and the hash function type template lt typename KeyType typename HashFunc gt class hashset We will discuss the mechanism for templating over a hash function below 0 We use separate chaining for collision resolution Hence the main data structure inside the class is std vectorlt std listltKeyTypegt gt mtable c We will use automatic resizing to handle the possibility that our table is too full 7 This resize is to the L that occurs inside the vector pushback function rather than the explicit resize function call Function Objects 0 Our hash function is implemented as an object with a function call operator 0 The basic form of the function call operator is class name public returntype operator args 1 where any speci c number of arguments can be used 0 Here is an example of a templated function object implementing the less than com parison operation template lttypename Tgt class lessthan public 1 bool operator const Tamp x const Tamp y return xlty This is the default 3rd argument to std sort 0 Constructors of functions objects can be used to specify parameters for use in com parisons For example class betweenvalues private int x y public betweenvalues int inx int iny xinx yiny bool operator int 2 return x lt 2 ampamp 2 lt y l This can be used in combination with findif For example if v is a vector of integers7 then betweenvalues lowrange 99 99 if stdfindif vbegin vend lowrange vend stdcout ltlt quotA value between 99 and 99 is in the vectornquot Our Hash Function Object class hashstringobj public unsigned int operator stdstring constamp key const This implementation comes from httpwwwpartownetprogramminghashfunctions unsigned int hash 1315423911 forunsigned int i O i lt keylength i hash quot hash ltlt 5 keyi hash gtgt 2 return hash The type hashstringobj is one of the template parameters to the declaration of a hashset typedef hashsetltstd string hashstringobjgt hashsettype It erat 0139s 0 lterators move through the hash table in the order the values are stored rather than the ordering imposed by say an operatorlt The order depends on the hash function and the table size 7 Hence the increment operators must move to the next entry in the current list or7 if the end of the current list is reached7 to the rst entry in the next non empty list 0 The declaration is nested inside the hashset declaration in order to avoid explicitly templating the iterator over the hash function type c The iterator must store a pointer to the hash table it is associated with 7 This re ects a subtle point about types even though the iterator class is declared inside the hashset this does not mean an iterator automatically knows about any particular hashset o The iterator must also store 7 The index of the current list in the hash table 7 An iterator referencing the current location in the current list 0 Because of the way the classes are nested7 the iterator class object must declare the hashset class as a friend7 but the reverse is unnecessary begin and end 0 They are member functions of the hashset class7 but they create iterator objects 0 begin 7 It must nd the rst key in the table7 perhaps skipping over empty lists 7 It must tie the iterator being created to the particular hashset object it is applied to This is done by passing the this pointer to the iterator constructor 0 end 7 Associates the table with the iterator as well 7 Assigns an index of 1 7 Does not assign the particular list iterator 0 Exercise Implement the begin function Iterator Operators o The increment operators must nd the next key either in the current list or in the next non empty list 0 The decrement operator must check if the iterator in the list is at the beginning and if so it must proceed to nd the previous non empty list and then nd the last entry in that list 7 While this sounds expensive remember that the lists should be very short 0 The comparison operators must accommodate the fact that when at least one of the iterators is the end the internal list iterator will not have a useful value Now we turn to the main functions of the hashset Insert 0 Computes the hash function value and then the index location o If the key is already in the list that is at the index location then no changes are made to the set but 7 an iterator is created referencing the location of the key 7 a pair is returned with this iterator and false o If the key is not in the list at the index location then the list should be inserted in the list at the front is ne and 7 an iterator is created referencing the location of the newly inserted key 7 a pair is returned with this iterator and true 0 Exercise Implement the insert function ignoring for now the resize Find 0 This is similar to insert and requires computation of the hash function and the index following by a std find operation Erase 0 Two versions are implemented one based on a key value and one based on an iterator 0 These are based on nding the appropriate iterator location in the appropriate list and applying the list erase function Resize 0 Must copy the contents of the current vector into a scratch vector 0 The current vector must be resized 0 Each key must then be inserted into resized vector 0 Exercise Write resize Iterators and Changes to the Hash Set 0 Any insert operation invalidates all hashset iterators because the insert operation could cause a resize of the table 0 The erase function only invalidates an iterator that references the current object Summary 0 The algorithmic steps are not particularly difficult o The use of C is more sophisticated than recent examples 0 The standard library is exploited to simplify the implementation 0 This imposes some hidden costs in the implementation the most substantial being in resize where 7 lists are copied and then reallocated7 and 7 hash function values are recomputed CSCI1200 Computer Science II Spring 2006 Lecture 14 Associative Containers Maps Part 2 Review of Lecture 13 0 Maps are associations between keys and values 0 Maps have fast insert access and remove operations 0 Maps store pairs map iterators refer to these pairs 0 The primary map member functions we discussed are operator 1 find insert and erase o The choice between maps vectors and lists is based on naturalness ease of programming and ef ciency of the resulting program Today7s Class 7 Maps Part 2 0 Maps containing more complicated values 0 Example index mapping words to the text line numbers on which they appear 0 Maps whose keys are class objects 0 Example maintaining student records 0 Summary discussion of when to use maps 141 More Complicated Values ma Quin vectorltintgtgt m o Letls look at the example p g 1 mapltstring vectorltintgt gt m l mapltstring vectorltintgt gt iterator p Note that the space between the gt gt is required Otherw1se gtgt 1s treated as an operator p4 quothelloquot 0 Here s the syntax for entering the number 5 in the vector associated with the string quothelloquot mstringquothelloquot pushback 5 1 Here s the syntax for accessing the size of the vector stored in the map pair referred to by map iterator p l p m findstringquothelloquot pgtsecondsize Now if you want to access and change the ith entry in this vector you can either using subscripting p gtsecondi 15 the parentheses are needed because of precedence or you can use vector iterators vectorltintgt iterator q pgtsecondbegin i q 15 Both of these of course assume that at least i1 integers have been stored in the vector either through the use of push1back or through construction of the vector We can gure out the correct syntax for all of these by drawing pictures to Visualize the contents of the map and the pairs stored in the map We will do this during lecture and you should do so all the time in practice 142 Exercise Write code to count the odd numbers stored in the map mapltstring vectorltintgt gt m This Will require testing all contents of each vector in the map Try Writing the code using subscripting on the vectors and then again using vector iteratorsl 143 A Word Index in a Text File Given a text file generate an alphabetical listing of the words in the file and the file line numbers on which each word appears If a word appears on a line more than once the line number is listed only once A map of strings to vectors stores the information include ltalgorithmgt include ltcctypegt include ltiostreamgt include gt include ltstringgt include ltvectorgt using namespace std A E m vectorltstringgt breakupv2const stringamp line int main mapltstring vectorltintgt gt wordstolines string line int linenumber 0 while getlinecin line li enumber Break the string up into words vectorltstringgt words breakupv2line Find if each word is already in the map for vectorltstringgt iterator p wordsbegin p wordsend p If not create a new entry with an empty vector default add to index to the end of the vector mapltstring vectorltintgt gt iterator mapitr if mapitr wordstolinesend and wordstolinesfindp wordstolinesppushbacklinenumber could use insert here If it is check the last entry to see if the line numbe already there If not add it to the back of the vector else if mapitrgtsecondback linenumber mapitrgtsecondpushbacklinenumber Output each word on a single line followed by the line numbers mapltstring vectorltintgt gt iterator mapitr for mapitr wordstolinesbegin mapitr wordstolinesend mapitr cout ltlt mapitrgtfirst ltlt quot tquot for unsigned int i O i lt mapitrgtsecondsize i cout ltlt mapitrgtsecond i ltlt quotquot cout ltlt quotnquot return 0 this breaks up a line into a vector of alphabeticcharonly strings vectorltstringgt breakupv2const stringamp line vectorltstringgt strings string constiterator p linebegin string oneword while p lineend Find the beginning of the next alphabetic string while p lineend ampamp isalphap p If haven t reached the end of the line if p lineend Restart the word with p oneword quotquot oneword tolowerp Add remaining letters for p p lineend ampamp isalphap p oneword tolowerp Add word to the vector of strings stringspushbackoneword return strings 144 Our Own Class as the Map Key 0 So far we have used string mostly and int once as the key in building a map lntuitively it would seem that string is used quite commonlyi o More generally we can use any class we want as long as it has an operatorlt de ned on it For example consider class Name public Nameconst stringamp first const stringamp last mfirstfirst mlastlast const stringamp first const return mfirst const stringamp last const return mlast private string mfirst string mlast 0 Suppose we wanted a map of names and associated student records where the student record class stores things like address courses grades and tuition fees and calculates things like GPAs credits and remaining required courses To make this work we need to add an operatorlt This is simple bool operatorlt const Nameamp left const Nameamp right return leftlast lt rightlast II left last rightlast ampamp leftfirst lt right first Now you can de ne a map mapltName StudentRecordgt students 0 Of course you would still need to write the StudentRecord classl 0 Also some older compilers require the de nition of operatorquot as well so be alert to this 145 Typedefs 0 One of the painful aspects of using maps is the syntax For example7 consider a constant iterator in a map associating strings and vectors of ints maplt string vectorltintgt gt constiterator p o Typedefs are a syntactic means of shortening this For example7 if you place the line typedef maplt string vectorltintgt gt mapvect before your main function and any function prototypes7 then anywhere you want the map you can just use the identi er mapvect mapvect constiterator p The compiler makes the substitution for your 146 An Additional Example Organizing MP37s o Letls store information about the MP3 les stored on various computers in a network7 o Welll need to dynamically update this information as computers are added to and removed from the network 0 Weld like to nd songs and the fastest connection for downloading themi o The solution stores the information in a map7 With a unique identi er for each computer forming the key and a class object that maintains information about a computer and its MP3s as the value h mp3h ifndef mp3h define mp3h An MP3 representation include ltstringgt using namespace std class MP3 ublic MP3 339 MP3const stringamp artist const stringamp title artistartist titletitle const stringamp getartist const return artist const stringamp gettitle const return title private string artist string title endif Computerh ifndef computerh define computerh Each computer has the capability of adding an MP3 file printing its MP3 files determining if a song MP3 is on the computer or finding the songs by a given artist include ltlistgt include ltstringgt include IImp3 hquot class Computer public Computerdouble speed speedspeed bool addmp3const stringamp artist const stringamp title void printmp3s const bool hassongconst stringamp artist const stringamp title MP3amp requestedsong const listltMP3gt songsbyartistconst stringamp artist const double getSpeed const return speed private double speed network connection speed in bytes per second listltMP3gt mp3s the songs on the computer could be a vector just as easily endif Conunnencpp include ltiostreamgt include quotcomputerhquot Add an MP3 to the list of MP3s Return false if the song is already there bool Computeraddmp3const stringamp artist const stringamp title listltMP3gtiterator p for p mp3sbegin p mp3send p if pgtgetartist artist ampamp p gtgettitle title break if p mp3send return false else mp3spushbackMP3artist title return true Iterate through the list of MP3 printing each void Computer rintmp3s const forlistltMP3gtconstiterator p mp3sbegin p mp3send p cout ltlt quot ARTIST quot ltlt pgtgetartist ltlt endl ltlt quot TITLE quot ltlt pgtgettitle ltlt endl Returns true if the Computer has the requested song returns reference to song via parameter bool Computer hassongconst stringamp artist const stringamp title MP3amp requestedsong const for listltMP3gt constiterator p mp3sbegin p mp3send p if pgtgetartist artist ampamp pgtgettitle title requestedsong p return true return false Build a list of all songs by the indicated artist listltMP3gt Computer songsbyartistconst stringamp artist const listltMP3gt results forlistltMP3gtconstiterator p mp3sbegin p mp3send p 4 pgtgetartist artist resultspushbackp return results maincpp This program processes queries about the MP3 files available on various computers Each computer is identified by a unique id a string Information about the computer including connection speed and a list of MPS s are stored in the computer class object include ltalgorithmgt include ltiostreamgt include quotmp3hquot include quotcomputerhquot typedef mapltstring Computergt MP3map since the names of maps tend to be rather long void addcomputerMP3mapamp mp3system prototypes of helper functions void printmp3soncomputerconst MP3mapamp mp3syste void findsongconst MP3mapamp mp3system void findsongsbyartistconst MP3mapamp mp3system int main the mp3 database MP3map mp3system bool quit false process the input char option while cin gtgt option switch option case 7 addcomputermp3system break case p printmp3soncomputermp3system break case f findsongmp3system break case F findsongsbyartistmp3system break case q return 1 break quotError quot ltlt option ltlt quot is not a valid commandquot ltlt endl Add a computer to the map of MP3 s void addcomputerMP3mapamp mp3system string computerid line double speed read id amp speed cin gtgt computerid gtgt speed getlinecin line read the rest of that line Create a new computer amp read its MP3 s Computer newcomputerspeed do string artisttitle getlinecin artist if artist quotquot break getlinecin title newcomputeraddmp3artist title while true Try to add the computer using the map insert function pairltMP3mapiterator boolgt resultpair make sure the computer assertresultpairseco d mp3systeminsertmakepaircomputerid newcomputer isn t already there cout ltlt IIComputer quot ltlt computerid ltlt quot addedquot ltlt endl Print the MP3 s for a given computer void printmp3soncomputerconst MP3mapamp mp3system string computerid line read id cin gtgt computerid getlinecin line Find the computer MP3map constiterator citr mp3systemfindcomputerid if citr mp3systemend cout ltlt IIComputer quot ltlt computerid ltlt quot is not in the systemquot ltlt endl else cout ltlt IISongs found on quot ltlt computerid ltlt IInquot citrgtsecondprintmp3s Find all computers with a particular song void findsongconst MP3mapamp mp3system string line artist title getlinecin line read the rest of request line get the artist amp title getlinecin artist getlinecin title Iterate through the map looking for the song bool found false string computerid double speed MP3map constiterator citr for citr mp3systembegin citr mp3systemend citr MP3 request if citrgtsecondhassongartist title request if found II citrgtsecondgetSpeed gt speed found true computerid citrgtfirst speed citrgtsecondgetSpeed if found cout ltlt IIFastest download for quotquot ltlt title ltlt quotquot by quot ltlt artist ltlt quot from quot ltlt computerid ltlt endl else cout ltlt quotNo computer found with quotquot ltlt title ltlt quotquot by quot ltlt artist ltlt endl Find and output information about all songs by a given artist void findsongsbyartistconst MP3mapamp mp3system string line artist getlinecin line read the rest of request line Get the artist getlinecin artist you need to write this for lab 147 When to Use Maps Reprise 0 Maps are an association between two types7 one of Which the key must have a operatorlt ordering on it o The association may be immediate 7 Words and their counts 7 Words and the lines on Which they appear 0 Or7 the association may be created by splitting a type 7 Splitting off the name or student id from rest of student record 7 Splitting off the computer id from the rest of the information about the computer and its MP3 les CSCI1200 Computer Science II Fall 2006 Lecture 4 Classes I Review from Lecture 3 o Vectors are dynamicallysized arrays o Vectors strings and other containers should be 7 passed by reference when they are to be changed and 7 passed by constant reference when they arent o If you forget the amp and pass by value the object will be copied which is expensive for containers with lots of elements Note This is unlike arrays which are not copied when passed by 1 He 0 Vectors can contain any type of objects including strings and other vectors Today7s Lecture C classes 0 Types and de ning new types 0 A Date class 0 Class declaration member variables and member functions 0 Using the class member functions 0 Class scope 0 Member function implementation 0 Classes vs structs 0 Designing classes Reading for Lectures 4 amp 5 Koenig and M00 Sections 4244 and Chapter 9 See also Malik Chapter 12 41 Types and De ning New Types 0 What is a type It is a structuring of memory plus a set of operations functions that can be applied to that structured memory 0 Examples integers doubles strings and vectors 0 In many cases when we are using a class we don7t know how that memory is structured Instead what we really think about is the set of operations functions that can be applied To clarify let s focus on strings and vectors These are classes Welll outline what we know about them 7 The structure of memory within each class object 7 The set of operations de ned 0 We are now ready to start de ning our own new types using classes 42 Example A Date Class 0 Many programs require information about dates Information stored about the date includes the month the day and the year 0 Operations on the date include recording it printing it asking if two dates are equal ipping over to the next day incrementing etc 43 C Classes 0 A C class consists of 7 a collection of member variables usually private and 7 a collection of member functions usually public which operate on these variables 0 public member functions can be accessed directly from outside the class 0 private member functions and member variables can only be accessed indirectly through public member functions 0 We will look at the example of the Date class declarationi 44 Using C classes We have been using C classes from the standard library already this semester so studying how the Date class is used is simply a review Program datema n cpp Purpose Demonstrate use of the Date class include ltiostreamgt include quotdate hquot int main stdcout ltlt quotPlease enter today s date nquot ltlt quotProvide the month day and year II int month day year stdcin gtgt month gtgt day gtgt year Date todaymonth day year Date tomorrowtoday getMonth today getDay todaygetYear tomorrow increment O stdcout ltlt IITomorow is II tomorrowprint stdcout ltlt stdendl Date SallysBirthday9291995 if sameDaytomorrow SallysBirthday stdcout ltlt quotHey tomorrow is Sally s birthdaynquot stdcout ltlt quotThe last day in this month is quot ltlt today lastDayInMonth ltlt stdendl return 0 0 Important Each object we create of type Date has its own distinct member variables 0 Calling class member functions for class objects uses the dot notationi For example tomorrow increment 0 Note We don7t need to know the implementation details of the class member functions in order to understand this example This is an important feature of object oriented programming and class design 45 Exercise Add code to datemain cpp to read in another date check if it is a leapyear and check if it is equal to tomorrow Output appropriate messages based on the results of the checks 46 Class Declaration dateh amp Implementation datecpp A Class implementation usually consists of 2 les First we ll look at the header le dateh File date h Purpose Header file with declaration of the Date class including member functions and private member variables class Date Date Dateint aMonth int aDay int aYear ACCESSURS int getDayO const int getMonth const int getYear const MUDIFIERS void setDayint aDay void setMonthint aMonth void setYearint aYear void increment other member functions that operate on date objects bool isEqualconst Dateamp date2 const same day month amp year bool isLeapYear const int lastDayInMonth const bool isLastDayInMonth const void print const output as monthdayyear private REPRESENTATION member variables int ay int month int year prototypes for other functions that operate on class objects are often included in the header file but outside of the class declaration bool sameDayconst Date ampdate1 const Date ampdate2 same day amp month And here is the other part of the Class 39 quot the 39 39 quot le datecpp File date cpp Purpose Implementation file for the Date class include ltiostreamgt include IIdate hquot using namespace std array to figure out the number of days it s used by the auxiliary function daysInMonth const int DaysInMonth13 0 31 28 31 30 31 30 31 31 30 31 30 31 DateDate default constructor day 1 month 1 year 1900 DateDateint aMonth int aDay int aYear construct from month day amp year month aMonth day aDay year aYear void Date setDayint d day d void Date setMonthint m month m void Date setYearint y year y void Date increment if isLastDayInMonth day else day 1 if month 12 f December month int Date getDay const return day int Date getMonth const return month int Date getYear const return year bool Date isEqualconst Dateamp date2 const return day date2 day ampamp month date2 month ampamp year date2 year bool Date isLeapYear const return year4 O ampamp year 100 0 II year400 int Date lastDayInMonth const if month 2 ampamp isLeapYear return 29 else return DaysInMonth month 1 bool Date isLastDayInMonth const return day lastDayInMonth uses member function void Date print const std cout ltlt month ltlt quotquot ltlt day ltlt quotquot ltlt year bool sameDayconst Dateamp date1 const Dateamp date2 return date1getDay date2 getDay ampamp date1getMonth date2getMonth 47 Class scope notation 0 Date indicates that what follows is within the scope of the class 0 Within class scope the member functions and member variables are accessible without the name of the object 48 Constructors These are special functions that initialize the values of the member variables You have already used constructors for string and vector objects 0 The syntax of the call to the constructor mixes variable de nitions and function calls See dateJnain cpp 0 Default constructors have no arguments 0 Multiple constructors are allowed just like multiple functions with the same name are allowed The compiler determines which one to call based on the types of the arguments just like any other function call 0 When a new object is created EXACTLY one constructor for the object is called 49 Member Functions Member functions are like ordinary functions except 0 They can access and modify the object s member variables 0 They can call the other member functions without using an object name 0 Their syntax is slightly different because they are de ned within class scope For the Date class 0 The set and get functions access and change a day month or year 0 The increment member function uses another member function isLastDayInMonth o isEqual accepts a second Date object and then accesses its values directly using the dot notation Since we are inside class Date scope this is allowed The name of the second object date2 is required to indicate that we are interested in its member variables 0 lastDayInMonth uses the const array de ned at the start of the cpp le More on member functions 0 When the member variables are private the only means of accessing them and changing them from outside the class is through member functions o If member variables are made public they can be accessed directly This is usually considered bad style and is not be allowed in this course 0 Functions that are not members of the Date class must interact with Date objects through the class public members aka the public interface77 declared for the class One example is the function sameDay which accepts two Date objects and compares them by accessing their day and month values through their public member functions 410 Header Files and Implementation Files cpp The code for the Date example is in three les 0 The header le date h contains the class declaration o The implementation le date cpp contains the member function de nitions Note that date h is include7ed o dateJnaincpp contains the code outside the class Again date h again is include7ed o The les date cpp and dat eJnain cpp are compiled separately and then linked to form the executable program Different organizations of the code are possible but not preferable In fact we could have put all of the code from the 3 les into a single le main cpp In this case we would not have to compile two separate les In many large projects programmers establish follow a convention with two les per class one header le and one implementation le This makes the code more manageable 411 Constant member functions Member functions that do not change the member variables should be declared const 0 For example bool Date isEqualconst Date ampdate2 const 0 This must appear consistently in both the member function declaration in the class declaration in the h le and in the member function de nition in the cpp le 0 const objects usually passed into a function as parameters can ONLY use const member functions Remember you should only pass objects by value under special circumstances In general pass all objects by reference so they aren t copied and by const reference if you don t wantneed them to change 0 While you are learning you will probably make mistakes in determining which member functions should or should not be const Watch for compile warnings amp errors 412 Exercise Add a member function to the Date class to add a given number of days to the Date object The number should be the only argument and it should be an unsigned int Should this function be const 413 Classes vs structs o The textbook introduces structs in Chapter 4 and classes in Chapter 9 Welve taken a different approach 0 Technically a struct is a class where the default protection is public not private 7 As mentioned above when a member variable is public it can be accessed and changed directly using the dot notation tomorrowday 52 We can see immediately why this is dangerous and an example of bad programming style because a day of 52 is invalid o The usual practice of using struct is all public members and no member functions The example in Sections 4244 illustrates this This practice is contrary to the usual conventions of C programming as discussed in Chapter 9 Rule for the duration of CS II You may not declare new struct types and no class member variable can be made public This rule will ensure you get plenty of practice writing C classes with good programming style 414 C vs Java Classes 0 In C classes have sections labeled public and private but there can be multiple public and private sections In Java each individual item is tagged public or private 0 Class declarations and class de nitions are separated in C whereas they are together in Java 0 In C there is a semicolon at the very end of the class declaration after the 415 Designing and implementing classes This takes a lot of practice but here are some ideas to start from 0 Begin by outlining what the class objects should be able to do This gives a start on the member functions 0 Outline what member variables might be needed to accomplish this 0 Write a draft class declaration in a h le 0 Write code that uses the member functions Revise the class h le as necessary 0 Write the class cpp le that implements the member functions In general donlt be afraid of major rewrites if you nd a class isnlt working correctly or isn7t as easy to use as you intended This happens frequently in practice 416 Exercise What happens if the user inputs 2 30 2006 into the program How would you modify the Date class to make sure illegal dates are not created CSCI1200 Computer Science II Fall 2008 Lecture 16 Trees Part I Review from Lectures 15 0 Maps containing more complicated values Example index mapping words to the text line numbers on which they appear 0 Maps whose keys are class objects Example maintaining student records 0 Summary discussion of when to use maps Today7s Lecture 0 STL set container class like STL map without the pairs 0 Binary Trees and Binary Search Trees 0 De nition amp basic operations 0 Implementation of cs2set class using binary search trees 0 Note Lots more tree stuff in CSCl 2300 Data Structures amp Algorithms DSA 161 Standard Library Sets 0 STL sets are ordered containers storing unique keys An ordering relation on the keys which defaults to operatorlt is necessary Because STL sets are ordered they are technically not traditional mathematical sets 0 Sets are like maps except they have only keys there are no associated values Like maps the keys are constant This means you can t change a key while it is in the set You must remove it change it and then reinsert it 0 Access to items in sets is extremely fast Olog n just like maps 0 Like other containers sets have the usual constructors as well as the size member function 16 2 Set iterators 0 Set iterators similar to map iterators are bidirectional they allow you to step forward and backward through the set Sets provide begin and end iterators to delimit the bounds of the set 0 Set iterators refer to const keys as opposed to the pairs referred to by map iterators For example the following code outputs all strings in the set words for setltstringgt iterator p words begin p wordsend p cout ltlt p ltlt endl 163 Set insert erase and find 0 There are two different versions of the insert member function The rst version inserts the entry into the set and returns a pair he rst component of the returned pair refers to the location in the set containing the entry The second component is true if the entry wasn7t already in the set and therefore was inserted It is false otherwise The second version also inserts the key if it is not already there The iterator pos is a hint as to where to put it This makes the insert faster if the hint is good pairltiteratorboolgt setltKeygt insertconst Keyamp entry iterator setltKeygt insertiterator pos const Keyamp entry There are three versions of erase The rst erase returns the number of entries removed either 0 or I The second and third erase functions are just like the corresponding erase functions for maps Note that the erase functions do not return iterators This is different from the vector and list erase functions sizetype setltKeygt eraseconst Keyamp x void setltKeygteraseiterator p void setltKeygt eraseiterator first iterator last 0 The nd function returns the end iterator if the key is not in the set constiterator setltKeygt findconst Keyamp x const 164 Overview Lists vs Trees vs Graphs 0 Trees create a hierarchical organization of data7 rather than the linear organization in linked lists and arrays and vectors o Binary search trees are the mechanism underlying maps amp sets and multimaps amp multisets o Mathematically speaking A graph is a set of vertices connected by edges And a tree is a special graph that has no cycles The edges that connect nodes in trees and graphs may be directed or undirecte 165 De nition Binary Trees 0 A binary tree strictly speaking7 a rooted binary tree is either empty or is a node that has point ers to two binary trees 0 Here s a picture of a binary tree storing integer values In this figure7 each large box indicates a tree node7 with the top rectangle representing the a value stored and the two lower boxes representing pointers Pointers that are null are shown with a 39 slash through the box 0 The topmost node in the tree is called the root 0 The pointers from each node are called left and I E right The nodes they point to are referred to as that node7s left and right children 0 The subtrees pointed to by the left and right pointers at any node are called the left subtree and right subtree of that node A node where both children pointers are null is called a leaf node A nodels parent is the unique node that points to it Only the root has no parent 166 De nition Binary Search Trees 0 A binary search tree is a binary tree where at each node of the tree7 the value stored at the node is 7 greater than or equal to all values stored in the left subtree7 an 7 less than or equal to all values stored in the right subtree 0 Here is a picture of a binary search tree stor ing string values 167 De nition Balanced Trees 0 The number of nodes on each subtree of each node in a balanced tree is approximately the same In order to be an exactly balanced binary tree7 what must be true about the number of nodes in the tree 0 In order to claim the performance advantages of trees7 we must assume and ensure that our data structure remains approximately balanced You7ll see much more of this in DSAl 168 Exercise Consider the following values 45 98 35 136 192 74 117 1 Draw a binary tree with these values that is NOT a binary search tree 2 Draw two dz erent binary search trees with these values Important note This shows that the binary search tree structure for a given set of values is not unique 3 How many exactly balanced binary search trees exist with these numbers How many exactly balanced binary trees exist with these numbers 169 The Tree Node Class template ltclass Tgt Here is the class de nition for nodes in the tree We will use this for the tree manipulation code we write class TreeNode lc TreeNode leftNULL rightNULL TreeNodeconst Tamp init valueinit leftNULL rightNULL T value TreeNode left TreeNode right Sometimes a 3rd pointer 7 to the parent TreeNode 7 is added 1610 In order Traversal 0 One of the fundamental tree operations is traversing 7 the nodes in the tree and doing something at each node The doing something 7 which is often just printing7 is referred to generically as visiting77 the node 0 There are three general orders in which binary trees are traversed preorder7 in order and postorder 0 These are usually written recursively7 and the code for the three functions looks amazingly similar 0 Here s the code for an inorder traversal to print the contents of a tree void printinorderostreamamp ostr const TreeNodeltTgt p f if p printinorderostr pgtleft ostr ltlt pgtvalue ltlt quotnquot printinorderostr pgtright o How would you modify this code to perform preorder and postorder traversals 1611 Exercises 1 Write a templated function to nd the smallest value stored in a binary search tree Whose root node is pointed to by p 2 Write a function to count the number of odd numbers stored in a binary tree not necessarily a binary search tree of integers The function should accept a TreeNodeltintgt pointer as its sole argument and return an integer Hint think recursively 1612 cs2set and Binary Search Tree Implementation 0 A partial implementation of a set using a binary search tree is in the code attached We Will continue to study this implementation in the next lecture amp lab 0 The increment and decrement operations for iterators have been omitted from this implementation Next lecture we Will discuss a couple strategies for adding these operations 0 We Will use this as the basis both for understanding an initial selection of tree algorithms and for thinking about how standard library sets really work 1613 cs2set Class Overview 0 There is an auxiliary TreeNode class and a treeiterator class The classes are templated o The only member variables of the csZset class are the root and the size number of tree nodes 0 The iterator class is declared internally and is effectively a Wrapper on the TreeNode pointers 7 Note that operatopk returns a const reference because the keys can7t change 7 As just discussed the increment and decrement operators are missing 0 The main public member functions just call a private and often recursive member function passing the root node that does all of the work 0 Because the class stores and manages dynamically allocated memory a copy constructor operator and destructor must be provide 1614 Exercises 1 Provide the implementation of the member function csZsetltTgt begin This is essentially the problem of nding the node in the tree that stores the smallest va ue 2 Write a recursive version of the function find Partial implementation of binarytree based set class similar to stdset The iterator increment amp decrement operations have been omitted ifndef cs2seth define cs2seth include ltiostreamgt include ltutilitygt TREE NUDE CLASS template ltclass Tgt class TreeNode u lic TreeNode leftNULL rightNULL TreeNodeconst Tamp init valueinit leftNULL rightNULL T value TreeNode left TreeNode right y template ltclass Tgt class cs2set TREE NUDE ITERATOR CLASS template ltclass Tgt class treeiterator public treeiterator ptrNULL treeiteratorTreeNodeltTgt p ptrp treeiteratorconst treeiteratoramp old ptroldptr 39treeiterator treeiteratoramp operatorconst treeiteratoramp old ptr oldptr return this operator gives constant access to the value at the pointer const Tamp operator const return ptrgtvalue comparions operators are straightforwa friend bool operatorconst treeiteratoramp 1 const treeiteratoramp r return lptr r ptr friend bool operatorconst treeiteratoramp 1 const treeiteratoramp r return lptr r ptr increment amp decrement will be discussed in Lecture 17 and Lab 1 private representation TreeNodeltTgt ptr y CS2 SET CLASS template ltclass Tgt class cs2set public cs2set rootNULL size0 cs2setconst cs2setltTgtamp old sizeold size root thisgtcopytreeoldroot 39cs2set thisgtdestroytreeroot root NULL cs2setamp operatorconst cs2setltTgtamp old if ampOld this thisgtdestroytreeroot root thisgtcopytreeoldroot size old size return this typedef treeiteratorltTgt iterator int size const return size bool operatorconst cs2setltTgtamp old const return old root thisgtroot FIND INSERT amp ERASE iterator findconst Tamp keyvalue return findkeyvalue root std pairlt iterator bool gt insertT constamp keyvalue return insertkeyvalue root int eraseT constamp keyvalue return erasekeyvalue root OUTPUT amp PRINTING friend stdostreamamp operatorltlt stdostreamamp ostr const cs2setltTgtamp s s printinorderostr sroot return ostr void printassidewaystreestdostreamamp ostr const printassidewaystreeostr root 0 ITERATORS iterator begin const Implemented in Lecture 16 iterator end const return iteratorNULL private REPRESENTATION TreeNodeltTgt root int size PRIVATE HELPER FUNCTIONS TreeNodeltTgt copytreeTreeNodeltTgt oldroot Implemented in Lab 10 void destroytreeTreeNodeltTgt p Implemented in Lecture 17 iterator findconst Tamp keyvalue TreeNodeltTgt p f Implemented in Lecture 16 std pairltiteratorboolgt insertconst Tamp keyvalue TreeNodeltTgtamp p f Discussed in Lecture 17 int eraseT constamp keyvalue TreeNodeltTgt ampp Implemented in Lecture 17 void printinorderstdostreamamp ostr const TreeNodeltTgt p const Discussed in Lecture 16 if p printinorderostr pgtleft ostr ltlt pgtvalue ltlt IInquot printinorderostr pgtright void printassidewaystreestdostreamamp ostr const TreeNodeltTgt p int depth const Discussed in Lecture 17 endif CSCI1200 Computer Science II Spring 2006 Lecture 9 Introduction to Recursion Review from Lecture 8 o Returning const references to member variables provides access to important variables without the cost of copying and without the danger of allowing them to be changed 0 Lists vs vectors 0 lterators 0 Special properties of vector iterators o The erase function from vectors and lists 0 Sieve of Eratosthenes Today7s Lecture 0 Introduction to recursion factorials and exponentiation o How recursion works 0 Iteration vs recursion 0 Rules for writing recursive functions 0 Examples that we will work on together 7 Printing a vector in reverse order 7 Binary search We will look at more sophisticated problems in Lecture 10 91 Recursive De nitions of Factorial and Integer Exponentiation o The factorial is de ned for nonnegative integers as n 7nnill ngt0 7 1 n 0 Computing integer powers is de ned as npi nnp l pgt0 1 p 92 Recursive C Functions C7 like other modern programming languages7 allows functions to call themselves This gives a direct method of implementing recursive functions 0 Here s the implementation of factorial int factint n 39C int result factn1 return 11 result 0 And herels the implementation of exponentiation int intpowint 11 int 13 39C if p 0 return 1 else return 11 intpow n p1 339 339 93 The Mechanism of Recursive Function Calls 0 For each recursive call or any function call a program creates an activation record to keep track of 7 Completely separate instances of the parameters and local variables for the newlycalled function 7 The location in the calling function code to return to when the newlycalled function is complete Who asked for this function to be called Who wants the answer 7 Which activation record to return to when the function is done For recursive functions this can be confusing since there are multiple activation records waiting for an answer from the same function 0 This is illustrated in the following diagram of the call fact 4 Each box is an activation record the solid lines indicate the function calls and the dashed lines indicate the returns Inside of each box we list the parameters and local variables and make notes about the computation fact3 n3 result fact2 return 3 2 fact2 n2 result fact 1 return 21 fact 1 n1 result fact0 retum 11 94 Iteration vs Recursion 0 Each of the above functions could also have been written using a for or while loop iiei iteratively o For example here is an iterative version of factorial int ifactint n int result 1 for int i1 iltn i result result i return result H 2 96 Often writing recursive functions is more natural than writing iterative functions especially for a rst draft of an problem implementationi You should learn how to recognize whether an implementation is recursive or iterative and practice rewriting one version as the other Note Welll see that not all recursive functions can be rewritten in iterative forml Note The order notation for the number of operations for the recursive and iterative versions of an algorithm is usually the same However in C C Java and some other languages iterative functions are generally faster than their corresponding recursive functions This is due to the overhead of the function call mecha nismi Compiler optimizations will sometimes but not always reduce the performance hit by automatically eliminating the recursive function calls Exercise Draw a picture to illustrate the activation records for the function call cout ltlt intpow4 4 ltlt endl Write an iterative version of intpowi Rules for Writing Recursive Functions Here is an outline of ve steps that are useful in writing and debugging recursive functionsi Note You don7t have to do them in exactly this order 1 2 F90 01 Handle the base casesi De ne the problem solution in terms of smaller instances of the problemi Use wishful thinking ie if someone else solves the problem of fact 4 I can extend that solution to solve fact5i This de nes the necessary recursive callsi It is also the hardest part Figure out what work needs to be done before making the recursive callsi Figure out what work needs to be done after the recursive calls completes to nish the computation What are you going to do with the result of the recursive cal 7 i Assume the recursive calls work correctly but make sure they are progressing toward the base casesl Example Printing the Contents of a Vector Here is a function to print the contents of a vector Actually its two functions a driver function and a true recursive function It is common to have a driver function that just initializes the rst recursive function call void printvecvectorltintgtamp v 39C printvecv 0 void printvecvectorltintgtamp v unsigned int i 39C if i lt vsize 39C 00111 ltlt 1 ltlt quot quot ltlt vi ltlt endl printvecv 11 0 Exercise What will this print when called in the following code int main 39C vectorltintgt a apushback3 apushback5 apushback11 apushback17 printvec a 0 Exercise How can you change the second pr intvec function as little as possible so that this code prints the contents of the vector in reverse order 9 8 Binary Search Suppose you have a vectorltTgt v where T is a placeholder for a speci c type7 sorted so that v0 lt v1 lt v2 lt Now suppose that you want to nd if a particular value x is in the vector somewhere How can you do this without looking at every value in the vector 0 The solution is an algorithm called binary search Let7s write the recursive version of this algorithm We re going to write it for general vectors using the template syntax This function will work on vectors of my type7 as long as the basic operators such as lt and are de ned for that type Here s the prototype for the driver function template ltclass Tgt bool binsearchconst vectorltTgtamp v const Tamp x 99 Looking Ahead to Lecture 10 o The problems we looked at today can be easily solved using nonrecursive techniques This will not be true when we look at these two problems next time 7 Sorting a vector using the mergesort technique 7 Solving a word search77 problem in a grid of letters allowing nonstraight paths CSCI1200 Computer Science II Spring 2006 Lecture 5 Classes I Review from Lecture 4 o Vectors are dynamicallysized arrays o Vectors strings and other containers should be 7 passed by reference when they are to be changed and 7 passed by constant reference when they arent o If you forget the amp and pass by value the object will be copied which is expensive for containers with lots of elements Note This is unlike arrays which are not copied when passed by 1 He 0 Vectors can contain any type of objects including strings and other vectors Today7s Lecture C classes 0 Types and de ning new types 0 A Date class 0 Class declaration member variables and member functions 0 Using the class member functions 0 Class scope 0 Member function implementation 0 Classes vs structs 0 Designing classes Reading for Lectures 5 amp 6 Koenig and M00 Sections 4244 and Chapter 9 See also Malik Chapter 12 51 Types and De ning New Types 0 What is a type It is a structuring of memory plus a set of operations functions that can be applied to that structured memory 0 Examples integers doubles strings and vectors 0 In many cases when we are using a class we don7t know how that memory is structured Instead what we really think about is the set of operations functions that can be applied 0 To clarify let s focus on strings and vectors These are classes We7ll outline what we know about them 7 The structure of memory within each class object 7 The set of operations de ned 0 We are now ready to start de ning our own new types using classes 52 Example A Date Class 0 Many programs require information about dates 0 Information stored about the date includes the month the day and the year 0 Operations on the date include recording it printing it asking if two dates are equal ipping over to the next day incrementing etc 53 C Classes 0 A C class consists of 7 a collection of member variables usually private and 7 a collection of member functions usually public which operate on these variables 0 public member functions can be accessed directly from outside the class 0 private member functions and member variables can only be accessed indirectly through public member functions 0 We will look at the example of the Date class declarationi 54 Using C classes We have been using C classes from the standard library already this semester so studying how the Date class is used is simply a review Program datemain c Purpose Demonstrate use of the Date class include ltiostreamgt include quotdate hquot int main stdcout ltlt quotPlease enter today s date nquot ltlt quotProvide the month day and year quot int month day year stdcin gtgt month gtgt day gtgt year Date today month day year Date tomorrow todaygetMonth todaygetDay todaygetYear tomorrow increment O stdcout ltlt IITomorow is quot tomorrowprint stdcout ltlt stdendl Date SallysBirthday9291995 call a different constructor if sameDay tomorrow SallysBirthday stdcout ltlt quotHey tomorrow is Sally s birthdaynquot stdcout ltlt quotThe last day in this month is quot ltlt today lastDayInMonth ltlt stdendl return 0 0 Important Each object we create of type Date has its own distinct member variables 0 Calling class member functions for class objects using the dot notationi For example tomorrow increment 0 Note after looking at the example we still will not have examined how the class member functions are implemented This is an important feature of class design 55 Exercise Add code to datemain cpp to read in another date check if it is a leapyear and check if it is equal to tomorrow Output appropriate messages based on the results of the checks 56 Class Implementation dateh amp datecpp A Class implementation usually consists of 2 les First we ll look at the header le dateh File date h Purpose Header file with declaration of the Date class including member functions and private member variables class Date Date Dateint aMonth int aDay int aYear Assignment and change void setDay int aDay void setMonth int aMonth void setYear int aYear void increment Access individual values int getMonth const int getYear const Functions that answer questions about a Date object bool isEqualconst Dateamp date2 const same day month year bool isLeapYear const int lastDayInMonth const bool isLastDayInMonth const Output as monthdayyear void print const private Member variables int day int month int year bool sameDay const Date ampdate1 const Date ampdate2 And here is the other part of the Class 39 quot the 39 39 quot le datecpp File date cpp Purpose Implementation file for the Date class include ltiostreamgt include IIdate hquot using namespace std array to figure out the number of days it s used by the auxiliary function daysInMonth const int DaysInMonth13 0 31 28 31 30 31 30 31 31 30 31 30 31 DateDate default constructor day 1 month 1 year 1900 DateDateint aMonth int aDay int aYear construct from monthdayyear month aMonth day aDay year aYear void Date setDayint d day d void Date setMonthint m month m void Date setYearint y year y void Date increment if isLastDayInMonth day day 1 if month 12 f December int Date getDay const return day int Date getMonth const return month int Date getYear const return year bool Date isEqualconst Dateamp date2 const return day date2 day ampamp month date2 month ampamp year date2 year bool Date isLeapYear const return year4 O ampamp year 100 0 II year400 int Date lastDayInMonth const if month 2 ampamp isLeapYear return 29 else return DaysInMonth month 1 bool Date isLastDayInMonth const return day lastDayInMonth uses member function void Date print const std cout ltlt month ltlt quotquot ltlt day ltlt quotquot ltlt year bool sameDay const Dateamp date1 const Dateamp date2 return date1getDay date2 getDay ampamp date1getMonth date2getMonth 57 Class scope notation 0 Date indicates that what follows is within the scope of the class 0 Within class scope the member functions and member variables are accessible without the name of the object 5 8 Constructors These are special functions that initialize the values of the member variables You have already used constructors for string and vector objects 0 The syntax of the call to the constructor mixes variable de nitions and function calls See dateJnain cpp 0 Default constructors have no arguments 0 Multiple constructors are allowed just like multiple functions with the same name are allowed The compiler determines which one to call based on the types of the arguments just like any other function call 0 When a new object is created EXACTLY one constructor for the object is called 59 Member Functions Member functions are like ordinary functions except 0 They can access and modify the object s member variables 0 They can call the member functions without using an object name 0 Their syntax is slightly different because they are de ned within class scope For the Date class 0 set and get functions access and change a day month or year 0 The increment member function uses another member function isLastDayInMonth o isEqual accepts a second Date object and then accesses its values directly using the dot notation Since we are inside class Date scope this is allowed The name of the second object date2 is required to indicate that we are interested in its member variables 0 lastDayInMonth uses the const array de ned at the start of the cpp le More on member functions 0 When the member variables are private the only means of accessing them and changing them from outside the class is through member functions o If member variables are made public they can be accessed directly This is usually considered bad style and will not be allowed in this course 0 Functions that are not members of the Date class must interact with Date objects through the class public members aka the public interface77 declared for the class One example is the function sameDay which accepts two Date objects and compares them by accessing their day and month values through their public member functions 510 Header Files and Implementation Files cpp The code for the Date example is in three les 0 The header le date h contains the class declaration o The implementation le datecpp contains the member function de nitions Note that dateh is included 0 dateJnaincpp contains the code outside the class Again date h again is included 0 The les date cpp and dat eJnain cpp are compiled separately and then linked to form the executable program Different organizations of the code are possible but not preferrable For example we could have combined dateh and datecpp into a single le and included it in the main program In this case we would not have to compile two separate les In many large projects programmers establish follow a convention with two les per class one header le and one implementation le 511 Constant member functions Member functions that do not change the member variables should be declared const 0 For example bool Date isEqualconst Date ampdate2 const 0 This must appear consistently in both the member function declaration in the class declaration in the h le and in the member function de nition in the cpp le 0 const objects usually passed into a function as parameters can ONLY use const member functions Remember you should only pass objects by value under special circumstances In general pass them by const reference you don t want them to change 0 While you are learning you will probably make errors in determining which member functions should or should not be constl Watch for compile errors 512 Exercise Add a member function to the Date class to add a given number of days to the Date object The number should be the only argument and it should be an unsigned int Should this function be const 513 Classes vs structs o The textbook introduces structs in Chapter 4 and classes in Chapter 9 Welve taken a different approach 0 Technically a struct is a class where the default protection is public not private 7 As mentioned above when a member variable is public it can be accessed and changed directly using the dot notation tomorrowday 52 We can see immediately that this is dangerous because a day of 52 is invalid o The usual practice of using struct is all public members and no member functions The example in Sections 4244 illustrates this This practice is contrary to the usual conventions of C programming as discussed in Chapter 9 Rule for the duration of CS II We will not allow the use of struct and no member variable can be made public This will be enforced with various levels of grading penalties 514 C vs Java Classes 0 In C classes have sections labeled public and private but there can be multiple public and private sections In Java each individual item is tagged public or private 0 Class declarations and class de nitions are separated in C whereas they are together in Java 0 In C there is a semicolon at the very end of the class declaration after the 515 Designing and implementing classes This takes a lot of practice but here are some ideas to start from 0 Begin by outlining what the class objects should be able to do This gives a start on the member functions 0 Outline what member variables might be needed to accomplish this 0 Write a draft class declaration in a h le 0 Write code that uses the member functions Revise the class h le as necessary 0 Write the class cpp le that implements the member functions In general donlt be afraid of major rewrites if you nd a class isnlt working correctly or isn7t as easy to use as you intended This happens frequently in practice 516 Exercise What happens if the user inputs 2 30 2006 into the program How would you modify the Date class to make sure illegal dates are not created Computer Science II 7 CSci 1200 Lecture 21 Priority Queues and Heaps Review from Lecture 20 o Collision resolution 0 Using a hash table to implement a set 7 Function objects 7 Overall design 7 lterators 7 Fundamental operations nd insert and erase c We will complete our discussion today 7 Erase 7 Resize 7 lterators 7 Limitations Today7s Class 0 Idea of a priority queue o A priority queue as a heap 7 a complete binary tree 0 Percolate up and percolate down operations 0 A heap as a vector 0 Making a heap o Heap sort Priority Queue 7 Fundamental Operations 0 Priority queues are used in prioritizing operations Examples include jobs on a shop oor packet routing in a network scheduling in an operating system or events in a simulation 0 Among the data structures we have studied their interface is most similar to a queue including the idea of a front or top and a tail or a back 0 Each item is stored in a priority queue using an associated priority and therefore the top item is the one with the lowest value of the priority score 7 The tail or back is never accessed through the interface to a priority queue o The main operations are insert or push and pop or deletemin Data Structure Options 0 Vector or list either sorted or unsorted 7 Here at least one of the operations push or pop will cost linear time at least if we think of the container as a linear structure 0 Binary search trees 7 If we use the priority as a key then we can use a combination of nding the minimum key and erase to implement pop An ordinary binary search tree insert may be used to implement push 7 This costs logarithmic time in the average case and in the worst case as well if balancing is used c The latter is the better solution but we would like to improve upon it 7 for example it might be more natural if the minimimum priority value were stored at the root 7 We will achieve this using a heap giving up the complete ordering imposed in the binary search tree Binary Heaps 0 De nition A binary heap is a complete binary tree such that at each internal node p the value stored is less than the value stored at either of p s children 7 A complete binary tree is one that is completely lled except perhaps at the lowest level and at the lowest level all leaf nodes are as far to the left as possible 0 Binary heaps will be drawn as binary trees but implemented using vectors 0 Alternatively the heap could be organized such that the value stored at each internal node is greater than the values at its children Pop Delete Min 0 The top root of the tree is removed o It is replaced by the value stored in the last leaf node 7 This has echoes of the erase function in binary search trees 7 We have not yet discussed how to nd the last leaf 0 The last leaf node is removed 0 The following percolatedown function is then run to restore the heap property This function is written here in terms of tree nodes with child pointers and the priority stored as a value7 but later it will be written in terms of vector subscripts percolatedown TreeNodeltTgt p while p gtleft TreeNodeltTgt child Choose the child to compare against if pgtright ampamp pgtrightgtvalue lt p gtleft gtvalue child p gtright else child p gtleft if child gtvalue lt p gtvalue swapchild p value and other nonpointer member vars p child else break Push Insert 0 To add a value to the heap7 a new last leaf node in the tree is created and then the following percolateup function is run It assumes each node has a pointer to its parent percolateup TreeNodeltTgt p while p gtparent if p gtvalue lt p gtparent gtvalue swapp parent value and other nonpointer member vars p p gtparent else break Analysis 0 Both percolatedown and percolateup are Olog n in the worst case o But7 percolateup and as a result push is 01 in the average case 0 This analysis will be discussed brie in class Exercise Suppose the following operations are applied to an initially empty binary heap of integers Show the resulting heap after each deletemin operation Remember7 the tree must be complete push 5 push 3 push 8 push 10 push 1 push 6 P0P push 14 push 2 push 4 push 7 Pop Pop Pop Vector Implementation 0 In the vector implementation the tree is never explicitly constructed Instead the heap is stored as a vector with child and parent pointers implicit c To do this number the nodes in the tree top to bottom and left to right starting with 0 Place the values in a vector in this order 0 As a result for each subscript i 7 The parent if it exists is at location 7 12j 7 The left child if it exists is at location 2i 1 1 7 The right child if it exists is at location 2i 1 2 o For a binary heap containing 71 values the last leaf is at location 71 7 1 in the vector and the last internal non leaf node is at location 7 12j o The standard library STL priorityqueue is implemented as a binary heap c We will explore this implementation further in Lab 12 Exercise 1 Show the vector contents for the binary heap after each deleteJnin operation push 8 push 12 push 7 push 5 push 17 push 1 P0P push 6 push 22 push 14 push 9 P0P P0P Building A Heap o In order to build a heap from a vector of values for each index from 717 12j down to 0 run percolatedown o It can be shown that this requires at most 0n operations 0 If instead we ran percolateup from each index starting at n 1 down to O we would incur a On log 71 cost Heap Sort 0 Here is a simple algorithm to sort a vector of values build a heap and then run 71 consecutive pop operations storing each popped value in a new vector o It is straightforward to show that this requires On log n time o This can also be done in place so that a separate vector is not needed Summary 0 Priority queues are conceptually similar to queues but the order in which values entries are removed popped depends on a priority 0 Heaps which are conceptually a binary tree but are implemented in a vector are the data structure of choice for a priority queue o In some applications the priority of an entry may change while the entry is in the priority queue This requires that there be hooks usually in the form of indices into the internal structure of the priority queue This is an implementation detail we have not discussed Computer Science II 7 CSci 1200 Lecture 21 Priority Queues and Heaps T0day7s Class 0 Idea of a priority queue o A priority queue as a heap 7 a complete binary tree 0 Percolate up and percolate down operations 0 A heap as a vector 0 Making a heap o Heap sort Priority Queue 7 Fundamental Operations 0 Priority queues are used in prioritizing operations Examples include jobs on a shop oor packet routing in a network scheduling in an operating system or events in a simulation 0 Among the data structures we have studied their interface is most similar to a queue including the idea of a front or top and a tail or a back 0 Each item is stored in a priority queue using an associated priority and therefore the top item is the one with the lowest value of the priority score 7 The tail or back is never accessed through the interface to a priority queue o The main operations are insert or push and pop or deletemin Data Structure Options 0 Vector or list either sorted or unsorted 7 Here at least one of the operations push or pop will cost linear time at least if we think of the container as a linear structure 0 Binary search trees 7 If we use the priority as a key then we can use a combination of nding the minimum key and erase to implement pop An ordinary binary search tree insert may be used to implement push 7 This costs logarithmic time in the average case and in the worst case as well if balancing is used c The latter is the better solution but we would like to improve upon it 7 for example it might be more natural if the minimimum priority value were stored at the root 7 We will achieve this using a heap giving up the complete ordering imposed in the binary search tree Binary H eaps 0 De nition A binary heap is a complete binary tree such that at each internal node p the value stored is less than the value stored at either of p s children 7 A complete binary tree is one that is completely lled except perhaps at the lowest level and at the lowest level all leaf nodes are as far to the left as possible 0 Binary heaps will be drawn as binary trees but implemented using vectors 0 Alternatively the heap could be organized such that the value stored at each internal node is greater than the values at its children Pop Delete Min 0 The top root of the tree is removed o It is replaced by the value stored in the last leaf node 7 This has echoes of the erase function in binary search trees 7 We have not yet discussed how to nd the last leaf 0 The last leaf node is removed 0 The following percolatedown function is then run to restore the heap property This function is written here in terms of tree nodes with child pointers and the priority stored as a value7 but later it will be written in terms of vector subscripts percolatedown TreeNodeltTgt p while p gtleft TreeNodeltTgt child Choose the child to compare against if pgtright ampamp pgtrightgtvalue lt p gtleft gtvalue child p gtright else child p gtleft if child gtvalue lt p gtvalue swapchild p value and other nonpointer member vars p child else break Push Insert 0 To add a value to the heap7 a new last leaf node in the tree is created and then the following percolateup function is run It assumes each node has a pointer to its parent percolateup TreeNodeltTgt p while p gtparent if p gtvalue lt p gtparent gtvalue swapp parent value and other nonpointer member vars p p gtparent else break Analysis 0 Both percolatedown and percolateup are Olog n in the worst case o But7 percolateup and as a result push is 01 in the average case 0 This analysis will be discussed brie y in class Exercise Suppose the following operations are applied to an initially empty binary heap of integers Show the resulting heap after each deletemin operation Remember7 the tree must be complete push 5 push 3 push 8 push 10 push 1 push 6 P0P push 14 push 2 push 4 push 7 Pop Pop Pop Vector Implementation 0 In the vector implementation the tree is never explicitly constructed Instead the heap is stored as a vector with child and parent pointers implicit c To do this number the nodes in the tree top to bottom and left to right starting with 0 Place the values in a vector in this order 0 As a result for each subscript i 7 The parent if it exists is at location 7 12j 7 The left child if it exists is at location 2i 1 1 7 The right child if it exists is at location 2i 1 2 o For a binary heap containing 71 values the last leaf is at location 71 7 1 in the vector and the last internal non leaf node is at location 7 12j o The standard library STL priorityqueue is implemented as a binary heap c We will explore this implementation further in Lab 12 Exercise 1 Show the vector contents for the binary heap after each deleteJnin operation push 8 push 12 push 7 push 5 push 17 push 1 P0P push 6 push 22 push 14 push 9 P0P P0P Building A Heap o In order to build a heap from a vector of values for each index from 717 12j down to 0 run percolatedown o It can be shown that this requires at most 0n operations 0 If instead we ran percolateup from each index starting at n 1 down to O we would incur a On log 71 cost Heap Sort Here is a simple algorithm to sort a vector of values build a heap and then run 71 consecutive pop operations storing each popped value in a new vector It is straightforward to show that this requires On log n time This can also be done in place so that a separate vector is not needed Summary A priority queue is conceptually similar to queues but the order in which values entries are removed popped depends on a priority A heap Whose logic structure is a binary tree but Whose implementation uses a vector is the data structure of choice for a priority queue In some applications the priority of an entry may change while the entry is in the priority queue This requires that there be hooks usually in the form of indices into the internal structure of the priority queue This is an implementation detail we have not discussed CSCI1200 Computer Science II Fall 2006 Lecture 22 Hash Tables Review from Lectures 20 amp 21 o Binary Trees amp Binary Search Trees 0 cs2set class implemented using a Binary Search Tree 0 BST operations nd insert destroy erase remove element printing begin amp end iterators tree height 221 Tree Iterators Increment amp Decrement o The increment operator should change the iterator s pointer to point to the next TreeNode in an in order traversal 7 the inorder successor77 7 while the decre tree iterator ment operator should change the itera Pm tor s pointer to point to the inorder predecessor Unlike the situation with lists and vec tors these predecessors and successors are not necessarily nearby either in physical memory or by following a link in the tree 0 There are two common solution ap TreeNOdew proaches Valuer 2 parent le IIight 7 Each iterator maintains a stack of pointers representing the path down the tree to the current nodei value 4 value 12 parent parent le right le right o If we choose the parent pointer method we7ll need to rewrite the insert and erase member functions to correctly adjust parent pointersi TreeNodeW value 18 parent le right 7 Each node stores a parent pointer see diagrami Only the root node has a null parent pointeri Although iterator increment looks expensive in the worst case for a single application of operator it is fairly easy to show that iterating through a tree storing n nodes requires 0n operations overa 222 Exercise 0 Implement an algorithm for nding the in order successor of a node TreeNode FindSuccessorTreeNode current 39C 223 Binary Search Tree Performance 0 The efficiency of the main find insert amp erase algorithms depends on the height of the tree 0 The bestcase and averagecase heights of a binary search tree storing n nodes are both Olog The worst case which often can happen in practice is O n Exercise Draw an example tree and specify the arguments to find insert amp erase that would exhibit this worstcase behavior Algorithms that automatically re balance a tree data structure in order to avoid the worstcase behavior will be covered in Data Structures and Algorithms Examples include redblack trees or AVL trees Standard Library STL maps amp sets are implemented using a tree data structure Thatls why all the find insert and erase operations run in Olog n operations and iterating through the data structure produces the elements in sorted order 224 Today7s Lecture Hash Tables 0 Hash Tables Hash Functions and Collision Resolution 0 Hash Table Performance 0 Binary Search Trees vs Hash Tables 225 De nition Whats a Hash Table 0 A table implementation with constant time access 7 Like a map we can store keyvalue pair associations in the hash table But its even faster to do find insert and erase with a hash table However hash tables don t store the data in sorted order 0 A hash table is implemented with a array at the top level 0 Each key is mapped to a slot in the array by a hash function 226 De nition Whats a Hash Function 0 A simple function of one argument the key which returns an index a bucket or slot in the array 0 Ideally the function will uniformly distribute the keys throughout the range of legal index values 0 A k l 0 What s a collision When the hash function maps multiple different keys to the same index 0 How do we deal with collisions One way to resolve this is by storing a linked list of values at each slot in the array 227 Example Caller ID 0 We are given a phonebook with 50000 namenumber pairings Each number is a 10 digit number We need to create a data structure to lookup the name matching a particular phone number ldeally name lookup should be 01 time expected and the caller ID system should use On memory 11 50000 0 Welll review how we solved this problem in Lab 5 with an STL vector then an STL map Finally welll implement the system with a hash table 0 Note In the toy implementations that follow we use small datasets but we should evaluate the system scaled up to handle the large dataset 228 Caller ID With an STL Vector void addvectorltstringgt ampphonebook int number string name phonebooknumber name void identifyconst vectorltstringgt ampphonebook int number if phonebooknumber quotUNASSIGNEDquot cout ltlt quotunknown callerquot ltlt endl else cout ltlt phonebooknumber ltlt quot is callingquot ltlt endl int main create the phonebook initially all numbers are unassigned vectorltstringgt phonebook1000O quotUNASSIGNEDquot add several names to the phonebook addphonebook 1111 quotfredquot addphonebook 2222 quotsallyquot addphonebook 3333 quotgeorgequot test the phonebook identifyphonebook 2222 identifyphonebook 4444 Exercise What s the memory usage for the vectorbased Caller ID system Whats the expected running time for nd insert and erase 229 Caller ID With an STL Map void addmapltintstringgt ampphonebook int number string name phonebooknumber name void identifyconst mapltintstringgt ampphonebook int number mapltintstringgt constiterator tmp phonebookfindnumber if tmp phonebook end cout ltlt quotunknown callerquot ltlt endl cout ltlt tmpgtsecond ltlt quot is callingquot ltlt endl int main create the phonebook initially all numbers are unassigned mapltintstringgt phonebook add several names to the phonebook addphonebook1111quotfredquot addphonebook2222quotsallyquot addphonebook3333quotgeorgequot test the phonebook identifyphonebook2222 identifyphonebook4444 Exercise What s the memory usage for the mapbased Caller ID system Whats the expected running time for nd insert and erase 2210 Now lets implement Caller ID With a Hash Table define PHONEBO0KSIZE 10 3 class Node 5182764321 u ic 6175551212 fred 5182761234 allce int number string name Node next l corresponds a phone number to a slot in the array int hashfunctionint number E add a number name pair to the phonebook void addNode phonebookPHONEBO0KSIZE int number string name l 5182761267 carol 00lOUIIgtUJNgt t given a phone number determine who is calling void identifyNOde phonebookPHONEBO0KSIZE int number int main create the phonebook initially all numbers are unassigned Node phonebookPHONEBO0KSIZE for int i O i lt PHONEBUUKSIZE i phonebooki NULL add several names to the phonebook addphonebook 1111 quotfredquot addphonebook 2222 IIsallyquot addphonebook 3333 IIgeorgequot test the phonebook identifyphonebook 2222 identifyphonebook 4444 2211 Exercise Choosing a Hash Function 0 Whats a good hash function for this application 0 Whats a bad hash function for this application 2212 Exercise Hash Table Performance 0 Whats the memory usage for the hashtable basecl Caller ID system 0 Whats the expected running time for nd7 insert7 and erase Computer Science ll 7 CSci 1200 Lecture 18 Recursion Revisited Completing Lecture 17 0 Reviewing the erase function and its effect on the tree 0 lterating through the tree 7 Parent pointer at each node 7 operator requires nding the in order successor to a node If the node has a right child the successor is the left most descendent of the right child which could just be the right child itself If the node does not have a right child the successor is found by walking back up the treeas long as the continues up right branches As soon as a left branch is traversed the in order successor is found Recursion o Reminder rules for writing recursive functions 1 De ne the recursion 7 the relationship between solutions to subproblems and solutions to the complete problem Handle the base case or cases rst in the function 2 3 What happens before recursive call or calls 4 What happens after 5 Assume the recursion works if everything else is correct but make sure the recursion is proceeding toward the base case 0 Examples 7 Binary search 7 Tree height computation 7 Accumulate function from Lab 9 o In our earliest examples 7 factorial bonacci and even binary search 7 the problems are easily solved without recursion The same is not true for tree height computation accumulate and the functions we will consider here 0 Today s problems 7 Merge sort 7 Non linear maze search Merge Sort o Idea 7 Split a vector in half 7 Recursively sort each half 7 Merge the two sorted halves into a single sorted vector 0 We will work an example rst to see how it is done 0 The recursive code with everything provided except the merging function is attached to the notes Merge 7 The Idea We have already considered example problems involving merging of two ordered sequences but here is a complete discussion of the idea 0 Suppose we have a vector called values having two halves that are each already sorted In particular the values in subscript ranges low mid the lower interval and mid1high the upper interval are each in increasing order 0 Ask yourself which value can be rst if the two intervals are sorted Which value could be next 0 In a loop the merging algorithm repeated chooses one value to copy to scratch 7 At each step of the loop there are only two possibilities the rst uncopied value from the lower interval and the rst uncopied value from the upper interval The copying ends when one of the two intervals is exhausted Then the remainder of the other interval is copied into the scratch vector Finally the entire scratch vector is copied back 0 We will complete the code during lecture Thinking About Merge Sort o It exploits the power of recursion We only need to think about 7 Base case intervals of size 1 7 Splitting the vector 7 Merging the results Recall the ve rules of recursion c We will insert cout statements into the algorithm and use this to try to understand what is happening Example Word Search 0 Take a look at the following grid of characters DunUd law oab o The e nf y r In I h ne 5 d th 1 h du j f oe r e cp m a rm r i fe a a dr e d39OQHIh mHHSLt I a u aadf a e adfa e n sart f i eerd a f avcz h p adlf i e rtlk e e ohtr o t ycrh l u tryr usual problem associated with a grid like this is to nd words going forward7 loackward7 up7 down7 or along a diagonal Can you nd computer 0 A sketch of the solution is as follows The grid of letters is represented as vectorlt string gt grid Each string represents a row We can treat this as a two dimensional array7 however A word to be sought7 such as computer is read as a string A pair of nested for loops searches the grid for occurrrences of the rst letter in the string Call such a location r c At each such location7 the occurrences of the second letter are sought in the 8 locations surrounding r c At each location where the second letter is found7 a search is initiated in the direction indicated For example7 if the second letter is at r of 17 the search for the remaining letters proceeds up the grid 0 At this point7 you should not have too much di iculty implementing such an algorithm 0 We are going to spend the rest of today s lecture on a di rerent7 but somewhat harder problem Nonlinear Word Search 0 Here is the same grid of letters as above heanfuyaadfj crarneradfad chenenssartr kdfthileerdr chadufjavcze dfhoepradlfc neicpemrtlkf paermerohtrr diofetaycrhg daldruetryrt What happens when we no longer require the locations to be along the same row column or diagonal of the grid but instead allow the locations to shake through the grid The only requirements are that 1 the locations of adjacent letters are connected along the same row column or diagonal and 2 a location can not be used more than once in each word 0 Can you nd rensselaer It is there How about temperature Close but hope The implementation of this is very similar to the implementation described above until after the rst letter of a word is found We will look at the code during lecture and then consider how to write the recursive function Summary of Idea for Recursion o Recursion starts at each location where the rst letter is found 0 Each recursive call attempts to nd the next letter by searching around the current position When it is found a recursive call is made 0 The current path is maintained at all steps of the recursion o The base case77 occurs when the path is full or all positions around the current position have been tried We will complete the implementation during lecture Computer Science 11 7 CSci 1200 Lecture 19 Data Structure Summary Hashing Part 1 Review from Lecture 18 o The erase function and its effect on the tree 0 lterating through the tree using parent pointers to nd the in order successor 0 Advanced recursion 7 Mergesort 7 Nonlinear search Today Reading FordampTopp Chapter 12 through Section 125 0 Summary of data structures we have studied thus far 0 Stacks and queues a quick introduction 0 Hashing 7 Idea 7 Hash functions 7 Hash tables 7 Collision resolution Data Structures Fundamental Operations 0 Find Find the location of a keyvalue in the data structure container or if the keyvalue is not in the data structure nd the location to insert it 0 Insert Given the required location insert the keyvalue plus any other data into the container 0 Erase Given the location of the keyvalue in the container remove the keyvalue plus any other data from the container Some container operations in the standard library include a nd operation within the insert or erase function Data Structures Analysis 0 We will ll in the table below with the costs of operations making the distinction between averagecase and worst case numbers of operations as necessary 0 In studying these remember that binary search trees are the data structure underlying the std map and std set containers and linked lists underly the std list Stacks and Queues 0 One way to obtain computational efficiency is to consider a simpli ed set of operations 0 Stacks allow access insertion and deletion from only one end called the top 7 There is no access to values in the middle of a stack 7 Stacks may be implemented ef ciently in terms of vectors and lists although vectors are preferrable 7 All stack operations are 01 0 Queues allow insertion at one end called the back and removal from the other end called the front 7 There is no access to values in the middle of a queue 7 Queues may be implemented ef ciently in terms ofa list Using vectors for queues is also possible but requires more work to get right 7 All queue operations are 01 0 Stacks and queues are covered in this week s lab Hidden Costs 0 Linked lists std list and binary search trees including std set and std map include dynamic memory allocation for each insert and for each erase o std vector occasionally re allocates the underlying array doubling it in size and copying all of values stored in the vector 0 Memory management operations tend to be substantially more expensive than ordi nary77 operations 0 We will do some simple analysis to show that the vector operations are not as expensive as they initially sound 0 The bottom line is that the hidden costs of memory management make vectors more favorable than the order notation analyis might otherwise show More Advanced Data Structures 0 Balanced binary search trees remove the worst case behavior of binary search trees by rotating and rebalancing the trees to ensure that DH OJ The non decreasing ordering is maintained The worst case height of the tree is Olog N making the primary operations each Olog N Red black trees are one such balanced tree and are the basis for std set and std map 0 Hash tables break the Olog N barrier at the cost of worst case 0N behavior We will look at techniques for avoiding this worst case behavior except for arti cially constructed cases Ordering information is also lost in hashing 7 in fact that is the point Putting these two comments together produces the observation that hashing may be used in place of binary search trees when the ordering of keys does not matter Hashing will occupy the rest of today s lecture and Lecture 20 o Priority queues are a mixture of trees and queues where the order in which items are removed depends on a priority value77 assigned to the values as opposed to the order in which the values are inserted Hashing Priority queue operations will have a worst case time of Olog N with an average case closer to 01 Priority queues are the focus of Lecture 21 and 22 0 Given are 7 Key values perhaps with associated data values as in a map 7 A function f mapping key values to the integer range 0 N 7 1 7 A table vector or array of size N o For each key value k to be stored compute ifk and store k and its associated value at location i of the table 0 Simple example 7 Keys are just integers k values are strings s 7 fk abs k N 7 Store each pair ltksgt at table location abs kN 0 Questions 7 What is a good design for f7 the hash function 7 What happens when two keys map to the same table location This is referred to as a collision Answering these two questions will be the focus ofthe rest of our discussion on hashing 0 Applications 7 Compilers storing variable names symbol tables 7 Routing tables 7 Database indexing 7 File locations in a memory system Hashing may be used in place of balanced binary search trees when ordering of the keys is not required Hash Functions 0 Goals 7 Fast computation 7 A random7 uniform distribution of keys throughout the table7 despite the distri bution of keys that are to be stored 0 Our f k abs kN example satis es the rst requirement7 but may not satisfy the second 0 An example of a dangerous hash function on strings is to add or multiply the ascii values of the individual keys unsigned int hash string constamp k unsigned int N unsigned int value O for unsigned int i0 iltksize i value ki conversion to int is automatic return k 70 N The problem is that different permutations of the same string result in the same hash table location 0 This can be improved through multiplications that involve the position and value of the key unsigned int hash string constamp k unsigned int N unsigned int value O for unsigned int i0 iltksize i value value8 ki conversion to int is automatic return k 70 N o This is better but can be improved further The theory of good hash functions is quite involved Two Approaches to Collision Resolution Two classes of approaches to collision resolution are commonly used o In open addressing when a table location already stores a key and its associated value if any a different table location is sought in order to store the new value o In separate chaining each table location stores a list or vector of the keys and values that are hashed to that location Collision Resolution Open Addressing 0 Three approaches to handling a collision during an insert operation 7 Linear probing if i is the hash location then the following sequence of table locations is tested i1N i2N i3N until an empty location is found 7 Quadratic probing if i is the hash location then the following sequence of table locations is tested probed i1N i22N i33N i44N More generally the jth probe of the table is i c1j ng mod N where c1 and 62 are constants 7 secondary hashing when a collision occurs a second hash function is applied to compute a new table location This is repeated until an empty location is found For each of these approaches the nd operation follows the same sequence of locations as the insert operation The key value is determined to be absent from the table only when an empty location is found 0 The erase function must mark a location as formerly occupied If a location is marked empty instead nd may fail Formerly occupied locations may and should be reused but only after the nd operation has been run to completion 0 Problems with open addressing 7 Slows dramatically when the table is nearly full eg about 80 or higher This is particularly problematic for linear probing 7 Fails completely when the table is full 7 Cost of computing new hash values 0 We will investigate ways to handle the rst two problems in Lecture 20 Collision Resolution Separate Chaining 0 Each table location stores a list of keys and values hashed to it 0 Thus the hashing function really just selects the list to check 0 This works well when the number of items stored in each list is small eg an average of 1 o Other data structures such as binary search trees may be used in place of the list but these have even greater overhead considering the number of items stored Hash Tables Summary 0 Good hash function is crucial 0 Two types of collision resolution 0 Average case is 01 for insert nd and erase when CSCI1200 Computer Science II Fall 2007 Lecture 10 Linked Lists Part I Review from Lecture 9 o Returning const references to member variables provides access to important variables without the cost of copying and without the danger of allowing them to be changed 0 Lists vs vectors 0 lterators vs subscripting 0 Special properties of vector iterators o The erase function for vectors and lists 0 Sieve of Eratosthenes Today7s Class Linked Lists Part I 0 Motivation implementation of the std list container class 0 Introductory example on linked lists 0 Basic linked list operations 7 Stepping through a list 7 Push back 7 Insert 7 Remove 0 Common mistakes 101 Motivation 0 Thus far our discussion of how 1istltTgt is implemented has been only intuitive it is a chain of objects 0 Now we will look at the mechanism 7 linked lists 0 Learning this is good for V b l 1 courses where the design of novel data structures is important 102 Objects with Pointers Linking Objects o The two fundamental mechanisms of linked lists are 7 creating objects with pointers as one of the member variables7 and 7 making these pointers point to other objects of the same type 0 These mechanisms are illustrated in the following program include ltiostreamgt using namespace std template ltclass Tgt class Node I public T value Node ptr y void main 39C Nodeltintgt 11 11 new Nodeltintgt llgtvalue 6 llgtptr NULL 11 is a pointer to a nonexistent Node Create a Node and assign its memory address to 11 This is the same as llvalue NULL 0 which indicates a quotnullquot pointer Nodeltintgt q new Nodeltintgt qgtvalue 8 qgtptr NULL set ll s ptr member variable to u E q point to the same thing as variable q llgtptr q cout ltlt II1st value quot ltlt ll gtvalue ltlt quotnquot e 6 ltlt quot2nd value quot ltlt llgtptrgtvalue ltlt endl er NULL 103 De nition A Linked List 0 The de nition is recursive A linked list is either 7 Empty7 or 7 Contains a node storing a value and a pointer to a linked list 0 The rst node in the linked list is called the head node and the pointer to this node is called the head pointer The pointerls value will be stored in a variable called head 104 Visualizing Linked Lists 0 The head pointer variable is drawn with its own box It is an individual variable It is important to have a separate pointer to the rst node7 since the rst node may change 0 The objects nodes that have been dynamically allocated and stored in the linked lists are shown as boxes7 with arrows drawn to represent pointers 7 Note that this is a conceptual view only The memory locations could be anywhere7 and the actual values of the memory addresses aren t usually meaningful o The last node MUST have NULL for its pointer value 7 you will have all sorts of trouble if you donlt ensure thisl 0 You should make a habit of drawing pictures of linked lists to gure out how to do the operations 105 Basic Mechanisms Stepping Through the List 0 Weld like to write a function to determine if a particular value7 stored in x7 is also in the list 0 You can think of this as a precursor to the find function Our function isnlt yet returning an iterator7 however 0 We can access the entire contents of the list7 one step at a time7 by starting just from the head pointer 7 We will need a separate7 local pointer variable to point to nodes in the list as we access them 7 We will need a loop to step through the linked list using the pointer variable and a check on each value 106 Exercise Write isthere template ltclass Tgt bool isthereNodeltTgt head const Tamp x f 107 Basic Mechanisms Pushing on the Back 0 Goal place a new node at the end of the list 0 We must step to the end of the linked list remembering the pointer to the last node 7 This is an 0n operation and is a major drawback to the ordinary linkedlist data structure we are discussing now We will correct this drawback by creating a slightly more complicated linking structure in our next lecure 0 We must create a new node and attach it to the end 0 We must remember to update the head pointer variable s value if the linked list is initially empty 7 Hence in writing the function we must pass the pointer variable by reference 108 Exercise Write pushback template ltclass Tgt void pushback NodeltTgt amp head T constamp value f 109 Basic Mechanisms Inserting a Node 0 There are two parts to this nding the location where the insert must take place and doing the insert operation 0 We will ignore the nd for now We will also write only a code segment to understand the mechanism rather than writing a complete function 0 The insert operation itself requires that we have a pointer to the location before the insert location o If p is a pointer to this node and x holds the value to be inserted then the following code will do the insertion Draw a picture to illustrate what is happening NodeltTgt q new NodeltTgt create a new node q gt value x store x in this node q gt next p gt next make its successor be the current successor of p p gt next q make p s successor be this new node 0 Note This code will not work if you want to insert x in a new node at the front of the linked list Why not 1010 Basic Mechanisms Removing a Node 0 There are two parts to this nding the node to be removed and doing the remove operation 0 The remove operation itself requires a pointer to the node before the node to be removed 0 Removing the rst node is an important special case 1011 Exercise Remove a Node Suppose p points to a node that should be removed from a linked list7 q points to the node before 137 and head points to the rst node in the linked list Write code to remove p7 making sure that if p points to the rst node that head points to what was the second node and now is the rst after p is removed 1012 Exercise List Copy Write a recursive function to copy all nodes in a linked list to form an new linked list of nodes with identical structure and values Here s the function prototype template ltclass Tgt void CopyAllNodeltTgt oldhead NodeltTgtamp newhead 1013 Basic Linked Lists Mechanisms Common Mistakes Here is a summary of common mistakes Read these carefully7 and read them again when you have problem that you need to solve o Allocating a new node to step through the linked list only a pointer variable is needed 0 Confusing the and the gt operators 0 Not setting the pointer from the last node to NULL 0 Not considering special cases of inserting removing at the beginning or the end of the linked list 0 Applying the delete operator to a node calling the operator on a pointer to the node before it is removed Delete should be done after all pointer manipulations are completed 0 Pointer manipulations that are out of order These can ruin the structure of the linked list 1014 Looking Ahead to Lecture 19 7 Our Own List Class 0 We will alter the structure of our linked list Nodes will be templated and have two pointers7 one going forward to the successor in the linked list and one going backward to the predecessor in the linked list We will have a pointer to the beginning and the end of the list template ltclass Tgt class Node public Node nextNULL prevNULL Nodeconst Tamp v valuev nextNULL prevNULL T value NodeltTgt next NodeltTgt prev 0 Well reimplement the mechanisms discussed today and we will de ne list iterators as a class inside a class Computer Science II 7 CSci 1200 Lecture 11 Linked Lists Part 2 Review from Lecture 10 0 Introductory example on linked lists 0 Basic linked list operations 7 Stepping through a list 7 Push back 7 Insert 7 Remove 0 Common mistakes Today7s Lecture 0 Limitations of singly linked lists 0 Doubly linked lists 7 Structure 7 Insert 7 Remove 0 Our own version of the listltTgt class 0 listltTgt iterator Limitations of SinglyLinked Lists 0 We can only move through it in one direction 0 We need a pointer to the node before the node that needs to be deleted 0 Appending a value at the end requires that we step through the entire list to reach the end Generalizations of SinglyLinked Lists 0 Three common generalizations 7 Doubly linked allows forward and backward movement through the nodes 7 Circularly linked simpli es access to the tail7 when doubly linked 7 Dummy header node simpli es special case checks 0 We will only consider doubly linked7 here The Structure of DoublyLinked Lists 0 For the next few examples7 we will use the simple node class class Node public int value Node next Node prev 0 Here is a picture of a doubly linked list holding 4 integer values head tail value 13 value 1 value 3 value 9 next next next X next 0 0 prev prev prev prev 0 Note that we now assume that we have both a head pointer7 as before and a tail pointer varialole7 which stores the address of the last node in the linked list 7 This is not strictly necessary7 but it allows immediate access to the end of the list for push back operations Inserting in the Middle of a DoublyLinked List 0 Suppose we want to insert a new node containing the value 15 following the node containing the value 1 0 Suppose also that we have a temporary pointer variable7 p7 that stores the address of the node containing the value 1 0 Here s a picture of the state of affairs head P tail value 13 value 1 value 3 value 9 next next next next 0 0 PTBV prev prev prev o What must happen 7 The new node must be created7 using another temporary pointer variable to hold its address 7 Its two pointers must be assigned 7 Two pointers in the current linked list must be adjusted Which ones Assigning the pointers for the new node MUST occur before changing the pointers for the current linked list nodes 0 At this point7 we are ignoring the possibility that the linked list is empty or that p points to the tail node p pointing to the head node doesn t cause any problems 0 Exercise write the code as just described Removing from the Middle of a DoublyLinked List 0 Suppose now instead of inserting a value we want to remove the node pointed to by p the node whose address is stored in the pointer variable p head P tail value 13 value 1 value 3 value 9 next next next next 0 0 PTBV prev prev prev 0 Two pointers need to change before the node is deleted All of them can be accessed through the pointer variable p 0 Exercise write this code Special Cases of Remove o If phead and ptail7 the single node in the list must be removed and both the head and tail pointer variables must be assigned the value 0 If phead or ptail7 then the pointer adjustment code we just wrote needs to be specialized to removing the rst or last node All of these will be built into the erase function that we write as part of our chlist class The cs2list Class 7 Overview 0 We will write a templated class called cleist that implements much of the function ality of the listltTgt container and uses a doubly linked list as its internal7 low level data structure Three classes are involved 7 The node class 7 The iterator class 7 The cs2list class itself The Node Class Here s the de nition template ltclass Tgt class Node public Node next0 prev0 Node const Tamp v valuev next0 prev0 T value NodeltTgt next NodeltTgt prev o It is ok to make all members public because individual nodes are never seen outside the list class 0 Note that the constructors all initialize the pointers to 0 null The Iterator Class 7 Desired Functionality o Increment and decrement operators 7 operations on pointers o Dereferencing to access contents of a node in a list 0 Two comparison operations only operator and operator The Iterator Class 7 Implementation See code attached to the handout 0 Separate class 0 Stores a pointer to a node in a linked list 0 Constructors initialize the pointer 7 they will be called from the chlistltTgt class member functions 0 This requires that cleistltTgt be a friend class of listiteratorltTgt 7 When a class A states that another class B is a friend7 this means that when any member function in B is working with an object of type A7 the B member function has access to A s private member variables and functions 7 In our case7 this means chlistltTgt member functions have direct access to the private member variables of listiteratorltTgt objects 7 the NodeltTgt pointers 7 This is especially important for the erase and insert functions 7 Note that friendship is granted7 not claimed Now back to the details of listiteratorltTgt o operator dereferences the pointer and gives access to the contents of a node 0 The mechanision of stepping through the chain of the linked list is implemented by the increment and decrement operators 0 operator and operator are de ned and quite important No other comparison operators are allowed The cs2list class 7 Overview and Prototype Job 7 Manages the actions of the iterator and node classes 7 Maintains the head and tail pointers and the size of the list 7 Manages the overall structure of the class through member functions Three member variables head7 tail7 size Typedef for the iterator name 7 This means that the name listiteratorltTgt is not used outside the function Prototypes for member functions7 which are equivalent to the std listltTgt member functions Some things are missing7 most notably constiterator and reverseiterator cs2list class 7 Some Member Function Details Many short functions are in lined Clearly7 it must contain the big 3 copy constructor7 operator7 and destructor 7 The details ofthese are realized through the private copylist and destroylist member functions You will write one of these during lab Exercises 1 2 Write chlistltTgtz pushfront Write chlistltTgt erase CSCI1200 Computer Science II Spring 2006 Lecture 3 Strings Review from Lectures 1 and 2 Standard library and 10 streams Expressions and statements Variables objects types Loops for amp while lf else conditionals logic switch statements Arrays Functions and parameter passing value amp reference Scope Algorithm analysis and order notation What7s Next C classes and the C standard library 0 Strings o Vectors 0 Classes 0 Lists and iterators 0 Maps It will take us several weeks to cover all of this material but by the time we are done you will have much of the preparation you need to solve challenging computational problems Readings for Today 0 Accelerated C Koenig and M00 Chapters 1 and 2 0 C Programming Malik pp 399 410 31 Example from Chapter 1 Strings ask for a person s name and generate a framed greeting include ltiostreamgt include ltstringgt int main std cout ltlt quotPlease enter your first name quot std string name std cin gtgt name build the message that we intend to write const std string greeting quotHello quot name quotquot build the second and fourth lines of the output const std string spaces greetingsize const std string second quot quot spaces quot quot build the first and fifth lines of the output const std string firstsecondsize write it all std cout ltlt std endl std cout ltlt first ltlt std endl std cout ltlt second ltlt std endl std cout ltlt quot quot ltlt greeting ltlt quot quot ltlt std endl std cout ltlt second ltlt std endl std cout ltlt first ltlt std endl return 0 32 About string Objects o A string is an object type de ned in the standard library to contain a sequence of characters 0 The string type like all types including int double char float de nes an interface which includes construction initialization operations functions methods and even other typesl c When an object is created a special function is run called a constructor whose job it is to initialize the object The greeting example code exhibits three ways of constructing string objects 7 By default to create an empty string 7 With a speci ed number of instances of a single char 7 From another string 0 The notation greetingsize is a call to a function size that is de ned as a member function of the string class There is an equivalent member function called length 0 Input to string objects through streams includes the following steps 1 The computer inputs and discards white space characters one at a time until a non white space character is found 2 A sequence of non white space characters is input and stored in the string This overwrites anything that was already in the string 3 Reading stops either at the end of the input or upon reaching the next whitespace character without reading it in o The overloaded operator 7 is de ned on strings It concatenates two strings to create a third string without changing either of the original two strings o The assignment operation 77 on strings overwrites the current contents of the string This seems like a lot to remember Do I need to memorize this Where can I nd all the details on string objects pi C0 to 34 35 Short Exercises What will be the values of strings a b and c at the end of the following code fragment std string a b c std cin gtgt a gtgt b gtgt c for the input eat123 grass every good boy deserves fudge allcows Write a C code fragment that reads in two strings outputs the shorter string on one line of output and then outputs the two strings concatenated together with a space between them on the second line of output C vs Java Standard C library std string objects behave like a combination ofJava String and StringBuffer objects If you aren t sure of how a std string member function or operator will behave check its semantics or try it on small examples or both which is preferable Java objects must be created using new as in String name new StringquotChrisquot This is not necessary in C The C approximate equivalent to this example is std string namequotChrisquot On the other hand there is a new operator in C and its behavior is somewhat similar to the new operation in Java We will study it later in the semester More on Strings Strings behave like arrays when using the subscript operator 7 This gives access to the individual characters in the string 7 Subscript 0 corresponds to the rst character 7 For example given std string a Then a0 and a1 quotSusanquot u and a4 n Strings de ne a special type string sizetype which is the type returned by the string function size and length 7The 7 string sizetype is generally equivalent to unsigned int notation means that sizeitype is de ned within the scope of the string type 7 You will have compiler warnings and potential compatibility problems if you compare an int variable to a size 36 Example Problem Writing a Name Along a Diagonal We will spend the rest of lecture on the following problem read in a name and then write it along a diagonal7 framed by asterisks Here s how the program might behave What is your first name Peter 96969696969696 t We will start by solving a simpler versions and then look at two ways to solve the whole problem 37 Exercises Writing the Name Diagonally Write a program to output the name diagonally7 so that the program interaction looks like this What is your first name Juanita J Here is a start to the code include ltiostreamgt include ltstringgt using stdcin using std using std using stdstring on do QC l d int main cout ltlt quotWhat is your first name quot string first cin gtgt first Fill in here return 0 You may need to use nested for loops here7 although it is possible to use just a single loop if you exploit properties of the string class 38 Thinking About the Whole Problem Now we are better prepared to address the original problem 0 Here are the two main difficulties 7 Making sure that we can put the characters in the right places on the right lines 7 Getting the asterisks in the right positions and getting the right number of blanks on each line 0 In the previous example we addressed a simpli ed version of the rst With that practice we are ready to try the full problem and we will look at two different ways of solVing it o It is good practice in general to start by solVing simpler problems that address the core issue or issues in a larger problem 39 Basic Approach for lst Solution 0 Initial stuff read the name and output a blank line as in an earlier example 0 Let s think about the main output think of the output region as a grid of rows and columns 7 How big is this region 7 What gets output where o This leads to an implementation with two nested loops and conditionals used to guide where char acters should be printed 310 lst Solution Program diagonalname Author Chuck Stewart Purpose A program that outputs an input name along a diagonal include ltiostreamgt include ltstringgt using namespace std int main cout ltlt quotWhat is your first name quot string first cin gtgt first const string star1ine firstsize4 const string blanks firstsize2 const string emptyline 7w blanks 77 cout ltlt endl ltlt starline ltlt endl ltlt emptyline ltlt endl Output the interior of the framed greeting one line at a time The use of the while loop instead of a for loop is just for illustration purposes A for loop is a more intuitive and therefore cleaner choice here string sizetype i 0 while i lt firstsize Job of loop body is to write a row of output containing s in the first Oth and last columns the ith letter in column i2 and a blank everywhere else for string sizetype j 0 j lt firstsize4 j if j 0 II j firstsize3 else if j 12 cout ltlt firsti else cout ltlt cout ltlt endl L cout ltlt emptyline ltlt endl ltlt starline ltlt endl return 0 311 Loop Invariants 0 De nition a loop invariant is a logical assertion that is true at the start of each iteration of a loop 7 In for loops7 the start is de ned as coming after the initializationincrement and termination test but before execution of the next loop iteration 0 An invariant is stated in a comment it is not part of the actual code o It helps determine 7 The conditions that may be assumed to be true at the start of each iteration 7 What must be done in each iteration 7 What must be done at the end of each iteration to restore the invariant 0 Analyzing the code relative to the stated invariant also helps explain the code and think about its correctness 312 L Values and R Values 0 Consider the simple code string a quotKimquot string b quotTomquot a0 bEOJ String a is now quotTimquot No big deal right Wrong Let s look closely at the line a0 b0 and think about what happens In particular what is the difference between the use of a0 on the left hand side of the assignment statement and b O on the right hand side Syntactically they look the same But 7 The expression b 0 gets the char value T from string location 0 in b This is an r ualue 7 The expression a0 gets a reference to the memory location associated with string location 0 in a This is an l ualue 7 The assignment operator stores the value in the referenced memory location The difference between an r ualue and an l ualue will be especially signi cant when we get to writing our own operators 0 Anyone seen the error message non lvalue in assignment std string foo quothelloquot foo2 X cout ltlt foo X fooES cout ltlt foo 313 Ideas for a 2nd Solution Here are ideas for a second solution 0 Think about what changes from one line to the next 0 Suppose we had a blank line77 string containing only the beginning and ending asterisks and the intervening blanks c We could overwrite the appropriate blank character output the string and then restore the blank character 314 Exercise Finish the 2nd Solution include ltiostreamgt include ltstringgt using std cin using std cout using std endl using std string int main cout ltlt quotWhat is your first name quot string first cin gtgt first const string starline firstsize4 const string blanks firstsize2 const string emptyline blanks string oneline emptyline cout ltlt endl ltlt starline ltlt endl ltlt emptyline ltlt endl Fill in here cout ltlt emptyline ltlt endl ltlt starline ltlt endl return 0 315 Thinking About Problem Solving c We began by working on simpli ed versions of the problem to get a feel for the core issues 0 Then we introduced two solution approaches 7 Thinking of the output as a two dimensional grid and using logical operations to gure out what to output at each location 7 Thinking of the output as a series of strings one string per line and then thinking about the differences between lines while sometimes you struggle to come up with one c There are often many ways to solve a programming problem Sometimes you can think of several 0 When you have nished a problem or when you are thinking about programming examples it is useful to think about the core ideas used If you can abstract and understand these ideas you can later apply them to other problems CSCI1200 Computer Science II Fall 2008 Lecture 3 Classes I Review from Lecture 2 o Vectors are dynamicallysized arrays o Vectors strings and other containers should be 7 passed by reference when they are to be changed and 7 passed by constant reference when they arent If you forget the amp and pass by value the object will be copied which is expensive for containers with lots of elements Note This is unlike arrays which are not copied when passed by 1 He 0 Vectors can contain any type of objects including strings and other vectors Today7s Lecture C classes 0 Types and de ning new types 0 A Date class 0 Class declaration member variables and member functions 0 Using the class member functions 0 Class scope 0 Member function implementation 0 Classes vs structs Designing classes 31 Types and De ning New Types 0 What is a type It is a structuring of memory plus a set of operations functions that can be applied to that structured memory Examples integers doubles strings and vectors 0 In many cases when we are using a class we don7t know how that memory is structured Instead what we really think about is the set of operations functions that can be applied To clarify let s focus on strings and vectors These are classes Welll outline what we know about them 7 The structure of memory within each class object 7 The set of operations de ned 0 We are now ready to start de ning our own new types using classes 3 9 Example A Date Class 0 Many programs require information about dates Information stored about the date includes the month the day and the year 0 Operations on the date include recording it printing it asking if two dates are equal ipping over to the next day incrementing etc 33 C Classes 0 A C class consists of 7 a collection of member variables usually private and 7 a collection of member functions usually public which operate on these variables 0 public member functions can be accessed directly from outside the class 0 private member functions and member variables can only be accessed indirectly through public member functions 0 We will look at the example of the Date class declarationi 34 Using C classes 0 We have been using C classes from the standard library already this semester so studying how the Date class is used is simply a review Program datemain cpp Purpose Demonstrate use of the Date class include ltiostreamgt include quotdate hquot int main stdcout ltlt quotPlease enter today s date nquot ltlt quotProvide the month day and year II int month day year tdcin gtgt month gtgt day gtgt year Date todaymonth day year Date tomorrowtodaygetMonth today getDay todaygetYear tomorrowincrement stdcout ltlt quotTomorow is II tomorrowprint stdcout ltlt stdendl Date SallysBirthday92919 D 95 if same aytomorrow SallysBirthday stdcout ltlt quotHey tomorrow is Sally s birthdaynquot stdcout ltlt quotThe last day in this month is quot ltlt today lastDayInMonth ltlt stdendl return 0 0 Important Each object we create of type Date has its own distinct member variables 0 Calling class member functions for class objects uses the dot notationi For example tomorrow increment 0 Note We don7t need to know the implementation details of the class member functions in order to understand this example This is an important feature of object oriented programming and class design 35 Exercise Add code to datemain cpp to read in another date check if it is a leapyear and check if it is equal to tomorrow Output appropriate messages based on the results of the checks 36 Class Declaration dateh amp Implementation datecpp A Class implementation usually consists of 2 les First we ll look at the header le dateh File date h Purpose Header file with declaration of the Date class including member functions and private member variables class Date Date Dateint aMonth int aDay int aYear ACCESSURS int getDayO const int getMonth const int getYear const MUDIFIERS void setDayint aDay void setMonthint aMonth void setYearint aYear void increment other member functions that operate on date objects bool isEqualconst Dateamp date2 const same day month amp year bool isLeapYear const int lastDayInMonth const bool isLastDayInMonth const void print const output as monthdayyear private REPRESENTATION member variables int ay int month int year prototypes for other functions that operate on class objects are often included in the header file but outside of the class declaration bool sameDayconst Date ampdate1 const Date ampdate2 same day amp month And here is the other part of the Class 39 quot the 39 39 quot le datecpp File date cpp Purpose Implementation file for the Date class include ltiostreamgt include IIdate hquot using namespace std array to figure out the number of days it s used by the auxiliary function daysInMonth const int DaysInMonth13 0 31 28 31 30 31 30 31 31 30 31 30 31 DateDate default constructor day 1 month 1 year 1900 DateDateint aMonth int aDay int aYear construct from month day amp year month aMonth day aDay year aYear int Date getDay const return day in t DategetMonth const return month int DategetYear const return year void Date setDayint d day d void Date setMonthint m f month m void Date setYearint y year y void Date increment if isLastDayInMonth day else day if month month year else month 1 12 f December bool Date isEqualconst Dateamp date2 const date2getDay return day date2 day ampamp month date2 month ampamp year date2year bool DateisLeapYear cons t return year4 O ampamp year 100 0 II year400 int Date lastDayInMonth const if month 2 ampamp isLeapYear return 29 else return DaysInMonth month bool Date isLastDayInMonth const return day lastDayInMonth uses member function void Date print const std cout ltlt month ltlt quotquot ltlt day ltlt quotquot ltlt year bool sameDayconst Dateamp date1 const Dateamp date2 getMonth date2getMonth return date1getDay date2getDay ampamp date1
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'