path: root/01-19.md

[\<- 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 **occurrences** 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

---

[01/21 ->](01-21.md)