Lecture 6 CS247

Last Time: Encapsulated List, Iterator This Time: Physical vs. logical constness, const iterators, templates, separate compilation.

We saw we could modify a const List& by using its iterator. This is due to the difference between physical and logical constness.

Physical constness is about a particular object’s implementation. Compiler guarantee’s this for const objects/const references. Ensures the fields won’t change.

Logical constness asks not only for the fields to be immutable, but also that the memory associated with the representation of the ADT doesn’t change.

How to achieve this?

• Begin and end cannot be const methods, they return Iterators that return modifiable string references via operator*.

We’ll write additional methods c.begin()/c.end() which return const iterators, which will only provide a const string& when calling operator*.

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

Now: Connect call begin/end on a const List&. Can only call cbegin/cend, these don’t allow us to modify the list. Complaint: Duplication between the two iterators. Fix this using a template class. Template classes are allowed to be parameterized via the type provided.

Classic example: STL - standard template library

vector<int> vs vector<string>

int and string are type parameter denotes what the vector contains.

Specify the return type of operator* as a template parameter, rest of the code is the same.

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){...}
		MyIteraotr<T>& operator++(){...}
		friend List;
	};
	// Back in List
	using Iterator MyIterator<string&>;
	using constIterator = MyIterator<const string&>;
	Iterator begin() {
		return Iterator{head};
	}
	const Iterator cbegin() {
		return ConstIterator{head};
	}
	// end and cend are the same
}

Note

Template definition of methods must be written in the header file. Node’s definition must also be moved into the header file, because the template needs to know the next field exists.

How do templates work? (briefly)

• For each use of MyIterator<T>, compiler generates another copy of the class with T substituted where necessary. Afterwards, compiles as usual.
• No run-time cost using templates, it’s as if we wrote our own Iterator/const Iterator.

Separate compilation

In List.h (original version), we provided a forward declaration of sturct Node. Provided definition of the class in the .cc file. This is especially useful for separate compilation. g++ -std=c++14 List.cc -c

• -c compiler flag lets us produce an object file.

Think of object files as containing the machine instructions for that code. Use object files to store the result of compilation, and reuse it if the .cc files haven’t changed.

With many files, significant speedup while developing.

We prefer to put implementations in a .cc file for the following reasons:

• List.cc changes $\to$ recompile List.cc into List.o. Link object files together to get an executable.
• List.h changes $\to$ all .cc files that include List.h must recompile.
• A.h includes List.h $\to$ any .cc files including A.h must change.

We prefer forward declarations of classes where possible-minimizes recompilation.

When can we simply forward declare, when do we need to use #include?

class A {...}; // A.h
class B: public A {}; // B.h
 
class C { // C.h
	A myA;
}
 
class D {
	A* ap
};
 
class E {
	A f(A x);
}
 
class F {
	A f(A x){
		x.doMethod();
		...
	}
}

• B needs to know how big A is, include
• C needs a field in A, need include. $\to$ B and C require #include in order to determine their size and compile them.
• D $\to$ all ptrs are the same size, just a forward declaration suffices.
• E $\to$ we don’t need to know the size of A, just that it exists for type-checking purposes.
• F $\to$ we must #include A.h to know that doMethod exists.