• CSci202 Computer Science II, Session 16 Iterators in Linked Data Structures
• : Preparation
• : Assigned Work Due
• : Input
• Questions
• : What is a matrix used for?
• : Can the member function on page 489 be used to check for other types besides ints?
• : What are the double colons for -- do they make an iterator?
• : Is it really a good idea to define classes inside other classes?
• : Is an iterator a palce in a container or the contents of a place in the container?
• : What is the difference between prefix++ and postfix++?
• : Can an iterator indicate a place in an empty container?
• : Do trees have iterators?
• : What is the benefit of defining an iterator since a pointer can do the job?
• : Why do several function in the Iterator class have a `throw` clause?
• : What is the difference between standard iterators and ones we do ourselves.
• : Is it important to be able to write our own iterators?
• Exercises
• Quiz 4 on Ch 12 + ALG + BigOs
• Laboratory 8 Implementing and using a Stack
• Next
• Abbreviations

CSci202 Computer Science II, Session 16 Iterators in Linked Data Structures


(previous): Linked Data Structures [ 15.html ]

Preparation

Study this page and chapter 13, section 13.3 ONLY.

(Trees will be covered in CSci330)

Plus prepare for quiz 4 by reviewing the chapter 12 and the following web pages: [ stl.html ] [ 13.html ] [ alg.html ] [ lab07.html ] [ 14.html ] [ lab08.html ]

Assigned Work Due

Hand in your questions, doubts and surprises.

Input

An iterator provides a minimum of four functions

Name	C++	Meaning
an iterator	p	A place in a container
contents	*p	the data stored at a place(p) in a container
increment	p++, ++p	move on to the next place in a container
equality	p == q	test to see if p and q are the same place in the container
inequality	p != q	true if p and q are different places

Typically each container c provides two special iterators:

C++	Meaning
c.begin()	The first place in the container
c.end()	The hypothetical place after the last item in the container c.

Given these it is easy to do something to every item in a container:

 		for(Container::Iterator p = c.begin(); p != c.end(); p++)

 			do_something_to(*p);

This chapter shows how easy it is to create and iterator for a Set.

Here is a diagram of the three classes [ SetIterator.png ] described in sections 13.2 and 13.3. You can download a copy of the Dia model here [ SetIterator.dia ] (right click or shift click...)

Questions

What is a matrix used for?

A matrix was invented in the 1800's to describe linear equations and the manipulations needed to solve them. In this form they turn up in just about every part of Physics and Engineering. As one example, the relation between the stresses and strains in an aircraft wing is modelled by a very large matrix of numbers. Using it we can find out if a wind design is strong enough before we even build the aeroplane. In computer graphics we use matrices to handle perspective, rotating objects, the surfaces of complex things (eg faces), the behavior of light, and so on. I used matrices last in my research to model removing bugs from a program -- Markov having shown how matrices model changes in the probabillities of different states. There are MANY more examples.

For me, the coolest thing about matrices was replacing 25 coeficients by the letter A.

In this book and in CS202 we can forget the above.... and treat matrices as two dimensional tables.

Can the member function on page 489 be used to check for other types besides ints?

Almost precisely the same code will work with any type of data where we have a "<=" boolean operation defined. In the next topic [ 17.html ] we will find out how to right the code ONCE and have it work with ints, chars, doubles, strings, etc..

What are the double colons for -- do they make an iterator?

Something like this [ ClassA::Name ] is used outside ClassA to refer to something called Name inside ClassA.

Since the book and the STL both declare iterators inside container classes the form [ container::iterator ] (STL) [ Container::Iterator ] (book) refer to the correct type of object to iterate through the Container.

Is it really a good idea to define classes inside other classes?

Yes -- when you want a helper class that is protected from abuse and when it belongs to a particular class.

Is an iterator a palce in a container or the contents of a place in the container?

An iterator is a place in a container. The contents is got by using the asterisk:

 		* it

Each iterator refers to at most one place in a container.... sometimes it refers to NO place at all.

What is the difference between prefix++ and postfix++?

i++ and ++i increment i, move the variable up one item. But, i++ returns the old value of i and ++i the new (bigger) value.

Can an iterator indicate a place in an empty container?

No. But it can refer to a place outside the container. For example c.end() is an iterator value outside c and so a natural place to make a iterator refer to, if the container c is empty.

Do trees have iterators?

Yes. at least 3 or 4. See CSci330.

What is the benefit of defining an iterator since a pointer can do the job?

Safety. It reduces the chances of some programmer mis-using your container and letting bad things to happen. throw clause?">

Why do several function in the Iterator class have a throw clause?

There is no way in C++ to attach it to several functions at one time. They make the iterators safe to use.

What is the difference between standard iterators and ones we do ourselves.

If we do well: just the author. If we do badly.... then the code in the library will be better.

Is it important to be able to write our own iterators?

I'm not sure. It depends on the shpe of your career. But I think it is important to know how to write them. At least knowing where to look up an example would be helpful.

In the immediate future.... it would be easy for me to write an incomplete iterator class for a given container and ask you to fill in the blanks in the final....

Exercises

Depends on the questions!

Quiz 4 on Ch 12 + ALG + BigOs

. . . . . . . . . ( end of section CSci202 Computer Science II, Session 16 Iterators in Linked Data Structures) <<Contents | End>>

Laboratory 8 Implementing and using a Stack

Abbreviations