WEBVTT 00:00.600 --> 00:04.680 Hello again! In this video, we are going to have an overview of standard algorithms. 00:06.270 --> 00:10.230 An algorithm generally is a step of sets which are used to solve a problem. 00:10.620 --> 00:13.380 It is quite similar, actually, to a recipe in cooking. 00:13.710 --> 00:19.830 So if you follow all the steps in the recipe correctly, you will get a nice, tasty cake, or pie, or something 00:19.830 --> 00:20.250 like that. 00:21.360 --> 00:27.810 In computing, an algorithm often refers to a technique for searching for data, or sorting data. 00:28.710 --> 00:35.130 It can also mean a technique for solving a specific problem. For example, with the travelling salesman. 00:35.670 --> 00:41.790 If a salesman has to travel to so many towns in a day, which is the quickest route? And there is an 00:41.790 --> 00:42.930 algorithm for solving that. 00:44.550 --> 00:49.970 The Standard Template Library that comes with C++ defines a number of functions in the header. 00:50.640 --> 00:56.490 And these implement the classic sorting and searching algorithms, as well as lots of other useful routines. 00:57.670 --> 00:59.470 So why should you use these? 00:59.950 --> 01:04.900 Well, there is a wide range of useful features. There is more than 100 algorithm functions for you to 01:05.290 --> 01:05.980 play around with. 01:06.700 --> 01:09.310 Using algorithms will make your code shorter and clearer. 01:10.150 --> 01:14.500 Quite often, when you have an explicit loop over a container, you can replace that with a single 01:14.500 --> 01:15.430 call to an algorithm. 01:16.750 --> 01:18.880 The algorithms are extremely flexible. 01:18.940 --> 01:22.000 There is plenty of scope for programmers to customize how they work. 01:22.210 --> 01:27.640 So you can adapt them to your particular problem, and they're also a good example of code re-use. 01:28.060 --> 01:32.560 They've been coded and tested by the people who wrote yout standard library implementation. 01:33.220 --> 01:37.330 They are more accurate, probably, and more efficient than anything you are likely to write. 01:37.330 --> 01:42.340 Unless you are really good and you have lots and lots of time. They can use internal compiler features 01:42.340 --> 01:48.580 and library features which are not available to application developers. And using algorithms will save 01:48.580 --> 01:49.930 you lots of development time. 01:53.060 --> 01:58.490 We saw that the library string has a find() member function. And you can use that to search, but you 01:58.490 --> 02:00.650 can only use it if you have a string object. 02:01.370 --> 02:07.040 The algorithm functions in the standard library are global, non-member functions, which will work 02:07.160 --> 02:11.630 with any kind of Standard Template Library container. And the container 02:11.630 --> 02:14.810 elements can have any type, including ones that you write yourself. 02:15.170 --> 02:19.340 So these are known as generic algorithms, because they are completely generic. 02:23.310 --> 02:28.440 All the algorithms are slightly different, but typically what happens is that you pass an iterator 02:28.440 --> 02:30.090 range to the algorithm call. 02:30.630 --> 02:34.680 So this will say which elements in the container you want the algorithm to process. 02:35.400 --> 02:40.680 If you want the entire container, you would say begin() and end(), or their return values. You can have others as 02:40.680 --> 02:43.500 well. You can process sub-containers just as easily. 02:44.960 --> 02:51.380 The algorithm will iterate over the range of elements, and it will call a function on each element. 02:52.910 --> 03:00.080 And then, usually, the algorithm will return an iterator, representing some element of interest, or a value, 03:00.080 --> 03:02.810 which is the result of some operation on the elements. 03:03.470 --> 03:08.030 For example, if you are doing a find, it will return and iterator to the first matching element. 03:08.810 --> 03:14.720 If you are doing a sum - addition - then that will return the results of adding up all the elements 03:14.720 --> 03:15.370 in the container. 03:19.330 --> 03:23.590 So let's look at the genetic find() algorithm. It is slightly different from the string one. 03:24.160 --> 03:30.040 (Apart from being generic and not requiring a string.) The string version returns an index which is okay. 03:30.760 --> 03:33.190 The generic find returns an iterator. 03:33.760 --> 03:37.750 And the reason for that is that some containers do not have the concept of an index. 03:38.170 --> 03:39.730 So this has to work with every container. 03:40.780 --> 03:44.710 If the character is not found, the algorithm will be return an invalid iterator. 03:45.040 --> 03:51.580 So the string find() returns the index of an impossible element, or an impossible index if you prefer. 03:51.940 --> 03:54.450 And the algorithm returns and impossible iterator. 03:55.420 --> 03:57.340 And that will be the return value from end(). 03:58.300 --> 04:01.000 So that will be an iterator to the last plus one element. 04:02.200 --> 04:04.960 So if we do a search, then it will look like this. 04:04.960 --> 04:09.160 We have these string we are searching. Then we have the find() call. Then we have the iterator 04:09.160 --> 04:11.590 range. We are using begin() and end(). 04:11.620 --> 04:17.110 So that will search the entire string. And we can use the const versions, because we are not going to modify the string. 04:18.160 --> 04:23.020 And then the value we are searching for, which is the first occurrence of the letter 'l'. 04:23.800 --> 04:30.040 And then this will return an iterator. And we can use auto to avoid having to work out what the iterator 04:30.040 --> 04:31.720 type is and how to spell it correctly! 04:33.580 --> 04:38.800 Then we need to check that we got a valid iterator, just as we needed to check the string find() for a valid 04:38.800 --> 04:39.280 index. 04:40.300 --> 04:45.760 So if the iterator is equal to the return value from end(), then we do not have a match and we cannot 04:45.760 --> 04:46.280 use that iterator. 04:46.960 --> 04:48.430 Otherwise, we can do something with it. 04:49.030 --> 04:54.220 For example, here we are printing out the distance between the start of the string and this iterator, 04:54.700 --> 04:57.340 and that will give the index of the element. 04:57.640 --> 05:00.070 So this is actually compatible with the string version. 05:01.240 --> 05:02.440 So let's try this out. 05:02.860 --> 05:04.150 We have our string here. 05:05.170 --> 05:09.640 We are going to print this out, using a range-for loop, one character at a time. 05:10.240 --> 05:12.700 Then we call the find() function. 05:15.290 --> 05:18.080 And then we carry out our check and calculate the index. 05:19.670 --> 05:24.020 And then we can do something else with the string if we like. So we have an iterator to the first 05:24.020 --> 05:26.180 occurrence of the letter 'l' in this string. 05:27.290 --> 05:33.320 So if we have a loop which starts from this iterator and goes up to the end of the string, then this will 05:33.920 --> 05:40.850 possess all the characters from that 'l' onwards. We cannot use a range-for loop, here because that has to 05:40.850 --> 05:42.290 cover all the elements in the string. 05:44.920 --> 05:49.210 OK, let's try this out. (Get myself out of the way!) 05:50.380 --> 05:57.080 So there is our string printed out, one character at a time. We found the matching element at index 2. (So 0, 05:57.100 --> 05:57.610 1, 2. 05:57.640 --> 05:58.360 Yes, that is correct.) 05:59.080 --> 06:05.530 And then if we print out the string from that iterator to the end, we get the string minus the first 06:05.530 --> 06:06.460 two characters. 06:07.750 --> 06:09.940 So what does this algorithm do exactly? 06:10.870 --> 06:13.970 Well, I have written some pseudo-code here, which is rather naive. 06:13.990 --> 06:18.700 I am sure the actual implementation is much more sophisticated, but this may help you think about what 06:18.700 --> 06:19.060 it does. 06:20.260 --> 06:24.730 So the find() call will take an iterator to the start and end of a range. 06:24.940 --> 06:26.650 So these will be the container' 06:26.650 --> 06:30.520 iterator type. And it will return an iterator of the same type. 06:31.480 --> 06:34.960 Then it has another argument, which is the thing it is looking for. 06:34.990 --> 06:37.660 So this is going to be the same type as the container elements. 06:38.830 --> 06:40.740 Then it has a loop over that 06:40.750 --> 06:41.600 iterator range. 06:43.770 --> 06:49.560 If the dereference iterator is equal to the thing it is looking for, then it has found the match. And then it 06:49.560 --> 06:50.670 can return that iterator. 06:51.310 --> 06:52.140 So that has all finished. 06:53.830 --> 07:00.250 If the loop completes and it has not found a match, then there is no match in the string, and it returns 07:00.250 --> 07:02.530 the iterator for the end of the range. 07:03.040 --> 07:09.940 And one thing I meant to mention, if this check fails and the result is the end iterator, then this 07:09.940 --> 07:15.190 loop is still safe, because it is going to start with the return value from end and then compare that to the return 07:15.190 --> 07:17.140 value from end and that will fail. 07:17.950 --> 07:21.850 So this never goes into the loop, and it never references the end() iterator. 07:22.300 --> 07:23.140 So that's all safe. 07:24.290 --> 07:26.140 OK, so that's it is for this video. 07:26.590 --> 07:27.430 I will see you next time. 07:27.430 --> 07:29.440 But until then, keep coding!