Lecture 25OutlineLinear Search 1Linear Search 2Linear Search 3Linear Search 4Template Functions 1Template Functions 2Template Header FilesIn-class Exercises 1In-class Exercises 2In-class Exercises 3Submitting In-class ExercisesFriday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 1Lecture 25Log into Linux. Copy files on csserver from /home/hwang/cs215/lecture25/*.*Reminder: Homework 6 due on Monday.Questions?Friday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 2OutlineTemplate functionsFriday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 3Linear SearchConsider a linear search function for an array of integers over a range [first, last) that returns the index of the search target, if it is in the array, or last, if the search target is not in the array.AnalysisObjects Type Movement Namearray of values int [ ] received arrindex of lower bound int received firstindex of upper bound int received targetsearch target int received targetindex of target int returned positionFriday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 4Linear SearchDesign1. For position from first to last-1 do 1.1. If arr[position] equals the target then 1.1.1. Return position2. Return lastCodeint LinearSearch (const int arr[], int first, int last, int target){ for (int position=first; position < last; position++) if (arr[position] == target) // found target return position; return last;}Friday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 5Linear SearchSuppose we want to use this function to search an array of strings? doubles? Dates?Would have to change the type of arr and target. Nothing changes in the design. The only characteristic of the element type needed is equality operator==.Could use a value_type typedeftypedef int value_type;int LinearSearch (const value_type arr[], int first, int last, value_type target){ ... }Friday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 6Linear SearchBut what if we want to use this function for both integers and strings in the same program?C++ allows function overloading, so we could write two functions, one with int and one with string as the element type.Then if we want to search an array of Dates, we need to add another copy with just the two type changes. Duplicate code should be avoided.What we need is a type parameter (vs. a data parameter). C++ allows type parameters by using a template.Friday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 7Template FunctionsTemplate function syntax is:template <typename T>int LinearSearch (const T arr[], int first, int last, const T & target){ ... }Note: the textbook uses class rather than typename. Use typename as it is the standard way to do this.Note: since we do not know if T is an object type, we pass the received target using a const reference parameterFriday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 8Template FunctionsTemplate functions are instantiated wherever the function is called. This means an actual type is plugged in for T, and the code for that version of the template function is generated.The type that is plugged into the template is determined by the type of the arguments.See files template-examples.cpp, templates.h, and Makefile.inclass25Friday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 9Template Header FilesSince the compiler must have the full implementation to instantiate a version of a template, the header file contains the entire template (not just a prototype), and there is no corresponding .cpp source file.Friday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 10In-class ExercisesIn templates.h, write a template function PrintArray that receives an array of values and the number of values in the array. This function should display each element to the screen on a separate line.Add code to the end of template-examples.cpp to use PrintArray to print out the three arrays (intList, realList, and strList).Friday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 11In-class ExercisesIn templates.h, write a template function FindIndexOfMinimum that receives an array of values and the number of values in the array. The function is to return the index of the minimum value in the array (as determined by operator<).Add code to the end of templates-examples.cpp to use FindIndexOfMinimum to display the minimum value in each array.Friday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 12In-class ExercisesIn templates.h, write a template function Sort that receives and passes back an array of values, and receives the number of values in the array. This function is to sort the array using a sorting algorithm of your choice.Add code at the end of template-examples.cpp to use Sort to sort the three arrays and then display them again using PrintArray.Friday, October 22 CS 215 Fundamentals of Programming II - Lecture 25 13Submitting In-class ExercisesWhen you have completed the in-class exercises, make sure you have put your name in each file, then tar together files templates.h and template-examples.cppSubmit this exercise to the submission system no later than class time on Monday (11am). The system only will compile the files; it will not run the
View Full Document
Unlocking...