diff options
Diffstat (limited to '02-11.md')
| -rw-r--r-- | 02-11.md | 308 |
1 files changed, 308 insertions, 0 deletions
diff --git a/02-11.md b/02-11.md new file mode 100644 index 0000000..5de7745 --- /dev/null +++ b/02-11.md @@ -0,0 +1,308 @@ +# Template Functions + +- Introduction of templates, which are C++ feature that easily permits the reuse of existing code for new purposes +- Shows how to implement and use the simplest kinds of templates: **template functions** + +## Finding the Maximum of Two Numbers + +### Finding the Maximum of Two Integers + +- Here's a small function that you might write to find the maximum of two integers + +``` +int maximum(int a, int b){ + if(a > b) return a; + else return b; +} +``` + +### Finding the Maximum of Two Doubles + +- Here's a small function that you might write to find the maximum of two double numbers + +``` +int maximum(double a, double b){ + if(a > b) return a; + else return b; +} +``` + +### Finding the Maximum of Two Knafns + +- Here's a small function that you might write to find the maximum of two knafns + +``` +int maximum(knafn a, knafn b){ + if(a > b) return a; + else return b; +} +``` + +### One Hundred Million Functions... + +- Suppose your program uses 100,000,000 different data types, and you need maximum function for each... + +### A Template Function for Maximum + +- This template function can be used with many data types + +``` +template<typename Item> +Item maximum(Item a, Item b){ + if(a > b) return a; + else return b; +} +``` + +- When you write a template function, you choose a data type for the function to depend upon... +- A template prefix is also needed immediately before the function's implementation + +### Using a Template Function + +- Once a template function is defined, it may be used with any adequate data type in your program... + +``` +cout << maximum(1, 2); +cout << maxiumum(1.3, 0.9); +``` + +## Multi Parameter Templates + +``` +int array_max(int data[], size_t n){ + size_t i; + int answer; + + assert(n > 0); + answer = data[0]; + for(i = 1; i < n; i++){ + if(data[i] > answer) answer = data[i]; + return answer; +} +``` + +### Solution 1 + +``` +template <typename Item> +Item array_max(Item data[], size_t n){ + size_t i; + Item answer; + + assert(n > 0); + answer = data[0]; + for(i = 1; i < n; i++){ + if(data[i] > answer) answer = data[i]; + return answer; +} +``` + +- What are the problems? + - `size_t` is not generic, so passing, for example, a `const size_t` will return an error + +### Examples + +``` +const size_t SIZE = 5; +double data[SIZE]; +//... + +cout << array_max(data, SIZE); +cout << array_max(data, 5); + +template <typename Item> +Item array_max(Item data[], size_t n); +``` + +### Solution 2 + +``` +template <typename Item, typename Sizetype> +Item array_max(Item data[], Sizetype n){ + size_t i; + Item answer; + + assert(n > 0); + answer = data[0]; + for(i = 1; i < n; i++){ + if(data[i] > answer) answer = data[i]; + return answer; +} +``` + +--- + +# Template Classes + +- A template function is a function that depends on an underlying data type +- In a similar way, when a class depends on an underlying data type, the class can be implemented as a **template class** +- For example, a single program can use a bag of integers, and a bag of characters, and a bag of strings, and... +- You do not have to determine the data type of a data structure when developing a code + +## Bag Example + +### Syntax For Template Classes + +``` +class bag{ + public: + typedef int value_type; + typedef size_t size_type; + ... +``` + +``` +template <typename Item> +class bag{ + public: + ... +} +``` + +- `template <typename Item>` is the template prefix, and it warns the compiler that the following definition will use an unspecified data type called `Item` + +### Template Class Functions + +- The bag's `value_type` is now dependent on the `Item` type +- **Outside the template class definition** some rules are required to tell the compiler about the dependency: + - The template prefix `template <class Item>` is placed immediately before each function prototype and definition + - Outside the template class definition, each use of the class name (such as `bag`) is changed to the template class name (such as `bag<Item>`) + - Within a class definition or within a member function, we can still use the bag's type names, such as `value_type` or `size_type` + - Outside of a member function, to use a type such as `bag<Item>::size_type`, we must add a new keyword `typename`, writing the expression `typename bag<Item>::size_type` + +### Example 1 + +- For our **original class**, the function's implementation began this way: + +``` +bag operator +(const bag& b1, const bag& b2) ... +``` + +- For the **template class**, the start of the implementation is shown here: + +``` +template <class Item> +bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2); +... +``` + +### Example 2 + +``` +bag::size_type bag::count(const value_type& target) const; +``` + +- Outside of a member function, you must put the keyword `typename` in front of any member of a template class is the name of a data type + +``` +template <class Item> +typename bag<Item>::size_type bag<Item>::count (const Item& target) const; +``` + +## Summary: Item and typename + +|In the original Bag class |In the template bag class | +|-----------------------------------|-----------------------------| +|value_type |Item | +|size_type (inside member function) |size_type | +|size_type (outside member function)|typename bag<Item>::size_type| + +## Header File Changes + +- **In the header file**, you place the documentation and the prototypes of the functions; **then you must include the actual implementations of all the functions** + - The reason for the requirement is to make the compiler's job simpler + - **An alternative**: You can keep the implementations in a separate implementation file, but place an `include` directive at the bottom of the header file to pick up these implementations + - We include the following line at the end of the header file: + +``` +#include "bag4.template" //Include the implementation +``` + +## Do Not Place using Directive + +- Because a template class has its implementation included in the header file, we must not place any `using` directives in the implementation +- Otherwiser, every program that uses our template class will inadvertently use the `using` directives + +## Bag Class Header and Implementation Files + +### Header File for the Bag Template Class + +``` +#ifndef SCU_COEN79_BAG4_H +#define SCU_COEN79_BAG4_H +#include <cstdlib> //Provides size_t + +namespace scu_coen79_6A{ + template <class Item> + class bag{ + public: + //TYPEDEFS and MEMBER CONSTANTS + typedef std::size_t size_type; + static const size_type DEFAULT_CAPACITY = 30; + + //CONSTRUCTORS and DESTRUCTORS + bag(size_type initial_capacity = DEFAULT_CAPACITY); + bag(const bag& source); + ~bag(); + + //MODIFICATION MEMBER FUNCTIONS + size_type erase(const Item& target); + bool erase_one(const Item& target); + void insert(const Item& entry); + void operator =(const bag& source); + void operator +=(const bag& addend); + void reserve(size_type capacity); + + //CONSTANT MEMBER FUNCTIONS + size_type count(const Item& target) const; + Item grab() const; + size_type size() const {return used;}; + + private: + Item *data; //Pointer to partially filled dynamic array + size_type used; //How much of array is being used + size_type capacity; //Current capacity of the bag + }; +``` + +- Inside the template class definition: Compiler knows about the dependency on `Item` type +- Some rules are required outside of the template class definition: + - `template<class Item>` is placed immediately before each function prototype and definition + - Each use of the class name is changed to the template class name (`bag<Item>`) + - We should then include the implementation of the template in the header file (needed by most compilers) + - Instead of that: we keep the implementation in a separate file + +``` +//NONMEMBER FUNCTIONS +//originally: bag operator +(const bag& b1, const bag& b2); + +template <class Item> +bag<Item operator +(const bag<Item>& b1, const bag<Item>& b2); + +#include "bag4.template" +#endif +``` + +### Implementation File for the Bag Template Class + +``` +#include <algorithm> //provides copy +#include <cassert> //provides assert +#include <cstdlib> //provides rand + +namespace SCU_COEN79_6A{ + + //MEMBER CONSTANTS + template <class Item> + const typename bag<Item>::size_type bag<Item>::DEFAULT_CAPACITY; +``` + +- Some compilers require the default parameters to be both in the prototype and implementation +- Remeber that: + - To refer to `size_type` outside a member function: `typename bag<Item>::size_type` +- Each definition is preceded by `template <class Item>` + +``` + //CONSTRUCTORS + template <class Item> + |