Hello again! In this video, we are going to talk about the set.
A search is a collection of elements, without any particular structure.
C++ has a class for this in the library, called set.
This is an associative container, so it is going to be the first time we have looked at an associative
container.
It is a very minimal associative container, because the element just has a key and nothing else.
This key has to be unique, so we cannot have two elements with the same key.
The elements in a sets are stored in order using the less-than operator of the key, and the set is
implemented as a tree, because there are efficiency requirements in the language, and that is the only
way to meet them.
Usually, they use a red-black tree.
So this is what a set will look like. And you will notice it looks exactly the same as the diagram in
the last video, and this is because the elements just have a key and nothing else.
To add an element to the set we use insert(). To remove one, we use erase().
We cannot use push_front() or push_back(), because trees do not have a front or back.
These will make sure that the element is added in the right place in the tree.
If we do an insert() or erase() operation, the tree will check whether it is correctly balanced. If it has
become unbalanced enough, it will actually stop the operation and rebalance itself. And then come back
to the operation after it has finished.
So sometimes, very occasionally, an insert() or erase() operation may take much longer than it would normally.
If we try to insert an element into a set which has the same key as an element that is already there,
then the insert() operation will fail and you might want to think about why that is.
And the answer is that elements have to have a unique key, so we cannot have two elements with the
same key.
So that is why it has to fail.
The return value from insert() is a little involved.
It actually actually returns a pair object.
Usually the second member of this pair is the one that we are interested in.
This is a button which will tell us whether the operation succeeded or failed.
The first member is an iterator to an element in the set.
If we succeeded in inserting a new element, it will be an iterator to that new element.
If the operation failed, then we get an iterator to the element, which already has that key.
So that will be the element which cause the insertion to fail, if you like.
So let's try this out.
We include the set header.
We create a set object.
And then we call insert(), to add some elements.
So these are insert certain elements with keys 6, 7, 4, and so on.
Then we try to insert an element with key 3.
The set already has an element with that key, so we expect this to fail.
We get a pair object returned by insert(), and the second member will tell us if this succeeded.
And the first member will be an iterator to the element which caused it to fail, if it failed. Or the
element which we inserted, if it succeeded.
Then we remove the element with key 3 from the set. And then we try to insert it again, and this
time it should succeed.
So there we are.
Those are the elements of the sets.
And you will notice that these are displayed in order.
So when we iterate through a set, the elements are returned in order.
So the set does have this internal ordering of the elements.
We tried to insert an element with key 3, but it already contains one.
Then we removed the element, and then we were able to add another element with key 3.
There are a couple of member functions which sometimes come in useful.
The find() member function will return an iterator to the element which has the same key as its argument.
If there is no element which has that key, then it returns last + 1.
The count() member function will return the number of elements which have the same key as its argument.
So because there are no duplicates, there can only be one element with that key.
Or there may not be any at all.
So the only possible return values are 0 or 1.
So let's go back to the code we had before, and this time we are going to call find.
And this will return the iterator. So if it succeeds, we can look at the value. And perhaps we can do
something with it?
So let's see if we can change the value of the element.
What do you think will happen?
Well, there was a bit of a clue, because it was commented out!
So you cannot assign to a variable that is const.
So it looks as though the element is const, or perhaps just the key to it.
We will come back to that.
And then we called the count() member function as well.
So we do have an element with key 7, from dereferencing the iterator.
And there is one element with key 7.
So, using search with algorithms. We are actually a bit restricted.
We have just seen that the elements are const.
And another limitation is that the elements in a set cannot be reordered.
And you might want to think about why that is.
And the reason is that the set maintains its own, internal, ordering.
If we had some algorithm that reorder the elements, that could conflicts with the internal ordering.
And also, if the elements are not const, then we could change the keys.
And that would, again, conflict with the way that the set organizes its data.
So these are not allowed.
So this means there a lot of algorithms that do not actually support set. But we can use ones, so
long as they just reach a range of iterators and they do not attempt to modify the elements or rearrange
them.
So, for example, we could call find_if(). We pass const iterator, so we are just reading the elements, and
then we have a lambda expression, which returns true if the element has key
7.
So that is really just the same as the find() call we had before.
So let's try that out again.
So this time we are calling find_if(), instead of the find() member function.
And we are also calling count_if() as well, to do the same thing as the count() member function.
And we get the same results.
So what is set good for?
It is very fast at locating or searching for an element.
So accessing elements is very fast.
Inserting and deleting elements is usually very fast.
But if the tree has to rebalance, it can be slow.
The main application of sets is for checking for membership of a set.
For example, if you have a service that some users are allowed to access, you could have a set of
user names.
And then, when somebody logs on, you can check if that username is in the set. And if they are, then
they can go ahead and use the service.
And if they are not in the search, then - sorry.
Another application is for getting rid of duplicates.
So if you have some data, and you want to get rid of all the duplicates, or you are not bothered
about keeping them, then you can use them to populate a search. And there will just be one element for
each distinct piece of data.
For example, if you have a document, and you read all the words from the document into a set, then
there will be one element in the set for each distinct word in the documents.
And then you can call size to get the number of distinct words in the document.
OK, so that is it for this video.
I'll see you next time, but until then, keep coding!