Hello again! In this video, we are going to have an overview of standard algorithms.
An algorithm generally is a step of sets which are used to solve a problem.
It is quite similar, actually, to a recipe in cooking.
So if you follow all the steps in the recipe correctly, you will get a nice, tasty cake, or pie, or something
like that.
In computing, an algorithm often refers to a technique for searching for data, or sorting data.
It can also mean a technique for solving a specific problem. For example, with the travelling salesman.
If a salesman has to travel to so many towns in a day, which is the quickest route? And there is an
algorithm for solving that.
The Standard Template Library that comes with C++ defines a number of functions in the header.
And these implement the classic sorting and searching algorithms, as well as lots of other useful routines.
So why should you use these?
Well, there is a wide range of useful features. There is more than 100 algorithm functions for you to
play around with.
Using algorithms will make your code shorter and clearer.
Quite often, when you have an explicit loop over a container, you can replace that with a single
call to an algorithm.
The algorithms are extremely flexible.
There is plenty of scope for programmers to customize how they work.
So you can adapt them to your particular problem, and they're also a good example of code re-use.
They've been coded and tested by the people who wrote yout standard library implementation.
They are more accurate, probably, and more efficient than anything you are likely to write.
Unless you are really good and you have lots and lots of time. They can use internal compiler features
and library features which are not available to application developers. And using algorithms will save
you lots of development time.
We saw that the library string has a find() member function. And you can use that to search, but you
can only use it if you have a string object.
The algorithm functions in the standard library are global, non-member functions, which will work
with any kind of Standard Template Library container. And the container
elements can have any type, including ones that you write yourself.
So these are known as generic algorithms, because they are completely generic.
All the algorithms are slightly different, but typically what happens is that you pass an iterator
range to the algorithm call.
So this will say which elements in the container you want the algorithm to process.
If you want the entire container, you would say begin() and end(), or their return values. You can have others as
well. You can process sub-containers just as easily.
The algorithm will iterate over the range of elements, and it will call a function on each element.
And then, usually, the algorithm will return an iterator, representing some element of interest, or a value,
which is the result of some operation on the elements.
For example, if you are doing a find, it will return and iterator to the first matching element.
If you are doing a sum - addition - then that will return the results of adding up all the elements
in the container.
So let's look at the genetic find() algorithm. It is slightly different from the string one.
(Apart from being generic and not requiring a string.) The string version returns an index which is okay.
The generic find returns an iterator.
And the reason for that is that some containers do not have the concept of an index.
So this has to work with every container.
If the character is not found, the algorithm will be return an invalid iterator.
So the string find() returns the index of an impossible element, or an impossible index if you prefer.
And the algorithm returns and impossible iterator.
And that will be the return value from end().
So that will be an iterator to the last plus one element.
So if we do a search, then it will look like this.
We have these string we are searching. Then we have the find() call. Then we have the iterator
range. We are using begin() and end().
So that will search the entire string. And we can use the const versions, because we are not going to modify the string.
And then the value we are searching for, which is the first occurrence of the letter 'l'.
And then this will return an iterator. And we can use auto to avoid having to work out what the iterator
type is and how to spell it correctly!
Then we need to check that we got a valid iterator, just as we needed to check the string find() for a valid
index.
So if the iterator is equal to the return value from end(), then we do not have a match and we cannot
use that iterator.
Otherwise, we can do something with it.
For example, here we are printing out the distance between the start of the string and this iterator,
and that will give the index of the element.
So this is actually compatible with the string version.
So let's try this out.
We have our string here.
We are going to print this out, using a range-for loop, one character at a time.
Then we call the find() function.
And then we carry out our check and calculate the index.
And then we can do something else with the string if we like. So we have an iterator to the first
occurrence of the letter 'l' in this string.
So if we have a loop which starts from this iterator and goes up to the end of the string, then this will
possess all the characters from that 'l' onwards. We cannot use a range-for loop, here because that has to
cover all the elements in the string.
OK, let's try this out. (Get myself out of the way!)
So there is our string printed out, one character at a time. We found the matching element at index 2. (So 0,
1, 2.
Yes, that is correct.)
And then if we print out the string from that iterator to the end, we get the string minus the first
two characters.
So what does this algorithm do exactly?
Well, I have written some pseudo-code here, which is rather naive.
I am sure the actual implementation is much more sophisticated, but this may help you think about what
it does.
So the find() call will take an iterator to the start and end of a range.
So these will be the container'
iterator type. And it will return an iterator of the same type.
Then it has another argument, which is the thing it is looking for.
So this is going to be the same type as the container elements.
Then it has a loop over that
iterator range.
If the dereference iterator is equal to the thing it is looking for, then it has found the match. And then it
can return that iterator.
So that has all finished.
If the loop completes and it has not found a match, then there is no match in the string, and it returns
the iterator for the end of the range.
And one thing I meant to mention, if this check fails and the result is the end iterator, then this
loop is still safe, because it is going to start with the return value from end and then compare that to the return
value from end and that will fail.
So this never goes into the loop, and it never references the end() iterator.
So that's all safe.
OK, so that's it is for this video.
I will see you next time.
But until then, keep coding!