WEBVTT 00:00.240 --> 00:06.280 Hello again! In this video, we are going to look at using custom types with associative containers. By 00:06.280 --> 00:11.760 a "custom type", I mean something that is not a built-in type or a C++ library class. 00:12.300 --> 00:17.970 So this could be a class that you wrote yourself, or maybe some classes from a third party library. 00:20.210 --> 00:26.840 We can use these custom types with all the C++ associative containers. So that is map, set, multiset 00:26.840 --> 00:27.800 and multimap. 00:28.400 --> 00:35.150 Either the ordered or the unordered versions. And we can use a custom type, either as the value of an associative 00:35.150 --> 00:37.790 container, or as the key, or both. 00:40.270 --> 00:46.210 As an example, we are going to represent a library of books. Some of you may have actually seen a 00:46.210 --> 00:47.710 physical library of books(!) 00:48.430 --> 00:53.890 If you have not, ask your parents, or maybe your grandparents :) We want to be able to search our library 00:53.890 --> 00:59.470 to find a book, or maybe some books, written by a particular author. So it will need to have keys 00:59.470 --> 01:00.040 and values. 01:01.000 --> 01:03.940 We could have more than one book by the same author in our library. 01:04.630 --> 01:08.860 So we need duplicate keys. And we would like the books to be in order. 01:09.250 --> 01:11.590 So the obvious container is a multimap. 01:13.140 --> 01:18.540 The key is going to be a string, which will be the name of the author. And the value will be an object 01:18.960 --> 01:21.780 of a class, which has details about the book. 01:23.820 --> 01:25.950 So we could write a class which looks like this. 01:26.430 --> 01:29.280 So we call it book, which is very imaginative! 01:30.510 --> 01:32.850 Sometimes it is good to have simple names, which are descriptive. 01:33.630 --> 01:38.850 And then the fields for this, and then the members of this are the title and publisher, which are both 01:38.850 --> 01:42.930 strings, and we have a constructor to initialize those members. 01:44.870 --> 01:51.410 And then to represent the library, we have a multimap. This will have a string as the key, which 01:51.410 --> 01:55.850 will be the author's name, and the value will be one of these book objects. 01:59.490 --> 02:08.040 So here is some code with our book class. The title and publisher members. The constructor. I have added 02:08.040 --> 02:12.150 a friend function which will print out the members of the class. 02:12.570 --> 02:15.720 It needs to be a friend, so it can access the private members. 02:17.250 --> 02:20.640 Then we have our multimap, which will represent the books in the library. 02:21.210 --> 02:27.330 The key is the author's name, a string. And the value is the book class with the details of the book. 02:28.440 --> 02:31.920 And then to add some books to the library, we create a book object. 02:32.730 --> 02:38.820 So we give the title and the publisher as arguments to the constructor. And then we call insert(), 02:39.270 --> 02:42.540 and we provide a pair, with the author's name and the book object. 02:45.090 --> 02:46.920 And I think you may have heard of this author before! 02:49.000 --> 02:53.830 And, by the way, it is well worth adding some or all of these books to your C++ library, 02:53.950 --> 03:00.490 if you want to have one. They all address different requirements, really. "Programming Principles and 03:00.490 --> 03:02.860 Practice" is for people who are starting out in programming. 03:03.190 --> 03:09.310 And it teaches you how to program, using the C++ language. So it might be a bit basic for people who 03:09.310 --> 03:10.090 are doing this course. 03:11.170 --> 03:15.760 "C++ Primer" is a fairly readable reference book, on C++11. 03:16.900 --> 03:24.670 "The C++ Programming Language" is a very technical reference book, and "A" Tour of C++" is a quick guide 03:25.150 --> 03:31.000 for people who already have a good knowledge of other programming languages, and want to learn all the 03:31.000 --> 03:32.800 important features about C++. 03:34.310 --> 03:36.740 So let's see what we get when we print these books out. 03:38.560 --> 03:44.440 So we get the author and the book details. These are ordered by the author. 03:44.560 --> 03:48.940 They are in alphabetical order, because they are using the string's less-than operator to order them. 03:50.410 --> 03:54.220 However, if we look at the details of the books, we see that they are not 03:54.220 --> 03:59.680 in order. So Bjarne Stroustrup has "Programming Principles" first and then "A Tour of C++" at the end. 04:00.860 --> 04:06.920 If we had a real library, then the books would usually be arranged by title for an author. So it would 04:06.920 --> 04:11.630 be nice to have all the books for one author grouped together and arranged by their title. 04:15.580 --> 04:21.100 So the multimap will sort the books in order of their key, which is the author. Books by the same author 04:21.100 --> 04:26.050 will be grouped together, but the titles will probably not be in order. 04:26.590 --> 04:28.630 And we would like to be able to do that. 04:30.790 --> 04:35.260 If we were doing database programming, we would need to provide something called a "compound key". 04:35.740 --> 04:42.040 So that would force the sort process to look at both the author and the title. With C++ associative 04:42.040 --> 04:42.550 containers, 04:43.060 --> 04:46.780 we can do that by writing a class which represents this key. 04:46.810 --> 04:49.930 So we need to have a class which has the author and the title. 04:50.380 --> 04:54.700 And it will make the sort look at the author first and then the title. 04:55.730 --> 04:57.680 So our class would look like this. 04:58.100 --> 05:02.780 I am going to call it book_idx, because it is like an index for the book. 05:03.240 --> 05:08.390 We are going to have the author and the title as fields, and maybe some public functions if we need them. 05:10.470 --> 05:17.280 And then our multimap will have an object of this class as the key, and then the book object as the value. 05:20.660 --> 05:26.270 For ordered associative containers, I hope you remember, the less-than operator is the one which sorts the 05:26.270 --> 05:26.690 keys. 05:27.260 --> 05:32.750 In fact, if you try to create a container and the key does not support the less-than operator, then 05:32.750 --> 05:33.800 that is not going to compile. 05:34.490 --> 05:40.220 We need to provide a less-than operator for our class, and we want to make sure that it is going to 05:40.220 --> 05:42.320 sort the elements in the way we want. 05:43.280 --> 05:49.130 So we need to sort the authors first and then, if the authors are the same, we need to sort the titles. 05:49.580 --> 05:55.460 So the title is going to act as a kind of tie-break if the authors are equal. For an unordered container, it is 05:55.460 --> 05:56.510 a bit more complicated. 05:57.380 --> 06:01.010 We need to tell the container how to hash the keys. 06:01.910 --> 06:04.880 There is a library hash function, which is templated. 06:05.390 --> 06:09.740 It has specializations for all the types in the library and the built-in types. 06:10.220 --> 06:14.000 But if we are using our own class, we need to provide our own specialization. 06:14.690 --> 06:16.280 So we need to write a hash function. 06:16.910 --> 06:19.610 And also, we need to define the equality operator. 06:20.240 --> 06:21.590 So this is a bit more complicated. 06:21.590 --> 06:24.500 So we are going to stick to ordered containers, for this example. 06:29.010 --> 06:33.960 Before we get on to actually implementing the less-than operator for our class, it might be worth having 06:33.960 --> 06:38.910 a quick digression on what it means for things to be equal. In C++, 06:38.910 --> 06:40.320 there is three possibilities. 06:41.390 --> 06:46.460 You can have two objects, which are the same objects in memory. So they occupy the same address, 06:46.970 --> 06:48.890 but they are referred to differently. 06:49.550 --> 06:56.420 So for example, if we have a book, I could say that, "this is my book" and you could refer to it as "James's 06:56.420 --> 06:56.690 book". 06:57.170 --> 06:58.220 But they are still both 06:58.220 --> 07:00.320 the same book. It is still the same copy of the book. 07:01.730 --> 07:06.710 We could have two objects which have different memory addresses, but all their values are the same, all their 07:06.710 --> 07:11.000 members. And that corresponds to having two different copies of the same book. 07:11.870 --> 07:15.560 And then finally, we can have two objects which have some values which are different. 07:15.770 --> 07:22.520 But the values which we are concerned about are the same, and they only differ in things which are 07:22.550 --> 07:23.480 not relevant to us. 07:23.960 --> 07:26.240 So, for example, we could have two copies of a book. 07:26.630 --> 07:28.580 One is hardback, one is paperback. 07:29.120 --> 07:32.720 But if we are only interested in the actual content, then those are 07:33.730 --> 07:38.950 actually, the same thing, as far as we are concerned. And usually in C++, when we say that two objects 07:38.950 --> 07:39.550 are equal, 07:39.910 --> 07:41.560 this is what we are alluding to. 07:44.770 --> 07:47.590 So here is how we would write our less-than operator. 07:47.980 --> 07:49.600 I hope this is vaguely familiar! 07:50.170 --> 07:53.590 It takes an object of the same type by reference to const. 07:55.520 --> 08:02.450 If the authors are the same, we want these to be ordered by title. So if the authors are equal, then 08:02.450 --> 08:07.010 we compare the titles, and we can just call the string's less-than operator, because these are strings. 08:08.790 --> 08:12.810 If we get here, then the authors are different, so we just compare them by the author. 08:14.960 --> 08:23.300 So this is the class for the book index. The author and title members. The constructor. Then the less-than 08:23.450 --> 08:29.360 operator, which we just saw on the slide. And then a function for printing them out again. 08:31.560 --> 08:36.090 And then similar, but not quite the same. Because we have moved the title out of the book field, I have 08:36.240 --> 08:37.500 added some more details. 08:37.860 --> 08:40.500 So now we have the publisher, the edition and the date. 08:43.040 --> 08:49.850 And then we create our multimap object, with the book index as the key, and a book object as the value. 08:51.650 --> 08:55.940 Then we create a book object, so published by Addison Wesley, 08:56.510 --> 09:01.370 2nd Edition, 2014. Then we create an index object. 09:01.520 --> 09:07.210 So the author and the title. And then we add these as, a pair, to the multimap. 09:11.420 --> 09:19.250 And now we get the title and the author, and then the book details. We have the authors in alphabetical 09:19.250 --> 09:19.550 order. 09:20.150 --> 09:25.580 And then we have the books for Bjarne Stroustrup, which are also grouped in alphabetical order. 09:27.440 --> 09:28.670 OK, so there we are. 09:30.290 --> 09:31.520 So that is it for this video. 09:31.820 --> 09:32.690 I will see you next time. 09:32.930 --> 09:35.030 Until then, keep coding!