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 49 00:04:05,209 --> 00:04:10,140
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(). 106 00:08:32,105 --> 00:08:33,910
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 15. So the answer is 15.
