Design Pattern

Iterator Design Pattern

First introduced in CS138, but really learned through CS247.

Resources

• https://refactoring.guru/design-patterns/iterator
• In C++: https://refactoring.guru/design-patterns/iterator/cpp/example

Motivation

We motivated the use of the iterator design pattern in CS247 through the implementation of a linked list. In the example below,

for (i=0;i<100000;i++) cout << l.ith(i);

$ith$ is a not a constant time operation. Takes $i$ steps to find the $i$-th node in the list.

• Total time is ${\sum }_{i=1}^{n}i$, so $O(n^2)$

We can’t just give clients access to Nodes again, because we would get Representation Exposure. We want to efficiently looping over a data structure while maintaining Encapsulation.

This is where we can use the Iterator Design Pattern, which provides an abstraction for pointers.

Implementation

Example:

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

Our client’s use of an iterator will look like:

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

These are the functions we need to implement

• 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

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

post-fix vs prefix ++

The teacher uses specifically prefix ++ so that the function overloaded is Iterator& operator++(). If we wanted it for post-fix ++, we would do Iterator& operator++(int i) (yes disgusting)

If you implement an iterator like this, we can use the range-based for loop syntax:

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

Const Iterators

If you want to do something like this, it doesn’t compile! How should we know that begin/end won’t modify the fields of this constant l?

void useList(const List& l) {
	...
	for (string s: l) { ... } // this calls l.begin(), l.end();
	...
}

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}};

However, we could modify a const List& by using its iterator.

The code below would modify it. (if you want to run the example: go to /u0/s36gong/cs247/1235/examples/lec6/not-const-correct/main.cc)

void printList(const List& l) {
  for (auto& s : l) {
    cout << s << endl;
    s = "CS247";
  }
}

This is due to the difference between physical and logical constness.

How to achieve logical constness? begin and end cannot be cast methods, they return Iterators that return modifiable string refs via operator *

We’ll write additional methods cbegin/cend which return const Iterators, which will only provide a cast string& when calling operator*.

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

Can only call cbegin/cend, these don’t allow us to modify the list.

Small Complaint: duplication between two iterators. Fix this using a C++ Template.

class List {
	...
	public:
		template<typename T> class MyIterator {
			Node* cur;
			MyIterator<T>(Node* cur): cur{cur} {}
			public:
				T operator*() {return cur->data;};
				bool operator!=(const MyIterator<T>& other) {...};
				MyIterator<T>&  operator++() {...};
				friend List;
		};
		using Iterator=MyIterator<string&>;
		using ConstIterator=MyIterator<const string&>;
		Iterator begin() {return Iterator{head};};
		ConstIterator cbegin() const {return ConstIterator{head};};
		Iterator end() {return Iterator{nullptr};};
		ConstIterator cend() const {return ConstIterator{nullptr};};
}

Old copy-pasta from CS138

Not on exam so i just copy pasted from the slides of Mike Godfrey in CS138.

Problem:

• We have a data container (e.g., stack, linked list, binary search tree, hash table) whose implementation is detailed and hairy, and should be opaque to external clients
• But the client has a need to visit each element in turn to perform some kind of operation on the data, such as:
  • Print the elements (“in order”)
  • Find out how many students were born in 1997 with the last name “Matthews”
  • Find all 7 digit phone numbers in my contacts, and prepend 519 to them

Let’s assume the desired operation isn’t part of the container’s normal API.

Bad (but do-able) solution:

• Make a friend function/class that is permitted to muck around with the data structure internals for each desired operation
• But this breaks Encapsulation, saddles the (friend) client with learning lots of hairy implementation details, creates risks that they may get things wrong and screw up the internal logic / correctness of the data container

Better solution: Have the data container itself provide an iterator API that allows for abstract navigation through its elements; e.g.,:

• begin() points to first element
• ++ advances to the next element, repeatedly
• end() points after the last element or is “null” i.e., its value indicates “we’re done here” – Again, note that here, the iterator variable is typically implemented as a pointer, so you have to deference it to access the element

The details of the operations begin(), operator++, and end() are implemented by the container class itself, which already knows the hairy details of the container implementation strategy

• The external client just needs to know how to call the iterator methods, then it can perform the operations on the elements on its own
• Access to the elements by the client is effectively gift-wrapped by the container’s iterator

The major containers of the C++ Standard Library (vector, list, queue, map, set, etc.) all provide various kinds of iterators for free!