So let's go to the next more sophisticated stronger iterator type. That's the bidrectional type. Bidirectional types must allow both the forward iterator operation, ++, but also the back up Iterator, back the iterator up, --. And again, lets study a canonical algorithm. A standard algorithm in SDL that requires the use of bidirectional iterator type. Again, the way you would read the library is you would see a name like BidirectionalIterator, indicating that that was indeed its type. And then you would see something like first and last, which is the iterator range. Frequently that’s begin and end. But it can be some other subpart of that range. And then what reverse does is to take some mutating algorithm, and it reverses the elements in the specified range. So we would expect, if we had 1, 4, -3. I could throw in another one, 6. That, at the end of this, we would have 6, -3, 4, 1. That's reverse. That's what reverse is going to do. And the logic in making STL algorithms efficient is, pick the weakest iterator that lets you have the most efficient algorithm. So efficiency is prize. And we're going to do swapping because we're going to keep track of where we are, both forward and backward. And we can just do this in one pass if we have both a forward and backward iterator. And then we can just swap the reverse and meet in the middle. So, that's our program. Swap and meet in the middle. We're going to move from both ends. So, the notion again is, We have these four elements, whatever they were. I don't remember if they were. Let's say 3 is here and 6 is there to begin with. -1 is here and 2 is there. And then we're going to start at the front with a front cursor. Start at the back with a back cursor. Do a swap. So at the end of that first swap, you're going to see 6 and 3, -1, and 2. And then you're going to move the cursors. So here's front and back again. F and B I'll call them. And then the 2 and the 1 will be swapped. And then we'll end up with 6, 2, -1, 3. So that's the algorithm. And that algorithm that I've just shown you will let us check for whether something is a palindrome. Simple palindrome is for example the name Otto. Otto is Otto forward or backward. A more complicated palindrome is one you can see. Dalmation. Na it am lad. So, we get right dalmatian either forward or backward. And here's how we would test for it. Here's an isPalindrome algorithm using bidirectional, bidirectional. And I love bidirectional, because I'm actually pretty well known in the AI community for something called bidirectional search. So, I have a warm spot for bidirectionality. And here you can see that algorithm that I already described. You keep going. So, this is an infinite loop. Which means there's going to be an exit somewhere in here. So, here's an exit and there's an exit. These are its exit points, otherwise we would have an infinite loop. We're testing to see when first and last get to meet. Okay so, let me just check what we're doing here. We're saying, while true decrement the last. Why do we decrement the last? Because we're off by 1. That's going to be begin end. So last is going to start over here. First is going to start over here. We decrement it. That's why its bidirectional. And now we're pointing at the last element. And here's where we're testing, and we return false. So we check if this element, what's in here And what's in here are the same. If they're not the same, it's not a palindrome and we return false. If there are the same, we have to move first over. We move first over. So, this is the new first. We re-enter the loop. So we move, last, back. We do our test to confirm whether they're different. If they're different we return false. And otherwise, we march first and last. And as long as first is not equal to last we return but if first equals last, so if they meet in the middle, that means that we've hit a palindrome. Meet in the middle means we break. And break gets us to true. We've already said what's on this slide, algorithm moves forward and backward, testing each position. Checks to see if two values that are symmetric are the same. And if they're not Internally, there is a false. If it keeps going and meets in the middle, it's true. And if you try to do this with only a forward iterator you would have to think about it. You would have to start over here. And then you could use a forward iterator. It would be a multi-pass algorithm to move to the end. And then you could do the swap. That would be okay. But then you'd have to move this iterator to the second position and then restart that iterator all over again. And you would end up with an order and squared computation. So, we don't want forward iterator, even though it's possible to manufacture this algorithm with a forward iterator. That's a design principle for STL. The strongest iterator necessary to make the algorithm official. Notice, we could also do this algorithm efficiently with a random access iterator. But a random access is too much power, we don't need it. So, we're always looking to optimize, most efficient algorithm, weakest iterator.