This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.
4.13 Iterators Categories
Loading...
From the course by University of California, Santa Cruz
C++ For C Programmers, Part A
470 ratings
From the lesson
Module 4
Prim’s and Kruskal’s algorithms. Use of basic Container Classes. Tripod-Container, Iterator, Algorithm.
Meet the Instructors
Ira PohlProfessor
Computer Science
Next major topic is going to, again, be architectural.
We're going to describe in more detail what the iterator hierarchy is.
Iterator categories.
We can see in the slide that an iterator and the iterator characteristics
are, you have methods like begin() and end(). In this case you're seeing,
this is a list. A typical list allows for bidirection.
And that there's previous pointer and a next pointer.
So if you are at a particular position in a list, you could do position plus, plus
and move over, or you could do position minus, minus, and move backwards.
And again, this specifies the range. This is the start of the range.
This is the end signal of the range.
So, again, very important to grasp that diagram
and this is in terms of the list but
it will be similar of a vector, it will be similar in terms of double ended view.
There are basically an STL five major categories.
Categories.
And the categories are
strongest, to weakest, if you want to think of that.
So this is the strongest,
random access. This is the weakest, what we call input.
Let's look at the weakest first.
The weakest allows you to read and only look at information once.
Read in a single pass, what could that mean.
Think of an input file. Input files are used for reading
and if you read through them you get to the end of file and then you're done The
cursor goes away. The second
weakest, which is very similar, is for output.
Now, output, you can write to the file, so the file can be modified.
But again, a single pass.
The third weakest, sort of intermediary, is forward.
In a forward iterator, you can read and write, so you can do both operations, so
you have more operations. But, you can also act on it.
The file
doesn't disappear on you.
It can be used multi, multi-pass, so the construct you're
operating on, like vector or a list, is staying there.
I'm like thinking of a file, that file read that disappears on you.
So it can be multi-pass but it's one directional that's what I
mean by 1D, I don't mean one dimensional, I mean one direction.
Bidirectional, which we saw in that little diagram is again more, more sophisticated.
Multi-pass is allowed, and you can go to
a previous element as well as the next element.
And finally, random access is strongest 'because you can go on it, anywhere, and
you can go anywhere, in what, is known in analysis of algorithms in order one.
You can do an address computation anywhere into, what is,
indexable. So, you can think of that as something
were it's an indexable container. Economical being a vector or
Now, when we go to design algorithms, we always
keep in mind what iterator category we want to use.
Now we always want to choose and well try,
try to understand but let me say this first.
I'm going to repeat it If you study this in detail, if you go to
study you'll have to study in a library on your own, the library is enormous.
But a very important conceptually
to keep in mind that when you design an algorithm you design the most
efficient version of the algorithm that allows you to use the weakest.
Iterator category.
So, restating that, in STL the design principle
is to use the weakest iterator that accomodates
the most efficient algorithm. We see in Quicksort.
Quicksort requires random access.
Without random access, you can't do Quicksort.
As a consequence, it can not be used on a non-random access container such as a list.
Indeed, list for example has a special sort routine.
It's not that you can't sort a list.
You could do it in one of two ways. You could transfer
the contents of the list to a vector for example, that would be one way and
then call the ordinary sort on the vector and then reconstitute the list.
So there you're building, you're destroying one
list, rebuilding the list, and using vector.
But it may be simpler to just call the specialized
sort on a vector, which will not be as efficient.
Can't
be. It won't be as efficient.
It doesn't have random access available to it in moving stuff around.
Now why random access? Well remember, we want an order -n - log -n
computation for Quicksort, and if you recall, Quicksort is also called partition
exchange.
We have that partition element. We identify two elements that belong
on the other side of petition, and we swap them.
For the swap to be efficient, this is sitting in (element) i and this is sitting in (element)
j and we need to. Deal with that, in random access mode.
If we deal with that as a list, we can
do that, but then that becomes an order-n computation.
So each swap would be order n. In random access, each swap is order-1.
And that gives quicksort its n log n behavior.
Let's go through the iterator hierarchy a little more carefully.
There's the input iterator.
The input iterator must allow the elements to
be searched in a forward direction one by one.
Requires that the operator plus, plus be defined advance the iterator.
And also requires that you will be allowed
to dreference the object that the pointer is pointing
at, that the iterator is pointing. When you have an input iterator,
canonically it's for accessing elements sequentially in input stream.
And that requires a rather minimal set of operations.
Similar to using what's called the find of an element, in a collection searched
sequentially. Also input iterators can have
equality and inequality defined. So, if you think of
because it's in the standard algorithms library, find().
And we have some basic
sequential. Let's say we're
looking for the element 6, we could start at the begin().
And then move along until we hit 5.
And that's going to be perfectly efficient.
We don't need any random access.
We don't know where something is, so we're
going to have to look through this set of items.
But we only need to look through them once.
If we go through them more than once, what's the point?
That would be extra work.
So looking and trying to find something in a list, so think about
a pile of note cards where you're keeping addresses for your friends.
And they're unordered, the typical algorithm would be exactly this.
Find, I would go to my little note pad, file, and keep
sequentially reading through them and looking for particular element.
I would look for where is Laura Pohl's current address?
And
I just would, continue to look that up and find() would do it.
So find() can rely on a weak, the weakest possible iterator, the input iterator.
And that's how it would be defined in STL.
Here's an example, using an input iterator.
And it's using the numeric library.
So again there's
algorithm, there's numeric, these are the different kinds of methods that get
produced generically through the use of STL, that's the three-legged stool again.
And accumulate() will be sitting in the numeric library.
And accumulate in this case is using
an input iterator that's at the start of this ifstream.
So we have a file, the file is sitting somewhere,
it's a data file.
Its name is data in the local directory,
which has some series of numbers which are integers.
And we want to add all those numbers up.
So, let's say there where the six numbers 64 minus 3 and 19.
The file had four elements.
We have an istream iterator. Which points at the beginning of the file.
And we have something for the end of stream.
The end of file, in effect.
So this is the equivalent of begin and end.
And then
the, we accumulate starting with the value zero.
So this can be an arbitrary,
value.
For example, if we have a whole bunch of files to look up, and add
up, we may want the last value to be the starting value for the next accumulate.
Accumulate is just going to Add 6 plus 4, minus 3, that's 7, plus 19.
So we're going to end up with, in that case, printing out 26.
All very compact, all done without worrying about
indexing. highly useful because
operations like this occur all the time. And accumulate as we see.
Only needs to run through it once, in one direction.
Just like find().
And so it can make use of the
weakest iterator and still be highly efficient.
So, if you were to look at the signature for accumulate in the library,
and you'll see, look it up in the standard or look it up using Wikipedia.
You'll see that a signature involves they'll,
they'll probably say something like input iterator there.
And then some kind of value.
Again, because it's all generic, right? These are input
iterators of a general type, though
this is some type. In general so it can be
an arbitrary value, and usually by default, that starts at
whatever is the is, is the natural
zero for that type,
but it could be some other value that your starting.
That's accumulate().
Very useful numeric routine people are doing accumulate() over and
over again so what's the point of writing your own version?
No point to it at all.
Okay, take a little quiz, see what would happen.
What is the output, from this little code segment.
So, we saw that the starting value was five, it wasn't zero.
And so it's 5 plus 1 plus 2 plus 3 plus 4, 5 plus 10 so that's 50.
So the answer
is 50.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
