Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

4.13 Iterators Categories

Loading...

C++ For C Programmers, Part A

University of California, Santa Cruz

4.4 (615 ratings) | 92K Students Enrolled

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.

Skills You'll Learn

Graph Theory, C++11, C++, Graph Algorithms

Reviews

4.4 (615 ratings)

5 stars
400 ratings
4 stars
138 ratings
3 stars
31 ratings
2 stars
20 ratings
1 star
26 ratings

AK

Jul 04, 2017

I like Prof. Ira a lot and wish to see more courses from him! I wish I was his student at SC. Best Regards to him and the Coursera team for the great work.

PK

Jul 18, 2018

I really loved this course. It is really helpul for my programming aspect. I have managed to develop my logical abilty and this course really helped me.

From the lesson

Module 4

Prim’s and Kruskal’s algorithms. Use of basic Container Classes. Tripod-Container, Iterator, Algorithm.

4.2 Jarnik-Prim MST11:50

4.3 Jarnik-Prim MST: Another Look11:07

4.4 Kruskal's Algorithm8:30

4.5 Overloading and Function Selection32:19

4.6 STL and STL C++1111:00

4.7 STL Example5:05

4.8 C++11 Feature: auto5:38

4.9 Vector Methods10:36

4.10 More Code8:50

4.11 C++11 Feature: for statement7:07

4.12 STL Input File11:30

4.13 Iterators Categories14:19

4.14 Output a Random Graph12:30

Taught By

Ira Pohl
Professor

Transcript

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.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates