CS247 Lecture 5

• Last time: Dtor, Move ctor, copy/move assignment operator, elision: CS247 Lecture 4
• This Time: Improving encapsulation, iterators.

How can the client misuse this ADT: Tampering and Forgery?

Struct Node {
	Node* next;
	String data;
};

Forgery:

Node n{"bad ptr", (Node*)0x247} // completly random memory address

Mostly likely a segmentation-fault on any kind of use.

Tampering:

Node n {"a", nullptr};
n.next = &n; // A cycle of 1 node.
 
Node n{"abc", nullptr};
Node p{"def", &n}; // This will try to delete stack memory when the dtor runs.

All these issues are from a common problem: Representation exposure Every ADT has a representation in memory .

• e.g. Linked lists are implemented via a series of Nodes. If the client gains access to the memory, we call that representation exposure. (Client can use this knowledge to do things we don’t expect.)

We have expectations/rules for all linked lists:

1. All next nodes are heap allocated (or next is nullptr)
2. No sharing between separated lists
3. No cycles in our list Clients shouldn’t need to uphold these invariants, it’s our responsability.

Solution: Encapsulation, provide public methods for the client to interact with our List with.

// list.h
class List{
	struct Node; // Forward declaration of a private 
				 // nested class
	Node* head = nullptr; // front of our list
public:
	List(){}; // default ctor, creates the empty list
	~List();
	void push(const string& s);
	string& ith(int i);
};
 
// list.cc
struct List::Node {
	// same as before
}
 
List::List() {}
List::~List() {delete head;}
void List::push(const string& s) {
	head = new Node{s, head}; // create new node with datas and points to the rest of our list and update where head is pointing to
}
string& List::ith(int i){
	Node* cur = head;
	for(int x = 0, x < i; ++x) cur = cur->next;
	return cur->data;
}

This solves our representation exposure problem. Client has no knowledge of Nodes, no access to internal memory representation, no tampering or forgery allowed. Lists are slow!

• ith is not a constant time operation!
• Takes i steps to find the i-th node in the List for (i = 0; i < 100000; ++i) cout << l.ith(0) Total: $\sum i=n\frac{n+1}{2}=n^2\frac{n}{2}=O(n^2)$

We can’t just give clients access to Nodes again, representation exposure.

Design Patterns: Effective solutions to common problems. Problem: Efficient looping over a data structure while maintaining encapsulation. Pattern: Iterator Design Pattern: provide an abstraction for ptrs.

Example:

int x[s] = {247, 1, -100, t, 60};
for(int* p = a; p != (a + 5); ++p){
	cout << *p << endl;
}

Our clients use of an iterator will look like:

List l;
for(List::Iterator it = l.begin(); it != l.end(); ++it){
	cout << *it << endl;
}

For List: begin/end functions that return iterators: For List::Iterator:

1. != to compare
2. ++ to go to the next Node
3. * to get the string at current Node

Implementation: (defined in .h)

class List {
	...
public: 
	class Iterator {
		Node* cur;
	public:
		Iterator(Node* cur): cur{cur} {}			
		bool operator!=(const Iterator& other) {
			return cur != other.cur;
		}
		string& operator*() {
			return cur->data;
		}
		Iterator& operator++() {
			cur = cur->next;
			return *this;
		}
	};
 
	Iterator begin() { return Iterator{head}};
	Iterator end() {return Iterator{nullptr}};
};

If your implement an iterator like this, we can use the range-based for loop syntax: (shortcut syntax)

for(string s: l) cout << s << endl;

[!=Note] No reference ⇒ a copy from cur→data into S.

for(string s:l){
	s = "";
}
// No effect on the list
 
for(string& s:l){
	s = "";
}
// sets strings in the list to empty

Can also use auto for type deduction:

for(auto s: l) // determines s is a string for us

Danger

Auto drops references, so if you want to modify l, use auto&.

Iterator is a public nested class, with a public ctor. Worry for Forgery:

• auto it = List::Iterator{nullptr};
  • creating an ending iterator

$\to$ This could be a problem for other kinds of Iterators where nullptr is not used. Solution:

class List{
	...
public:
	class Iterator{
		Node* cur;
		Iterator(Node* cur):cur{cur} {} // changed
	public:
		// as before
		friend List; // List can use privat methods Iterators, namely the ctor.
	};
};

• friend List is a friend class
• In general: cautious when using friends, weakens encapsulation.
• Only make friends if they can do something for you!

Subtle issue:

void useList(const list& l) {
	...
	for(string s:l) {...}
	// s:l this calls l.begin() and l.end()
}

Doesn’t compile! because l is a constant value

• How should we know begin/end won’t modify the fields of this constant l?

Solution: Declare begin/end as const methods, promise we won’t modify fields.

Iterator begin() const {return Iterator{head};}
Iterator end() const {return Iterator{nullptr};}

A constant object (or const reference to an object) may only have const methods called on it.

Now it compiles. (actually bad)

physical vs logical constness??

---

Next: