INB371 Week 5 Lecture

5 Pages
Unlock Document

Malcolm Corney

INB371 Week 5 Lecture Overview Templates Arrays and Containers Algorithms and Efficiency Classes Templates Templates are a powerful feature which allows you to define functions and define classes. Last week we looked at IntVector, IntStack, IntQueue. Writing an implementation for every container of every type would be time consuming. Instead we can make a template which takes a generic type, to allow you to put any type into it. The common form of template spec is 'template ', placeholder being used through the template and when used properly, will be replaced with the proper datatype. Templates can be used before a function definition to create a generic colection of functions. template ValueType maximum(ValueType v1, ValueType v2) { return (v1 > v2) ? v1 : v2; a template for a function which will find the return the bigger type. The compiler generates the different code for the different versions of maximum, and would only then be able to used on types that you can use the > operator. Templates are more commonly used in defining generic classes. THe template keyword must appear before the class definition and all implementations of the member functions. THE COMPILER CANNOT PROCESS GENERIC CLASSES UNLESS IT HAS ACCESS TO BOTH THE INTERFACE AND IMPLEMENTATION AT THE SAME TIME. If we were to redefine IntStack to a template version of Stack, you'd ad the template keyword to the interface just before the class definition. e.g. template then you'd change every mention of the original type (int), and change it to ElemType, e.g. void push (ElemType value). Implementations need to be included as part of the stack.h header. code in lecture slides NOTE: Using the C++ 'pre-compiler', you can actualy #include header files into sections of another header, such as using #include "stackpriv.h" in the 'private' declaration, which would put everything in stackpriv.h into the private declaration section. When working with abstract classes, you must be careful how objects behave when they're copied or passed by value to parameters in methods. When copying objects, typically we want to copy the underlying data, not just the directly acessible fields in the thing. Shallow vs Deep copy Suppose you have a Stack containing 3 elements. You have your list and count variables, which describe the list, and then 3 'cells' containing the value and link. Creating a 'shallow copy' would copy the 'list' and 'count' veriables from the original. Now you have two pointers (list) pointing to the first 'cell' in the stack. A deep copy, on the other hand, copies the contents of the linked list, but also creates a second independent structure of cells with different memory addresses. To ensure deep copying is done correctly, the operator 'operator=' which takes care of assigning one object to another, and a 'copy' constructor, which takes care of by-value passing with parameters. DEFINITION Copy Constructor Stack(const Stack& src); // takes a constant stack Stack operator=(Stack& src); // returns a Stack copy of the original. Body of functions not shown - contact Malcolm (lecturer) if you would like them. When working with arrays and containers, it's sometimes better to use pointers to objects as the element rather than objects. Consider a Deck of Card, with respect to shuffling. A card object would have a Card(Rank, Suit) constructor, and thne a private enum for Rank and another for Suit. If you were to then create a Deck class, you'd have a Deck() constructor, a ~Deck() destructor, a Shuffle method, and a DealNextCard() method which returns a Card. private fields are a Card pointer to an array of cards, and a counter with cards dealt. Now for implementing. the Deck() constructor would create a new array of cards under the 'cards' pointer declared in private, 'cards = new Card[CARDS_IN_DECK]'. Then you'd use a for loop of rank, inside a for loop of suit. Inside these for loops you'd have card[suit * 13 + rank] = Card((Rank)rank, (Suit)suit);. Suit and Rank are in () because you're casting it back to the enumeration type in Card. The destructor simply deletes the array of cards. 'delete[] cards'. The Shuffle() method creates a new random object, and then generates a random integer between 0 and CARDS_IN_DECK-1. Then, in a for loop which starts at 0 and ends in MAX_SHUFFLES , You'd pick two cards from your cards array using the Random object (cards[random]), and swap them. You can do this with a Dynamic arr
More Less

Related notes for INB221

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.