In this video, I'd like to go over some of the algorithms in the stl.
Now there are a lot of algorithms in the stl, I'm only going to
cover a few of them, but the techniques you'll see apply to
many of them, and you can be very productive with them very quickly.
I'm in the section 20 workspace, and I'm in the algorithms project.
And let me just go over these includes real quick.
I am including algorithm.
We need that to use these algorithms.
I'm also including vector, list and cc type.
Now cc type we're going to use for the 2 upper function that converts a
character from lowercase to uppercase.
That's the only reason we're going to do it.
And most of the examples we use a vector, but there's 1 that's
going to use the list just to change things around a little bit.
Okay, so that's that.
We're also going to use this person class that I created right here.
It's a really really simple person class.
A person has a name and age.
I think we've used a class like this or very similar to this before.
I have a default constructor that pilot will generate for me.
I've got an overloaded constructor that expects a name and age.
Then I've got these 2 operators.
These are really important.
Whenever we use the stl, it's got to have a way to compare our own objects.
Now these are all user-defined types.
So I need to provide the less than and the equality operators.
And all I'm doing here is I'm saying that 1 person is less than
another person if their age is less than the other person's age.
This is just totally arbitrary in this example.
This really would depend on whatever business logic you're using.
And how do I compare 2 persons?
Well, their names have to be the same, and their age have to be the same.
So we've got that and here.
So that's it, a real simple person class that we're going to use in here.
So I've also divided this into functions just like I did
with the iterators lecture.
So let's take a look at this first 1 here.
What is the algorithm we're using?
The algorithm is right there.
That function is defined function.
It finds an element in a container.
Okay, the first occurrence of the element in the container.
So what are we going to do?
Let's create a vector of integers 1 2 3 4 5.
And then I'm going to call std find.
I'm going to give it the beginning and the end.
Now notice that this syntax here is a little different, I
just wanted to show you that syntax in case you run into it.
It's equivalent to vec.begin and vec.end, like we've seen before but.
In this case, it std began, and you pass in the vector or the container.
So it's just another way to do, it means exactly the same thing.
So let's get back to this.
I'm calling the find function I'm passing in where I want to
start where I want to end, right, that's the sequence that I'm going
to get back from the container.
I'm using these iterators.
And that's what I want to find.
I want to find that element 1.
I know it's there.
It's right here.
Okay, now what does this return?
Well, if it finds it, it will return an iterator pointing to it.
If it doesn't find it, it'll return an iterator to the end.
So it's really simple to check.
Okay, so let me clear this, and let's look at the logic here.
So we're executing that function.
And if the location -- remember, location I'm using auto,
but location is an iterator to a vector of integers.
If the location is not equal to the end of the vector, then we found it.
We found the number, and we could just dereference it and print it out.
In this case, it'll print out 1.
Otherwise, we couldn't find the number.
So let's execute this.
And then we'll change the code just a little bit.
So let me run this real quick.
We found the number 1.
Absolutely, it's in there.
Now let's change the 1 to something like a 7.
We know that the 7 is not in the vector.
So let's execute this again, couldn't find the number,
just what we expected.
Now I'm going to change this back to 1 so you guys can play with it when you
have the the source code on your end.
That's as simple as it gets.
The really cool thing about this is I'm finding the first occurrence
of an element in any container.
That's mind-blowing, right, because you're not worried about
how this stuff is implemented.
You've got all these different containers how easy is this you.
Know I just want to find some things, just go call find.
Where do I start.
Where do I end.
What do I want to find.
That's real classic abstraction, that's pretty cool.
That's using a primitive type an integer.
What would it look like if we're trying to find a player.
So that's what this example right here is going to show you.
So let's take a look at that.
In this case, I'm not using a vector, I'm using a list,
but it's all the same.
I've got a list of persons, right.
I'm calling them player.
I'm initializing it to Larry is 18 years old, Moe is 20 and Curly's 21.
Remember, that person class I showed you a little bit ago.
I want to find that person in that list.
Look at the code, auto location 1 equals std find, where do
I start, where do I end, what do I want to find.
The stl algorithms is going to use the equality operator that
I've overloaded for my person class to compare these guys.
So hopefully, it'll find this guy right here, right.
So if location 1 is not equal to the end, then I found Moe.
Otherwise, I didn't find Moe.
And how do I know that Moe is Moe.
Well, Moe has to be.
His name it has to be Moe and he has to be 20.
Remember, our equality operator is checking for both.
All right, so let's give this one a run, and we should see found Moe.
That's exactly what we get.
Now if I change Moe's age here.
Let's see I'll make them 18 or 12.
That's not in there.
I don't have a Moe 12 in there.
So at this point when I run it, I should not find Moe.
And it says Moe not found.
That's exactly what we expected.
So let me change this again back to 20.
Okay, so that is the find test.
That shows you how to use the find function, super powerful.
I mean when you think about it how hard is it to write a
find function for an array.
It's not really.
You start at the beginning, and you move along, we found it.
I'm done.
But what about a list, a doubly linked list, a priority queue, a set.
Wow, that's a lot of code you would have to write yourself.
You don't have to worry about any of that.
You just call find tell it where to start, tell it what it were to end
and tell it what you want to find, and you're done, it's as simple as that.
Okay, so that's the find test.
Let me show you the count test now.
So I'll uncomment that out, and let's take a look for the count test.
This one is really, really dead simple.
All it does is it counts the number of elements in a container, but it take…
you can take it a little bit further.
You can actually count the number of occurrences of that specific element.
Remember, we could just use size for the count of the elements.
But in this case, how many times does the 1 appear in this container.
Well, I've got it here, here and here.
It occurs 3 times.
So what's my algorithm count from the beginning to the end.
And again, you can use a subset if you like.
I'm always going to do beginning to end in these examples.
This will return an integer.
If we get back a 0, didn't find it.
If we get back a 1 or 2 or 3 that's how many times the 1 occurred.
So in this case, I expect back a 3.
Let's run this, and there it is, 3 occurrences found.
So the 1 was there 3 times.
Again, if I put something that's not in there like a 10 in this
case and I run this, it should get back 0 occurrences found
and that's exactly what we get.
Okay, simple as that.
So let's close this one down.
And let's take a look at a more powerful one called the count if test.
So here's the count if.
The count if is a little bit different.
We're going to use the lambda expression for it.
This one is super powerful.
We're only going to count how many times that element occurs
if it matches some condition.
Okay, that condition is called a predicate.
It's something that returns a true false value.
So here's my vector.
And you can see that what's my condition.
Well, you can see right here.
Look at the lambda, the lambda tells you exactly what I'm doing.
I'm only looking for numbers that mod 2 or 0.
I'm only looking for even numbers here, right.
That's what that predicate right here is doing.
So I'm starting at the beginning, and here's my lambda.
I'll write it up here just we understand exactly what's going on.
There's my lambda.
And here's the code for the lambda, which is this piece right here,
and I won't write that again.
That's my lambda.
So what's going on.
I'm starting at the beginning of that vec.
I'm going toward the end of the vec.
And for each element, in that sequence, I'm passing it into here.
And that's going to return true or false.
Depending on what it's returned, it's going to include it in the count here.
Okay, so in this case, what's being passed into this lambda here is
1 and then 2 and then 3 and then 4 and then 5 and so forth.
And all it's doing is if this is true, if this predicate right here
is true, it's just counting them up.
Okay, so in this case, how many even numbers do we have.
We have 1, we have 2, we have 3, we have 4.
So I would expect a 4 coming back.
Over here, you can see it's the same idea except this
time, what am I looking for.
I'm looking for odd numbers.
How many odd numbers do we have.
We have 1 2 3 4 5.
So we've got 5, I expect a 4 from here.
I expect this to print out of 5.
Now let's write another function, we'll write this one together.
How can we determine, how many elements in the vec are
greater than or equal to 5.
So what do we do.
Well, we write the statement real simple.
Num equals std count if, that's my algorithm.
We're going to do vec.begin.
Let's search the entire vector.
We're going to go to vec.end.
Now we could have used a constant iterator here.
We could use a lot of things.
I'm just going to do real simple.
So I'm going from beginning to end.
And at this point, this is where I need my lambda.
So all these elements are being passed into this.
What am I going to do, I'm going to put my lambda in here.
It's going to expect a single integer.
I'm going to write my code right in here.
Then I'm going to close this and close it like that with a semicolon.
So what is the predicate.
I'm going to return true if x is greater than or
equal to 5, just like that.
And let me just copy this line right here, I'll move it down here.
So all I'm going to do is I'm going to output num,
numbers are greater than 5.
How many of those do we expect.
Well, we've got 2 greater than or equal to 5.
Sorry, so we have 5 and the 100.
So there's only 2.
So let's run this.
We have 4 even numbers, just what we expected.
We've got 5 odd numbers and 2 of the numbers are greater than
or equal to 5, I'll change that.
There you go, pretty simple.
These lambdas take a little getting used to, but you get
used to them really quickly, and they're so powerful, it makes
programming much, much simpler.
Okay, so that's count if.
The next one we'll do is a replace test.
So let's take a look at replace test.
Let me comment that out here.
So what is this doing.
Well, this is looking through a vector in this case or any container.
And it's going to replace one number with another.
Pretty cool.
So here I've got a std vec.
And I've got 1 2 3, notice the one.
That's all I really care about in this case.
I've got 3 of those 1s right in here.
I'm just displaying them out right now, and we'll display them out.
And then I'm calling std replace, and I'm starting at
the beginning, going to the end, and I'm replacing 1 with a 100.
And remember, I'm using primitives here, but we can use
our own objects if you like so.
In this case, I'm replacing those 3 1s with a 100 and then
I'm just displaying it again.
So let's give that a run.
And we'll be able to see that we've got 1 2 -- let me move this
-- over just a little bit, 1 2 3.
You can see the 3 1s here.
And you can see that the 3 1s have been replaced with 100s.
Really cool, really easy.
Okay, let's do a couple of more.
And the point of this is not to show you these specific algorithms.
There's, like I said, over 50, probably closer to
90 algorithms out there.
If you look at the numeric header as well, they all work in a similar
way, they all use iterators, many of them use predicates.
So this gives you a pretty good feeling for the power that's out
there and the things you can do.
So this is the all of test.
This is really cool.
Let me show you this one.
So here's my vec1.
And I've got a 1 a 3 a 5 a 6 or 9 a 1 a 3 a 13 a 19 and 5, just
some arbitrary numbers in there.
What this is doing.
There is the function all of.
It's going to see whether all of the elements in that
container match this predicate.
That's super powerful.
So in this case, I'm saying if all of those elements are greater than
10, then this will return true.
Otherwise, they would it will return false.
So obviously, then they're not all greater than 10, right.
I've got a 1 and a 3 and a 5.
So I expect this to return false, and I expect this to print out.
In this case here, all of that I'm starting at the beginning going
toward the end, I'm checking to see if all the elements are less than 20.
You can see in here they are less than 20.
Every single one of them is less than 20.
So I expect this guy to display right now.
We have the all of.
There's also another algorithm called any of, which.
So if any of them is greater than 10 it'll be true.
So you've got the power to compare them all or just compare one of them.
So let's execute this.
And we can see here, not all of the elements are greater than 10.
Absolutely, we've got some that are less than 10, but all
the elements are less than 20.
And I can't impress upon you the fact enough times
about how powerful this is.
We don't really care about the container.
That's the cool part.
I don't need to worry about it.
It could be implemented in a really, really complex way, doesn't matter.
The algorithms library handles it for us.
All right, so the last example is a string transform test.
This is pretty cool.
There's an algorithm called transform.
And it works not just with strings, it works with with containers obviously.
But it's used very often with strings.
Let me show you what it does.
And this is where that 2 upper function comes in.
So here I've got str1 is a std string.
And it's initialized to this is a test.
And all I'm doing is I'm displaying before the transform,
I'm displaying the string.
So that's just going to display this is a test, just like that.
Then I'm going to call the std transform function.
I'm going to tell it where to start at str1 begin.
Where to end in, other words, it's processing the entire string.
And then where to start placing its results at the
beginning of the string again.
And what do I want to do.
Well, I want to make each character 2 upper, and i can pass my own
function in here, but we already have the 2 upper function defined
in cc type so may as well use it.
Whenever you put that scope resolution operator in the front
of something with nothing here just that guy followed by something
else, that means global scope.
And that's what's going on here.
So I'm using the 2 upper method or function actually
that's in the global scope.
So what do you think this does, it makes every single character
in that string uppercase.
Super powerful.
We can process strings.
If you remember that one example we did a while back with the
way back in the course, right, where we encrypted a string.
This makes it really easy because you can transform that string, you can
play all kinds of games with it, and the algorithm becomes much cleaner.
So let's run this example.
And we should see the string in lowercase and then
the string and uppercase. There it is.
This is a test.
All right, so that gives you a little bit of introduction.
And let me uncomment this out, set it up just like that, so I'll
save it like that for you guys to be able to download it and play
with this from the beginning.
So here you can see the find, the count, the count if, the
replace, the all of, you can play around with the any of.
And what I would encourage you to do is -- let me just
close this up a little bit.
What I want to encourage you to do is play with these lambdas.
Give yourself different conditions, make them a little bit more
complicated if you like, and just get used to the lambda syntax.
One of the things that we're not going to do in this course or maybe I will
in a different section later on, I can add a section just on lambdas.
That guy, right there, those 2 square brackets, that's the lambda's
capture block, that's a real important piece of the lambda that
allows you to capture the context.
So if I have variables in here, I can catch them in there
and set them and use them.
We're not doing that in here, we're just keeping
the lambdas really simple.
Hopefully, you do understand these lambdas and how powerful they are.
Play around with them, get comfortable with them.
It's really the way to go with modern c++.
All right, so that's it for the algorithms demo.
Now we're going to start talking about the actual containers.
The first one we'll talk about is std array.
So I'll be right back to talk about that.