Hello again! In this video, we are going to continue looking at unordered associative containers.
C++11 provides unordered versions of all the associative containers, so that is unordered versions of set,
multiset, map and multimap.
These support most of the usual operations on associative containers. So we can call insert(), erase()
and find(), and so on.
There are also some special operations for managing the buckets.
If you want to get really low level and tune the performance! Operations on an unsorter container
are usually faster than they are for the sorted equivalent.
And that is especially true if you have a large container, with a lot of insert() or erase() operations
going on.
Operations can be slow if the hash table needs to re-size. So, ordered containers need to rebalance
their trees occasionally as they grow; unordered containers need to re-size their hash tables occasionally
as they grow.
And also, if you have a lot of collisions, that can also slow things down.
There are some restrictions on iterators with unordered containers.
We can only use forward iteration, so we cannot use reverse iterators or const reverse iterators.
We can increment iterators into an unordered container, but we cannot decrement them.
These containers do not really have a sense of order, so iterator ranges are not really
all that useful. But you can use them for iterating over the entire container, and you need forward iterators
to do that.
And you can also iterate over elements which have the same key, in the unordered versions of multimap
and multiset.
But if you do that, you cannot use lower_bound() or upper_bound(), because they are not supported.
You would have to use equal_range(), or alternatively the find() and count() that we used, earlier on.
Occasionally you need to work with an unordered container for speed.
But then you have to deliver your results into an ordered container.
For example, you may have to call a function, which takes a map as an argument.
So what you can do, is do the work in an unordered container, and then copy it into a sorted container,
an ordered map, when you have finished.
So you have your unordered map, you do the work with it. And then you create an ordered map, an normal
map, and then you can copy the data into it.
To do that, you need an insert iterator.
And you can do that by providing the return value from end() in the sorted map as the destination.
And then that will populate the ordered map, with all the data from your unordered map.
So let's have an example.
We are going to have the same multimap we have seen before, but this time it is an unordered multimap
with that data.
Then we create a regular multimap, an ordered multimap. And then we have the call to copy, to populate
our ordered map with the data from the unordered multimap.
So let's see what we get.
So, in fact, in the unsorted map, the elements were actually sorted, by chance, in order of their keys.
So I can actually add another element.
And I will be very modest, and have one for me.
I will give myself 99, because nobody is perfect!
OK, that is better.
So, in the unsorted map, they are not in order anymore.
And then when we copy the data into the sorted map, they are all in order of the keys.
OK, so that is it for this video.
I will see you next time, but until then, keep coding!