[\<- 01/28](01-28.md)

---

## The Bag Class with Dynamic Arrays (cont.)

### Header File for the Bag Class with a Dynamic Array

```
// FILE: bag2.h (part of the namespace scu_coen79_4)
// CLASS PROVIDED: bag
#ifndef SCU_COEN79_BAG2_H
#define SCU_COEN79_BAG2_H
#include <cstdlib> //provides size_t

namespace scu_coen79_4{

	class bag{

		public:
			//TYPEDEFS and MEMBER CONSTANTS
			typedef int value_type;
			typedef std::size_t size_type;
			static const size_type DEFAULT_CAPACITY = 30;

			//CONSTRUCTOR and DESTRUCTOR
			bag(size_type initial_capacity = DEFAULT CAPACITY);
			bag(const bag& source); //copy constructor
			~bag(); //destructor

			//MODIFICATION MEMBER FUNCTIONS
			void reserve(size_type new_capacity); //increases the bag's current capacity to the new capacity
			bool erase_one(const value_type& target);
			size_type erase(const value_type& target);
			void insert(const value_type& entry); //inserts a new copy of entry to the bag
			void operator +=(const bag& addend);
			void operator =(const bag& source); //enables a bag to have same items and capacity as source

			//CONSTANT MEMBER FUNCTIONS
			size_type size() const {return used;};
			size_type count(const value_type& target) const;

		private:
			//Pointer to partially filled dynamic array
			value_type *data;

			//How much of array is being used
			size_type used;

			//Current capacity of the bag
			size_type capacity;
	};

	//NONMEMBER FUNCTIONS for the bag class
	bag operator +(const bag& b1, const bag& b2);
}

#endif
```

### The Revised Bag Class - Implementation

- Three functions are particularly important:
	1. Constructors
	2. Destructor
	3. Assignment operator
- These three member functions are always needed when a class uses dynamic memory

- **The constructors**: Each of the constructors is responsible for setting up the three private member variables in a way that satisfies the invariant of the dynamic bag class
- **Constructor**:

```
bag::bag(size_type initial_capacity){
	data = new value_type[initial_capacity];
	capacity = initial_capacity;
	used = 0;
}
```

- `initial_capacity` tells how many items to allocate for the dynamic array

- **Copy Constructor**:

```
bag::bag(const bag& source){
	//Library facilities used: algorithm

	data = new value_type[source.capacity];
	capacity = source.capacity;
	used = source.used;
	copy(source.data, source.data + used, data);
}
```

- `copy()` takes in three arguments:
	- The start
	- The end
	- The destination
- The capacity of the dynamic array is the same as the capacity of the bag that is being copied
- After the dynamic array has been allocated, the items may be copied into a newly allocated array

- **The destructor**: The primary responsibility of the destructor is **releasing dynamic memory**

```
bag::~bag(){
	delete [] data;
}
```

**The assignment operator**

- Assignment operator vs. Copy constructor:
	- The assignment operator is not constructing a new bag, meaning that there is already a partially filled array allocated
		- The size of this array might need to be changed
		- If we allocate a new array, then the original array must be returned to the heap
	- In the assignment operator, it is possible that the source parameter (which is being copied) is the same object that activates the operator
		- With a `bag b`, this would occur if a programmer writes `b = b` (called a **self assignment**)

```
void bag::operator =(const bag& source){
	value_type *new_data;

	//If needed, allocate ar array with a different size
	if(capacity != source.capacity){
		new_data = new value_type[source.capacity];
		delete [] data;
		data = new_data;
		capacity = source.capacity;
	}

	used = source.used;
	copy(source.data, source.data + used, data);
}
```

- The solution for the self-assignment is to provide a special check at the start of the operator
- If we find that an assignment such as `b = b` is occurring, then we will return immediately
- We can check for this condition by determining whether source is the same object as the object that activated the operator

```
//Check for possible self-assignment:
if(this == &source) return;
```

- `this` is a **pointer** to the object that activated the function
- `&source` is the **address** of the `source` object
- Revised assignment operator:

```
void bag::operator =(const bag& source){
	value_type *new_data;

	if(this == &source) return; //Check for self-assignment

	//If needed, allocate ar array with a different size
	if(capacity != source.capacity){
		new_data = new value_type[source.capacity];
		delete [] data;
		data = new_data;
		capacity = source.capacity;
	}

	used = source.used;
	copy(source.data, source.data + used, data);
}
```

Example:

- Assume that `source` is a bag with a capacity of 5, and the bag that activated the function has a mere capacity of 2
- When the assignment begins, we have this situation

![diagram](02-02_1.png)

- Since the current capacity (which is 2) is not equal to the amount needed (which is 5), the code enters the body of the if-statement
- In the body, we have a local variable, `new_data`, which is set to point to a newly allocated array of five items:

![diagram](02-02_2.png)

- Once the new array has been allocated:
	- We return the old array to the heap
	- Assign `data = new_data`, so that the data pointer points to the new array

![diagram](02-02_3.png)

- Capacity is changed to 5
- We no longer need the local variable `new_data`

![diagram](02-02_4.png)

- At this point:
	- Copy the items from source's array into the newly allocated array
	- Set the value of `used`

- Why not to use the following two statements for memory allocation instead of using a local variable?

```
delete [] data; //Release old array
data = new value_type[source.capacity]; //Allocate new array
```

- When the destructor is given an invalid object (such as our invalid bag):
	- The destructor may cause an error message that will be more confusing than the usual message from `bad_alloc`
	- Programs will be harder to debug
- The invalid bag also makes it harder for experienced programmers to deal with the `bad_alloc` exception in a way that tries to recover without halting the program
- Because of these problems: **Member functions must always ensure that all objects are valid prior to calling new**

### The reserve member function

- `reserve` member function is used to change the capacity of a bag

```
void bag::reserve(size_type new_capacity){
	//Postcondition: The bag's current capacity is changed to the new_capacity (but not less than the number of items already in the bag)

	value_type large_array;
	if(new_capacity == capacity) return; //The allocated memory is already the right size
	if(new_capacity < used) new_capacity = used; //can't allocate less than used
	
	larger_array = new value_type[new_capacity];
	copy(data, data + used, larger_array);
	delete [] data;
	data = larger_array;
	capacity = new_capacity;
}
```

### The insert and operator += member functions

```
void bag::insert(const value_type& entry){
	if (used == capacity) reserve(used+1);
	data[used] = entry;
	++used;
}
```

```
void bag::operator +=(const bag& addend){
	//Library facilities used: algorithm

	if(used + addend.used > capacity) reserve(used + addend.used);
	copy(addend.data, addend.data + addend.used, data + used);
	used += addend.used;
}
```

### The operator + member function

```
bag operator +(const bag& b1, const bag& b2){

	bag answer(b1.size() + b2.size()); //The function declares a bag of sufficient size
	answer += b1;
	answer += b2;
	return answer;
}
```

---

## Prescription for a Dynamic Class

### Four Rules

- When a class uses **dynamic memory**, follow these four rules:
	- Some of the member variables of the class are **pointers**
	- Member functions **allocate and release dynamic memory**
	- The **automatic value semantics of the class is overridden**
	- The **class has a destructor** to return all dynamic memory to the heap

### Special Important of the Copy Constructor

- The **copy constructor** is used when **one object is to be initialized as a copy of another**, as in the declaration:

```
bag y(x); //Initialize y as a copy of x
```

- There are three other common situations where the copy constructor is used

1. Alternative syntax: The first situation is really just an alternative syntax for using the copy constructor to initialize **a newly declared object**:

```
bag y = x; //Initialize y as a copy of x
```

2. The second situation that uses the copy constructor is **when a return value of a function is an object**
	- Example: The bag's `operator+` returns a `bag` object
	- The function computes its answer in a local variable, and then has a return statement
	- When the return statement is executed, the value from the local variable is copied to a temporary location called the **return location**
	- The local variable itself is then destroyed (along with any other local variables), and the function returns to the place where it was called

3. A third situation arises **when a value parameter is an object**
	- Example: `int rotations_needed(point p);`
	- When the function is called, **the actual argument is copied to the formal parameter p**
	- The copying occurs **by using the copy constructor**

---

## Smart Pointers

```
class smartIntPtr{
	int *ptr; //Actual pointer

	public:
		//Constructor:
		smartIntPtr(int *p = NULL) {ptr = p;};

		//Destructor
		~smartIntPtr() {delete ptr;};

		//Overloading dereferncing operator
		int& operator *() {return *ptr;};
};

int main(){
	smartIntPtr ptr(new int());
	*ptr = 20;
	cout << *ptr << endl;

	return 0;
}
```

---

## Clarifying the this Keyword

```
class Test{

	public:
		void printAddress() {cout << "My address is: " << this << endl;};
};

int main(){
	Test obj1;
	obj1.printAddress();
	return 0;
}

//Output:
My address is: 0x7fff5fbff6d8
```

```
class Test{

	private:
		int x, y;
	
	public:
		Test(int x = 0; int y = 0) {this->x = x; this->y = y;}
		Test& setX(int a) {x = a; return *this;};
		Test& setY(int b) {y = b; return *this;};
		void print() {cout << "x = " << x << "y = " << y << endl;};
};

int main(){
	Test obj1(5, 5);
	obj1.setX(10).setY(20);

	obj1.print();
	return 0;
}

//Output:
x = 10 y = 20
```

- We return the reference to the calling object
- This allows us to chain the operations
- Another alternative in the main function if `setX()` and `setY()` return `this` instead of `*this`:

```
Test *obj1 = new Test(5, 5);
obj1->setX(10)->setY(20);
```

---

# Data Structures and Other Objects

### Linked Lists in Action

- Chapter 5 introduces the often-used data structure of linked lists
- This presentation shows how to implement the most common operations on linked lists

## Declaration for Linked Lists

- For this presentation, nodes in a linked list are objects as shown here

![diagram](02-02_5.png)

```
class node{

	public:
		typedef double value_type;
		//...

	private:
		value_type data_field;
		node *link_field;
};
```

- The `data_field` of each node is a type called `value_type`, defined by a typedef
- Each node also contains a `link_field` which is a pointer to another node
- A program can keep track of the front node by using a pointer variable such as `head_ptr`
- Keep in mind that `head_ptr` is not a node -- it is a pointer to a node
- We represent the empty list by storing `null` in the head pointer

## Node Class

```
//Constructor
Node(const value_type init_data = value_type(), node* init_link=NULL) {data_field = init_data; link_field = init_link;};

//Member functions to set the data and link fields
void set_data(const value_type& new_data) {data_field = new_data;};
void set_link(node *new_link) {link_field = new_link;};

//Constant member functions to retrieve the current data
value_type data() const {return data_field};

//Two slightly different member functions to retrieve the current link:
const node *link() const {return link_field;};
node *link() {return link_field;};

private:
	value_type data_field;
	node* link_field;
```

- Whenever a member function returns a `*`, you have to write two functions
	1. const
	2. non const

## Clarifying the const Keyword

- Consider the pointer to a node: `node *p;`
- We can allocate a node for `p` to point to (through using `p = new node`) and then activate any of the member functions (`p->set_data()` or `p->data()`)
- Now consider this pointer parameter declared using `const` keyword: `const node *c;`
- The `const` keyword means that the pointer `c` cannot be used to change the node
	- Pointer `c` cannot be used to activate non-constant member functions
	- The pointer `c` can move and point to many different node, by we are forbidden from using `c` to change any of those nodes that `c` points to

- Note that:
	- We cannot assign a const pointer to a non-const pointer
	- We can assign a non-const pointer to a const pointer

### Example 1

```
node *node_ptr1 = new node;
node *node_ptr2 = new node;

const node const_node_ptr1 = node_ptr1;

const node_ptr1->set_data(5); //Invalid
const_node_ptr1 = node_ptr2;  //Valid
```

- A const pointer cannot be used for activating non-const member functions
- A new value can be assigned to a const pointer

### Example 2: node *const c = &first

```
node *const c = &first;

node *node_ptr1 = new node;
node *node_ptr2 = new node;

const node const_node_ptr1 = node_ptr1;

const node_ptr1->set_data(5); //Valid
const_node_ptr1 = node_ptr2;  //Invalid
```

- If you want to create a **pointer that can be set once during its definition and never changed to point to a new object**, then put the word `const` after the `*`

### Node's Constant Member Functions

- A node's constant member functions should never provide a result that could later be used to change any part of the linked list
- Example: The purpose of the link member function is to obtain a copy of a node's link field
- At first glance, this sounds like a constant member function since retrieving a member variable does not change an object
- So we might write this:

```
node *link() const {return link_field;};
```

### Problem with const

- The node's constant member functions should never provide a result that we can later use to change any part of the linked list

```
node *link() const {return link_field;};
```

![diagram](02-02_6.png)

```
node *second = head_ptr->link();
```

![diagram](02-02_7.png)

```
second->set_data(9.2); //!!!!!!!!
```

### Solution 1

- It makes sense to implement link as a non-constant member function:
	- Making the function non-constant **provides better accuracy about how the function's results might be used**
- `link` implementation as a non-constant member function:

```
node *link() {return link_field;};
```

**This solution has another problem**:
	- Suppose that `c` is defined as `const node *c`
	- With the above non-constant link implementation, we could never activate `c->link()`, because it can only activate const functions

### Final Solution

```
const node *link() const {return link_field;};
```

- This **second version** is a constant member function:
	- `c->link()` can be used, even if `c` is declared with the `const` keyword
	- The return value from the `const` version of the function cannot be used to change any part of the linked list
		- The compiler converts the `link_field` to the type `const node*` for the `const` version function

### Rule for const Member Functions

- When the return value of a member function is a pointer to a node, you should generally have two version:
	- A `const` version that returns a `const node *`
	- An ordinary version that return an ordinary pointer to a node
- When both a const and non-const version of a function are present:
	- The **compiler automatically chooses the correct version** depending on whether the function was activated by a constant node (such as `const node *c`) or by an ordinary node