diff options
Diffstat (limited to '01-19.md')
| -rw-r--r-- | 01-19.md | 515 |
1 files changed, 515 insertions, 0 deletions
diff --git a/01-19.md b/01-19.md new file mode 100644 index 0000000..5b32d08 --- /dev/null +++ b/01-19.md @@ -0,0 +1,515 @@ +[\<- 01/14](01-14.md) + +--- + +# Operator Overloading (cont.) + +## Friend Functions + +- A **friend function** is a function that **is not a member function**, but that still has access to the private members of the objects of a class +- To declare a friend function, the function's prototype is placed in a class definition, preceded by the keyword `friend` + +``` +class point{ + + public: + //... + //FRIEND FUNCTIONS + friend istream& operator >>(istream& ins, point& target); + + private: + //... +}; +``` + +- Even though the prototypes for friend functions appear in the class definition, **friends are not member functions** +- Therefore, **it is not activated by a particular object of a class** +- All of the information that the friend function manipulates must be present in its parameters +- Friendship may be provided to any function, not just to operator functions +- Friendship should be limited to functions that are written by the programmer who implements the class + +``` +#include <iostream> +using namespace std; + +class Box{ + double width; + + public: + friend void printWidth(Box box); + void setWidth(double wid) {width = wid;}; +}; + +void printWidth(Box box){ + cout << "Width of box : " << box.width << endl; +} + +int main(){ + Box box; + box.setWidth(10.0); + + printWidth(box); + + return 0; +} +``` + +--- + +# The Standard Template Library (STL) and the Pair Class + +- It is important for you to understand how to build and test your own data structures +- However, you'll find that a suitable data structure has already been built for you to use in an application +- In C++, **a variety of container classes**, called the **Standard Template Library (STL)**, are available + +## The Pair Class + +- Each pair object **can hold two pieces of data** +- Example: integer and a double number; or a char and a bool value; or even a couple of throttles + +``` +#include <utility> //provides the pair class +using namespace std; //The pair is part of the std namespace + +int main(){ + pair<int, double> p; + p.first = 42; //first is the member variable for the int piece + p.second = 9.25; //second is the member variable for the double + //... +} +``` + +``` +template<class T1, class T2> +struct pair; +``` + +- This class couples together a pair of values, which may be of different types (T1 and T2) +- The individual values can be accessed through its **public members** `first` and `second` +- The **data types of these two pieces are specified in the angle brackets**, as part of the object's declaration +- We'll see more of these angle brackets later. They are called the **template instantiation** + +``` +template<class T1, class T2> +pair<T1, T2> make_pair(T1 x, T2 y); +``` + +- Constructs a pair of object with its first element set to `x` and its second element set to `y` + +- Example: + +``` +#include <utility> //std::pair +#include <iostream> //std::cout + +int main(){ + std::pair<int, int> foo; + std::pair<int, int> bar; + + foo = std::make_pair(1, 2); + bar = std::make_pair(0.5, 'B'); //implicit conversion + + std::cout << "foo: " << foo.first << ", " << foo.second << '\n'; + std::cout << "bar: " << bar.first << ", " << bar.second << '\n'; + + return 0; +} +``` + +- Output: + +``` +foo: 1, 2 +bar: 0, 66 +``` + +- Note: 66 is the decimal ASCII number of 'B' + +- Another Example: + +``` +#include <utility> //std::pair, std::make_pair +#include <string> //std::string +#include <iostream> //std::cout + +int main(){ + std::pair<std::string, int> university, myuniversity; + + university = std::make_pair("SCU", 95053); + + myuniversity = university; + + std::cout << "My University: " << myuniversity.first << '\n'; + std::cout << "My University Zip: " << myuniversity.second << '\n'; + return 0; +} +``` + +- Output: + +``` +My University: SCU +My University Zip: 95053 +``` + +--- + +# Summary + +- Object-oriented programming (OOP) supports **information hiding** by placing data in packages called **objects** +- Objects are implemented via **classes** +- **Member functions** enable the manipulation of objects +- An **Abstract Data Type (ADT)/data structure/class:** A new data type, together with the functions to manipulate the type + - The term **abstract** refers to the fact that we emphasize the abstract specification of **what has been provided, disassociated from any actual implementation** +- Information hiding is provided by **private** member variables +- Declaring a function as a **friend function** enables access to private members +- A **constructor** is a member function that is automatically called to initialize a data structure +- Using **namespace** avoids conflicts between different items with the same name +- **Header file** includes documentation and class definition +- **Implementation file** includes the implementation of the member functions +- C++ provides three common kinds of parameters: **value parameters, reference parameters, const reference parameters** +- C++ allow you to **overload operators** for your new data structures +- Many built-in classes are provided by the **Standard Template Library** + +--- + +# Data Structures and Other Objects Using C++ + +## Container Classes + +- A **container class** is a data type that is capable of holding a collection of items + +### Bags + +- For the first example, think about a bag +- Inside the bag are some numbers + +### Summary of the Bag Operations + +1. A bag can be put in its **initial state**, which is an empty bag +2. Numbers can be **inserted** into the bag +3. You may check how many **occurences** of a certain number are in the bag +4. Numbers can be **removed** from the bag +5. You can check **how many** numbers are in the bag + +### The Bag Class + +- C++ classes can be used to implement a container class such as a bag +- The class definition includes: + - The heading of the definition + - A constructor prototype + - Prototypes for public member functions + - Private member variables + +``` +class bag{ + + public: + bag(); + void insert(...); + void remove(...); + ...and so on + + private: + We'll look at private members later +}; +``` + +### Using the Bag in a Program + +- Here is typical code from a program that uses the new bag class: + +``` +bag ages; + +//Record the ages of three children +ages.insert(4); +ages.insert(8); +ages.insert(4); +``` + +### The Header File and Implementation File + +- The programmer who writes the new bag class must write two files: + - `bag1.hxx`, a header file that contains documentation and the class definition + - `bag1.cxx`, an implementation file that contains the implementations of the bag's member functions + +### Documentation for the Bag Class + +- The documentation gives **prototypes and specifications** for the bag member functions +- Specifications are written as **precondition/postcondition** contracts +- Everything needed to **use** the bag class is included in this comment + +### The Bag's Class Definition + +- After the documentation, the header file has the class definition that we've seen before + +### The Implementation File + +- As with any class, the actual definitions of the member functions are placed in a separate implementation file +- The **definitions** of the bag's member functions are in `bag1.cxx` + +### Implementation Details + +- The entries of a bag will be stored in the front part of an array, as shown in this example + +|[0]|[1]|[2]|[3]|...| +|---|---|---|---|---| +|4 |8 |4 | | | + +- We also need to keep track of how many numbers are in the bag + - An integer to keep track of the bag's size: `int size` + +### Bag: Private Members (1st Try) + +- One Solution: + +``` +class bag{ + + public: + ... + + private: + int data[20]; + size_t count; +}; +``` + +- `size_t` is a non-negative integer, defined at the machine level + +### An Example of Calling Insert + +``` +void bag::insert(int new_entry) +``` + +- Before calling insert, we might have this bag b: + - `b.count: 2` + - `b.data: ` + +|[0]|[1]|[2]|...| +|---|---|---|---| +|8 |4 | | | + +### Bag: Private Members (2nd Try) + +- A more flexible solution: + +``` +class bag{ + + public: + static const size_t CAPACITY = 20; + + private: + int data[CAPACITY]; + size_t count; +}; +``` + +### An Example of Calling Insert + +- We make a function call `b.insert(17)` + - What values will be in `b.data` and `b.count` after the member function finishes? + - After calling `b.insert(17)`, we will have this bag b: + - `b.count: 3` + - `b.data: ` + +|[0]|[1]|[2]|...| +|---|---|---|---| +|8 |4 |17 | | + +### Pseudocode for bag::insert + +1. `assert(size() < CAPACITY);` +2. Place `new_entry` in the appropriate location of the data array +3. Add one to the member variable count + +``` +data[count] = new_entry; +++count; + +//alternatively: +data[count++] = new_entry; +``` + +### Other Kinds of Bags + +- In this example, we have implemented a bag containing **integers** +- But we could have had a bag of **float numbers**, a bag of **characters**, a bag of **strings**... + +### A typedef for value_type + +- Instead of forcing the bag to always include integers, we use the name `value_type` for the data type of the items in a bag + +``` +class bag{ + + public: + typedef int value_type; + ... +}; +``` + +- Bag functions can use the name `value_type` as a synonym for the data type `int` +- Other functions, which are not bag member functions, can use the name `bag::value_type` as the type of the items in a bag + +### Implementation: A typedef for size_type + +- In addition to the `value_type`, our bag defines another data type that can be used for variables that keep track of how many items are in a bag +- This type will be called `size_type`, with its definition near the top of the bag class definition: + +``` +class <Name of the class>{ + + public: + typedef <A data type such as int or double> <A new name>; + typedef <an integer type of some kind> size_type; + ... +}; +``` + +### Specification - The std::size_t Data Type + +- The data type `size_t` is an integer data type that can **hold only non-negative numbers** +- C++ implementation guarantees that the values of the `size_t` type are sufficient to hold the size of any variable that can be declared on your machine + +``` +class bag{ + + public: + typedef int value_type; + typedef std::size_t size_type; + ... +}; +``` + +- To use `size_t` in a header file, we must include `cstdlib` and use the full name `std::size_t` +- The actual size of `size_t` is platform-dependent: On 32-bit and 64-bit systems `size_t` will take 32 and 64 bits, respectively + +### The Header File and Implementation File + +- The programmer who writes the new bag class must write two files: + - `bag1.hpp`, a header file that contains documentation and the class definition + - `bag1.cxx`, an implementation file that contains the implementations of the bag's member functions + +``` +//FILE: bag1.h +//CLASS PROVIDED: bag (part of the namespace scu_coen79_3) + +//TYPEDEF and MEMBER CONSTANTS for the bag class: +//typedef int value_type +//bag::value_type is the data type of the items in the bag. It may be any of the C++ built-in types (int, char, etc.), or a class with a default constructor, an assignment operator, and operators to test for equality (x == y) and non-equality (x != y) + +//typedef size_t size_type +//bag::size_type is the data type of any variable that keeps track of how many items are in a bag + +//static const size_type CAPACITY = 20 +//bag::CAPACITY is the maximum number of items that a bag can hold + +//CONSTRUCTOR for the bag class: +//bag() +//Postcondition: The bag has been initialized as an empty bag + +//MODIFICATION MEMBER FUNCTIONS for the bag class: +//size_type erase(const value_type& target); +//Postcondition: All copies of target have been removed from the bag +//Postcondition: The return value is the number of copies removed (which could be zero) + +//bool erase_one(const value_type& target) +//Postcondition: If target was in the bag, then one copy has been removed; otherwise the bag is unchanged +//Postcondition: A true return value indicates that one copy was removed; false indicates that nothing was removed + +//void insert(const value_type& entry) +//Precondition: size() < CAPACITY +//Postcondition: A new copy of entry has been added to the bag + +//void operator +=(const bag& addend) +//Precondition: size() + addend.size() <= CAPACITY +//Postcondition: Each item in addend has been added to this bag + +//CONSTANT MEMBER FUNCTIONS for the bag class: +//size_type size() const +//Postcondition: The return value is the total number of items in the bag + +//size_type count(const value_type& target) const +//Postcondition: The return value is number of times target is in the bag + +//NONMEMBER FUNCTIONS for the bag class: +//bag operator +(const bag& b1, const bag& b2) +//Precondition: b1.size() + b2.size() <= bag::CAPACITY +//Postcondition: The bag returned is the union of b1 and b2 + +//VALUE SEMANTICS for the bag class: +//Assignments and the copy constructor may be used with bag objects +``` + +### The Invariant of a Class + +- We need to state **how the member variables of the bag class are used** to represent a bag of items +- There are two rules for our bag implementation + - The number of items in the bag is stored in the member variable `used` + - For an empty bag, we do not care what is stored in any of `data`; for a non-empty bag, the items in the bag are stored in `data[0]` through `data[used-1]`, and we don't care what is stored in the rest of data +- The rules that dictate how the member variables of a class represent a value (such as a bag of items) are called the **invariant** of the class +- With the exception of the constructors, each function depends on the invariant being valid when the function is called +- Check out the wikipedia article on class invariant + +### += Operator + +``` +void bag::operator +=(const bag& addend){ + size_type i; //an array index + + assert(size() + addend.size() <= CAPACITY); + for(i = 0; i < addend.used; ++i){ + data[used] = addend.data[i]; + ++used; + } +} +``` + +- If we activate `b+=b` then the private member variable used is the same variable as `addend.used` +- Each iteration of the loop adds 1 to `used`, and hence `addend.used` is also increasing, and the loop never ends +- What is the solution? + +### += Correct Implementation + +- The implementation uses the `copy` function from the `<algorithm>` Standard Library + +``` +void bag::operator +=(const bag& addend){ + + assert(size() + addend.size() <= CAPACITY); + copy(addend.data, addend.data + addend.used, data + used); + used += addend.used; +} +``` + +### Time Analysis for the Bag Functions + +|Operation |Time Analysis | +|-------------------|------------------------------------------------| +|Default constructor|O(1) (Constant time) | +|count |O(n) (n is the size of the bag) | +|erase_one |O(n) (Linear time) | +|erase |O(n) (Linear time) | +|+= another bag |O(n) (n is the size of the other bag) | +|b1 + b2 |O(n1 + n2) (n1 and n2 are the sizes of the bags)| +|insert |O(1) (Constant time) | +|size |O(1) (Constant time) | + +- `erase_one` sometimes requires fewer than n x (number of statements in the loop); however, this does not change the fact that the function is O(n) + - In the worst case, the loop does execute a full `n` iterations, therefore the correct time analysis is no better than O(n) +- Several of the other bag functions do not contain any loops at all, and do not call any functions with loops + - Example, when an item is added to a bag, the new item is always placed at the end of the array + +## Summary + +- A **container class** is a class where each object contains a collection of items + - Examples: Bags and sequences classes +- `typedef` statement makes it easy to alter the data type of the underlying items +- The simplest implementations of container classes use a **partially filled array**, which requires each object to have at least two member variables: + - The array + - A variable to keep track of how much of the array is being used +- At the top of the implementation file: When you design a class, always make an explicit statement of the rules (**invariant of the class**) that dictate how the member variables are used |