diff options
Diffstat (limited to '02-11.md')
| -rw-r--r-- | 02-11.md | 436 |
1 files changed, 305 insertions, 131 deletions
@@ -1,134 +1,4 @@ -# 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; -} -``` +[\<- 02/09](02-09.md) --- @@ -305,4 +175,308 @@ namespace SCU_COEN79_6A{ ``` //CONSTRUCTORS template <class Item> + bag<Item>::bag(size_type initial_capacity){ + data = new Item[initial_capacity]; + capacity = initial_capacity; + used = 0; + } + + template <class Item> + bag<Item>::bag(const bag<Item>& source){ + //Library facilities used: algorithm + + data = new Item[source.capacity]; + capacity = source.capacity; + used = source.used; + std::copy(source.data, source.data + used, data); + } +``` + +- Each definition is preceded by `template <class Item>` +- Note: We do not include any `using` directive, as the implementation is in the header file + +``` + //DESTRUCTOR + template <class Item> + bag<Item>::~bag(){ + delete [] data; + } + + //MODIFICATION MEMBER FUNCTIONS + template <class Item> + typename bag<Item>::size_type bag<Item>::erase(const Item& target){ + size_type index = 0; + size_type many_removed = 0; + + while(index < used){ + if(data[index] == target){ + --used; + data[index] = data[used]; + ++many_removed; + } + else ++index; + } + + return many_removed; + } + + //other functions... +} +``` + +## Parameter Matching for Members + +- Unlike an ordinary **template functions**, the compiler is able to match a `size_type` parameter of a **member functions** with any of the usual integer arguments (such as `int` or `const int`) +- Originally: + +``` +void bag::reserve(size_type new_capacity); +``` + +- With template: + +``` +Template <class Item> +void bag<Item>::reserve(size_type new_capacity); +``` + +## Using Template Bag Class + +- When the template bag class is ready, then we can declare one bag of characters and one bag of double numbers: + +``` +bag<char> letters; //The template parameter is instantiated as a character +bag<double> score; //The template paramter is instantiated as a double +``` + +--- + +# The STL's Algorithms and Use of Iterators + +## Standard Library + +- STL is a vast library of components in C++ +- STL is based on *template* programming +- It has three main components + 1. Containers + 2. Algorithms + 3. Iterators +- All components adhere to the principles of data abstractions + +## Iterators + +- An **iterator** is any object: + - **Pointing to some element in a range of elements** (such as an array or a container) + - Has the ability to iterate through the elements of that range using a set of operations (**with at least the increment (++) and dereference (\*) operators**) +- The most obvious form of iterator is a **pointer** + - A pointer can point to elements in an **array**, and can iterate through them using the increment operator (++) + +### Standard Categories of Iterators + +- The C++ Standard specifies **fice significant categories of iterators, based on five of their capabilities** + + + +### STL Categories of Iterators + +|Iterator form |Description | +|----------------------|-------------------------------------------| +|input iterator |Read only, forward moving | +|output iterator |Write only, forward moving | +|forward iterator |Both read and write, forward moving | +|bidirectional iterator|Read and write, forward and backward moving| +|random access iterator|Read and write, random access | + +## Input Iterator + +- An input iterator is designed to read a sequence of values +- Current element of an input iterator `p` can be retrieved by using a dereferencing `*` operator such as `x = *p` +- The `++` increment operator moves the iterator forward to another item +- The end of an input iterator's elements is usually detected by comparing the input iterator with another iterator that is known to be just beyond the end of the input range +- Produced by: + - `istream_iterator`, `find()` + +## Output Iterator + +- To change the element the iterator refers to, for example: `*p = "dance"` + - The `++` increment operator moves the iterator forward to another item + - **The output operator itself cannot be used to retrieve elements** + - The output iterator's usefulness is limited to the situation where some algorithm needs to put a sequence of elements in a container or other object with an output iterator +- Produced by: + - `ostream_iterator`, `inserter()`, `front_inserter()`, `back_inserter()`, `move()` + +### Input/Output Iterator + +``` +#include <algorithm> +#include <fstream> +#include <iostream> +#include <iterator> +#include <string> +#include <vector> + +//Read a bunch of strings from a file +//sort them lexographically and print them to output stream + +using namespace std; + +main(){ + //Define a vector to store the strings received from input + vector<string> strings_v; + + //Define the filestream object used to read data from file + ifstream fin("input_file.txt"); + + //Get input stream and end of stream iterators + istream_iterator<string> fin_it(fin); + istream_iterator<string> eos; + + //Get output stream iterators + ostream_iterator<string> cout_it(cout, " "); + + //Copy elements from input to vector using copy function + copy(fin_it, eos, back_inserter(strings_v)); + + //Sort the vector + sort(strings_v.begin(), strings_v.end()); + + //Copy elements from vector to output + copy(strings_v.begin(), string_v.end(), cout_it); +} +``` + +``` +Contents of File "input_file.txt": quick brown fox jumps over the lazy dog +Output: brown dog fox jumps lazy over quick the +``` + +## Forward Iterator + +- A forward iterator `p` is an object that provides these items: + - Have all the functionality of **input iterators** + - **If they are not constant iterators**, then they also have the functionality of **output iterators** + - They are limited to one direction in which to iterate through a range (forward) + - **All standard containers support at least forward iterator types** +- Example: Iterator of a `forward_list` is a forward iterator + +### Example + +``` +#include <iostream> +#include <forward_list> + +int main(){ + std::forward_list<int> mylist(4); + + for(std::forward_list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){ + *it = rand(); + } + + std::cout << "mylist contains:"; + for(std::forward_list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){ + std::cout << '' << *it; + } + + return 0; +} +``` + +## Std::Copy Function + +``` +template <class InputIt, class OutputIt> +OutputIt copy(InputIt first, InputIt last, OutputIt d_first); +``` + +- Both InputIt and OutputIt are iterators over the same object +- The first element that is copied comes from first, and the copying continues up to (but not including) last +- The return value is an iterator that is one position beyond the last copied element in the description + +### Use of Copy Function + +``` +int numbers[7] = {0, 10, 20, 30, 40, 50, 60}; +int small[4] = {0, 0, 0, 0}; + +int *p = numbers + 2; //an iterator that starts at numbers[2] +int *mid = numbers + 6; //an iterator that starts at numbers[6] + +int *small_front = small; //an iterator that starts at small[0] + +copy(p, mid, small_front); +copy(numbers+4, numbers+7, small); +``` + +- After first copy: + + + +- After second copy: + + + +## Bidirectional Iterator + +- Has all the abilities of a forward iterator, plus it can move backgward with the `--` operator +- The `--p` operator moves the iterator `p` backward one position and returns the iterator after it has moved backward +- The `p--` operator also moves the iterator backward one position and returns a copy of the iterator before it moved +- Produced by: + - `list`, `set`, `multiset`, `map`, `multimap` + +### Example + +``` +#include <iterator> //std::insert_iterator +#include <list> //std::list +#include <algorithm> //std::copy + +int main(){ + std::list<int> foo, bar; + for(int i = 1; i <= 5; i++){ + foo.push_back(i); + bar.push_back(i*10); + } + + std::list<int>::iterator it = foo.begin(); //returns a bidirectional iterator + + std::copy (bar.begin(), bar.end(), it); + std::cout << "foo:"; + for(std::list<int>::iterator it=foo.begin(); it != foo.end(); ++it){ + std::cout << '' << *it; + } + + std::cout << '\n'; + return 0; +} +``` + +``` +Output: +foo: 10 20 30 40 50 +``` + +## Random Access Iterator + +- Has all the abilities of bidirectional iterators +- The term random access refers to the ability to quickly access any randomly selected location in a container +- A random access iterator `p` can use the notation `p[n]` to provide access to the item that is `n` steps in front of the current item +- Therefore, distant elements can be accessed directly by applying an offset value to an iterator without iterating through all the elements in between +- Produced by: ordinary pointers, `vector`, `deque` +- Example: `p[0]` is the current item, `p[1]` is the next item, and so on + +## Array Iterator + +- C++ allows any pointer to an element in an array to be used as if it were a random access iterator +- The "current item" of such a pointer is the array element it points to +- The `++` and `--` operators move the pointer forward or backward one spot +- For a pointer `p`, the notation `p[i]` refers to the item that is `i` steps ahead of the current item +- Since a pointer to an array is a random access iterator, we can use these pointers in Standard Library functions that expect an iterator + +## Iterator Invalidation Rules +- **Insert an element** + - vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) + - list: all iterators and references unaffected +- **Erase an element** + - vector: every iterator and reference after the point of erase is invalidated + - list: only the iterators and references to the erased element is invalidated |