WEBVTT 00:00.150 --> 00:07.380 Hello again! In this video, we are going to continue looking at unordered associative containers. 00:07.380 --> 00:13.470 C++11 provides unordered versions of all the associative containers, so that is unordered versions of set, 00:13.830 --> 00:16.050 multiset, map and multimap. 00:17.630 --> 00:24.140 These support most of the usual operations on associative containers. So we can call insert(), erase() 00:24.140 --> 00:25.220 and find(), and so on. 00:26.090 --> 00:29.780 There are also some special operations for managing the buckets. 00:30.080 --> 00:36.780 If you want to get really low level and tune the performance! Operations on an unsorter container 00:37.070 --> 00:40.430 are usually faster than they are for the sorted equivalent. 00:40.850 --> 00:45.740 And that is especially true if you have a large container, with a lot of insert() or erase() operations 00:45.740 --> 00:46.190 going on. 00:49.860 --> 00:56.550 Operations can be slow if the hash table needs to re-size. So, ordered containers need to rebalance 00:56.550 --> 01:02.070 their trees occasionally as they grow; unordered containers need to re-size their hash tables occasionally 01:02.070 --> 01:02.730 as they grow. 01:03.890 --> 01:07.340 And also, if you have a lot of collisions, that can also slow things down. 01:10.880 --> 01:14.510 There are some restrictions on iterators with unordered containers. 01:15.260 --> 01:22.160 We can only use forward iteration, so we cannot use reverse iterators or const reverse iterators. 01:22.610 --> 01:27.890 We can increment iterators into an unordered container, but we cannot decrement them. 01:31.730 --> 01:36.620 These containers do not really have a sense of order, so iterator ranges are not really 01:36.800 --> 01:42.830 all that useful. But you can use them for iterating over the entire container, and you need forward iterators 01:42.830 --> 01:43.400 to do that. 01:44.150 --> 01:49.370 And you can also iterate over elements which have the same key, in the unordered versions of multimap 01:49.370 --> 01:50.360 and multiset. 01:52.240 --> 01:56.620 But if you do that, you cannot use lower_bound() or upper_bound(), because they are not supported. 01:56.980 --> 02:02.980 You would have to use equal_range(), or alternatively the find() and count() that we used, earlier on. 02:05.620 --> 02:10.240 Occasionally you need to work with an unordered container for speed. 02:10.570 --> 02:14.200 But then you have to deliver your results into an ordered container. 02:14.740 --> 02:18.160 For example, you may have to call a function, which takes a map as an argument. 02:21.740 --> 02:27.410 So what you can do, is do the work in an unordered container, and then copy it into a sorted container, 02:27.410 --> 02:29.570 an ordered map, when you have finished. 02:30.350 --> 02:36.290 So you have your unordered map, you do the work with it. And then you create an ordered map, an normal 02:36.290 --> 02:38.870 map, and then you can copy the data into it. 02:39.650 --> 02:41.240 To do that, you need an insert iterator. 02:42.170 --> 02:47.390 And you can do that by providing the return value from end() in the sorted map as the destination. 02:47.480 --> 02:52.580 And then that will populate the ordered map, with all the data from your unordered map. 02:57.710 --> 02:59.000 So let's have an example. 02:59.280 --> 03:04.940 We are going to have the same multimap we have seen before, but this time it is an unordered multimap 03:04.940 --> 03:05.630 with that data. 03:07.640 --> 03:16.400 Then we create a regular multimap, an ordered multimap. And then we have the call to copy, to populate 03:16.400 --> 03:20.240 our ordered map with the data from the unordered multimap. 03:22.590 --> 03:23.680 So let's see what we get. 03:26.190 --> 03:31.920 So, in fact, in the unsorted map, the elements were actually sorted, by chance, in order of their keys. 03:33.510 --> 03:35.820 So I can actually add another element. 03:38.500 --> 03:40.990 And I will be very modest, and have one for me. 03:43.090 --> 03:46.300 I will give myself 99, because nobody is perfect! 03:49.400 --> 03:50.210 OK, that is better. 03:50.420 --> 03:53.930 So, in the unsorted map, they are not in order anymore. 03:54.500 --> 03:58.640 And then when we copy the data into the sorted map, they are all in order of the keys. 03:59.700 --> 04:01.240 OK, so that is it for this video. 04:01.470 --> 04:04.290 I will see you next time, but until then, keep coding!