Hello again! In this video, we are going to look at searching algorithms. So these are algorithms which
search within iterator ranges.
When we looked at the string interface for the library string, we saw that it has several member functions
for searching within strings.
For example, if we call find_first_of(), then it will search in the object that it was called on,
and return the first occurrence of an element from its argument.
And we used that to find the first vowel in the string "Hello world".
There is a generic algorithm version of this function,
find_first_of(), and this can be used with any container. Or in fact, anything which supports iterator
ranges.
If we wanted to do this example again, using the generic algorithm, then we would pass the beginning
and end iterators for "Hello World" as the first two arguments, and then the begin and end iterators
for "vowels" as the second two arguments.
This will return, and iterator to the first vowel in "Hello world".
If there is no match, then it returns
the invalid iterator, so we need to check that. And then, if we get a valid iterator, we can use
it.
This algorithm uses the equality operator by default. The equality operator of the element's type. String
in this case.
And in fact, I think all the examples in this video and the next one use the equality operator.
So that's why the equality operator is so important, because it is used for matching and searching for
data. And in programming, that is something we do all the time.
So here is our code.
We have the Hello World string. We have the vowel string. We call find_first_of() with the iterators for
"Hello World" and the vowels, and then we check the return value and we use that to get the data.
Normally, you would not be interested in the index position of the element. The actual data is more
useful.
But in these examples, I am going to show it, as it helps to understand what the algorithm is actually
doing.
So let's try this out. And we get the first vowel is 'e' at index 1.
When we did our search, it found an element with the value 'e', which matches, and it return an
iterator to that element.
If there had been no match, it would have carried on past the last element and returned
the end iterator. if we want to do another search to find the next vowel, then we can just call
find_first_of() again. Then we pass the starting point.
We do not use this iterator because it will start with the letter 'e' and return the same value again.
And if we keep doing that, we get an infinite loop.
We need to start again from the next iterator.
So the next vowel from here,
before the end of the container.
So we need to use the iterator range from the iterator after the result, to the end.
And then the rest of the code will be the same.
So we have got the same code that we had before, for finding the first vowel. And then we call it again
to find the second vowel.
We use the iterator following the result as the start of the rate of change.
And if we get the first vowel is 'e' at index 1, the second vowel is 'o' at index 4. And
then we could call it again, to get the next index. 'o' at index
seven.
The adjacent_find() algorithm will look for two neighbouring elements which have the same value.
So if we called this on "Hello world", it would find the double 'l' as the first match, and it would return
an iterator to the first letter 'l'.
So to call this, we just pass one iterator range, and it will work out where the first match
is.
Found adjacent elements with value 'l' at index 2.
If we want more than two elements with the same value, and we know which value we want, then we can
use search_n().
So this will look for 'n' successive elements which have the same given value. And we can say
what we want the value of 'n' to be, and we have to say what the value is.
For example, we could have a vector of ints, and then we could call this with begin() and end() for the entire
vector.
And then 2 is the length of the sequence.
And 3 is the value.
So we want the first sequence of 2 elements with the value 3, which should be those two.
And let's try that out.
2 elements with value 3, starting at index 5.
(Two, three, four five, yep)
And then finally, there is a search() algorithm which is completely different from search_n(),
but I did not choose these names!
So this is similar to searching for a substring within a string.
We give it two iterator ranges and this will look for the first complete occurrence of that
iterator range in the first one.
So if we are doing this with strings again, we have our "Hello world" string. So that is the first two
iterators, which is the first pair.
And then we have a substring, so that would be the second path.
And this is going to look for the first occurrence of "wo" in "Hello world".
So the substring "wo" is found its index 6.
If I make it something that is not in the string. So "wol".
And there is no result. So perhaps I should say,
"No match found".
Okay, so that substring is not found.
Okay, so that it is for this video.
I'll see you next time.
But until then, keep coding!