In this video, we'll learn about the stl set containers.
These are associative containers.
Associative containers are collections of stored objects that allow
for fast retrieval using a key.
The stl provides both sets and maps.
In this video, we'll learn about sets, and we'll learn
about maps in the next video.
Depending on the type of the associate container, they're usually
implemented behind the scenes as a balanced binary tree, something like
a red black tree or as a hash set.
These are very efficient data structures.
So operations on sets and maps are very fast.
The stl has 4 types of set containers.
The, set, the unordered set, the multi-set and the unordered multi-set.
We'll focus mainly on the set since it's the one most often used.
But I'll also describe the others as well.
Let's first talk about the set.
In order to use a set, you must include the set header file.
The set class is similar in concept to a mathematical set.
The elements in this set are ordered by key and no
duplicate elements are allowed.
All iterators are available for sets.
Let's initialize a few set objects.
In the first example in this slide, I declare s as a set of integers and
i initialize it to 1 2 3 4 and 5.
In the second example, I declare stooges as a set of std strings and
I initialize it to some strings.
Then at the bottom of the slide, you can see that sets also support
assignment via an initialization list.
But there are some differences with sets. On the first line,
I'm initializing s as a set of integers and I'm providing the initializers.
But notice that the initializer list contains duplicate elements.
That's not allowed in a set.
This won't cause an error though.
The duplicates are simply ignored and we end up with a proper set.
Also notice that the set is sorted.
The size method returns the number of elements that are in the set and
max size tells us what the maximum number of elements a set can hold.
Remember, sets do not allow direct access to elements, so we can't use the
subscript operator or the .at method as we have with other containers.
Sets also don't have a front and back.
So methods like push back and pop back in the front
versions do not apply to sets.
So how do we add elements to sets.
Simple, we use the sets insert method.
We can also use the in-place method if we want.
In the last statement on the slide, we insert 7 into the set.
If 7 is in the set, it won't be added again.
If it's not in this set, then it will be added and it will be added in order.
So let's talk a little bit more about the insert method.
Suppose I have an object p1 that's a person object, in this case Larry 18.
I also have p2 as a person object, Moe 25.
We can insert p1 into the stooges set by simply calling
stooges.insert and passing in p1.
If the element is not in the set, it will be added.
Otherwise, it won't be added.
The set class uses the overloaded less than operator to determine
if the element exists in the set.
That's fine, but sometimes we want to know whether an element
was inserted successfully or not.
The insert method returns a std pair.
Remember, std pair we talked about it a few times in this section,
and we'll talk about it some more in the maps video as well.
The pair object that's returned has its first attribute as an iterator
to the element that we just inserted or an iterator to the duplicate
element that's already in the set.
And then the second attribute is a Boolean that indicates whether the
operation was successful or not.
That's pretty cool.
Now we have all the information we need and we can do whatever
we need in our program.
We can also erase elements in a set very easily.
S.erase 3 will erase the 3 in the set s if it exists.
We can use the sets find method to find the 5.
And if it exists, delete it by passing the iterator to the erase method.
Notice that the sets find method is different from the find function
in the stl algorithms library.
You should use the sets find because the sets find knows all about the
internal implementation of the set, and it's going to be much more efficient.
Finally, we can use the count method to see how many times
an element appears in a set.
If you think about that it doesn't make a lot of sense, right.
I mean a set can only have an element in there once at most.
But in this case, it's real handy to tell whether an
element is in the set or not.
If we get back to 0, we know it's not in the set.
If we get back a 1, it is in the set.
We're going to use this in multi-sets because multi-sets can have duplicates.
So this method is really useful there as well.
Finally, as with all other stl containers s.clear removes all
of the elements from the set, and s.empty returns true if the
set is empty or false otherwise.
Well, that's a quick summary of the set class.
Please refer to the set documentation since there's
more and many of the methods I show you have variants as well.
So let's talk about the other set classes.
First, let's talk about the multi-set class.
It's also defined in the set header file.
A multi-set is a set that's ordered by key but it allows duplicate elements.
All iterators are available.
The unordered set is in the unordered set header file.
The unordered set is a set that's unordered, and it does
not allow duplicate elements.
Due to the way that unordered sets are implemented, elements
can't be modified in place.
If you need to change an element, you have to remove it and
then insert the updated one.
Also unordered sets do not allow reverse iterators.
The last type of set provided by the stl is the unordered multi-set.
The unordered multi-set does not order elements and it does allow duplicates.
Again, no reverse iterators are allowed.
As you can see the stl provides powerful set classes for nearly
every need, however, by far the most used is the set, and that's
one we're going to focus on.
So let's head over to the IDE and we'll look at examples of using sets.
Okay, so I'm back in the IDE.
Again, I'm in the section 20 workspace, and I'm in the set project.
And what I've got here is I've got the same person class and I won't
bother going over it again we've gone over it a bunch of times.
I haven't made any changes to it since the last time.
But I do want to bring that to your attention again the operator
that we're using for the operator less than is comparing ages.
Okay, so we're considering one person less than the other
based on the age, not the name.
And that's going to be important because the set uses that operator.
So when we see these guys sorted, you're going to see them sorted
by age rather than by name.
And that's important to understand.
A lot of people think that it's this operator right here
that's doing it, and it's not.
Okay, so let's get started.
There's 3 tests here.
So not as long as the other videos, but let's start with test 1.
And you can see the output right up here.
You can see that's where the test 1 is right here.
So let's start.
I'm going to create a set called s1.
And you can see it's a set of integers.
You can see the consistency with the syntax across the entire stl.
And I'm putting in 1 4 3 5 2.
Notice I did that on purpose.
I changed the order.
The sets are ordered by default.
So when I display s1, you can see that it's being displayed in
order, in this case, integer order.
If I had put in the stooges with ages, then we get a different order.
I'm doing that in the next test.
In this example here, I'm assigning this initializer list to s1, but notice
there are duplicates in here, right.
There's duplicates all over the place here.
Duplicates aren't allowed in sets.
This will still work.
This will work just fine.
When I go to display s1, you can see that the duplicates were not
handled, of course, they're omitted.
So it's not going to add duplicates to a set that's
not going to allow duplicates.
Then we've got right here we're inserting 0 and we're inserting 10
and then we're displaying it again.
And you can see that right there, there's the output.
You can see the 0 at the beginning and the 10 at the end.
So they were inserted where they should have been inserted,
which is exactly right.
Now let me just scroll up here just a little bit.
And we're right about here on line 50.
I'm seeing how many times does 10 occur in the list?
This is going to return an integer.
It's either going to return 0 or 1, in this case of a set because the set
either has the element in it or not.
There is the multi-set, which allows multiple entries, right, duplicates.
In that case, this could return 2 or 3 or 4 depending on how
many times that element exists.
But in this case, I'm saying is the 10 in the list.
This will either return a 1 or a 0, 1 being true 0 being false.
So 10 is in the set or 10 is not in the set.
We know 10 is in the set because we just added it right here.
So I expect to get back 10 is in the set.
Okay, and now I'm using the find method here.
I'm using s1.find.
I'm not I'm not using std find which is in the algorithms library.
I'm using the sets version of find.
A lot of people use the other one.
The other one is a very generic type find that's going to use an iterator
and just search through the entire set.
This guy's real smart.
This one understands how the set is implemented behind the scenes.
So if it's implemented as a balanced binary tree, it's going to be
pretty smart about finding things.
So let's find the 5 in the set.
Is the 5 in there?
Absolutely, it's in there right here.
So what are we going to do?
We're going to assign the results of that to an iterator.
If we get back the end of the set obviously, it wasn't there.
If we don't get it back, then we found the 5 and what's pointing to
it, so that's what we got right here.
We know it's in there.
And that's what we got back.
We can clear the set and then display it again.
And obviously, that clears out the set just like it
does with all the containers.
Okay, so there you go.
Hopefully, the consistency is is paying off.
Like I said, there was a method to my madness with all these examples.
Usually, when you see a lot of them and more and more, you'll see the
pattern and it just really clicks.
So now let's see the test 2.
What we've got here is a set of person objects.
And we'll call them stooges, and we said the person had a name and
age. I just put 1 2 3 here because I want to show you the order that
these are going to be put in.
So now when I display stooges, look at them right here.
That's the order Larry 1, Moe 2, Curly 3.
Notice that it's ordering by age, 1 2 3.
It's not ordering by name.
Otherwise, Curly would be the first one, right.
So that's important to understand.
It's using operator less than to do the ordering.
All right, so that's what it's using right here.
So we can emplace James 50.
And we can display the Stooges again.
And you can see that at this point James 50 was added at the end because
the 50 is what it's using to order.
So this really drives the point home.
Suppose I want to emplace Frank 50, it won't let me because it's
using the 50 to decide whether to put it in there or not.
So according to this, that 50 is already in there.
Now had I checked to see that the that the upper or less than was the name
and the key and the age I'm sorry then this would have definitely worked.
But when I display it again right here, there's no Frank in there.
As far as this is concerned, it already exists.
All right, so now we've got a couple of more output statements.
Let me scroll up a bit, and I'll show you how these work.
In this case, I'm finding Moe 2 in the list.
I know Moe 2 is there.
I'm going to get an iterator back.
And if it's not equal to the end of the list, then what
I'm going to do is erase Moe.
That's all I'm doing. I'm not displaying Moe, I'm erasing Moe.
Then I'm displaying stooges.
And you can see right here that Moe right there is
gone, which is kind of cool.
Now this is the one that really shows you how the power of that operator.
In this case, I'm finding a person whose name is x and whose age is 50.
This doesn't come into play because I'm not using that in
my overloaded less than operator.
So it's going to find James there at 50.
And it's going to erase James.
And then I display stooges again, you can see that James is gone.
This gets a lot of people when you're first starting out with the
stl, a lot of these containers.
Some of them use equality, some of them use less than.
The set uses the less than.
So be aware of that.
The final test is this guy, and this is important one because it
shows you what's what happens when we insert some data into a set.
Let's just start up here first.
I'm creating a set of std strings, and it's called s.
And I'm putting in there abc.
Now obviously we're using strings.
So it's going to use the string order to sort.
I'm displaying s and you can see abc right here is displaying.
Actually, you know what let me scroll that up just a little bit so
it kind of aligns a little better.
There we go.
So we're displaying abc right here.
Now I'm inserting a d and I'm displaying s.
You can see the d has been inserted in here.
But notice at this time, I assigned the return value of the insert method
to this guy right here, result.
And I'm using auto.
What I'm getting back here is a std pair.
Remember, the std pair has 2 attributes, first and second.
In this case, first is an iterator that's pointing to either the d
that we just inserted or the d that's already duplicated in there
that didn't allow me to insert.
In either case, I'm getting an iterator to the element that I'm inserting or
it's copy that's already in there.
Hopefully, that makes sense.
Then the second part of the pair -- the second attribute is
going to have a boolean true false was the insertion successful.
So I've changed this to bool alpha so it displays the true false value.
And here I'm displaying first.
And we expect that d.
You see it right there.
So we we either got a d that we inserted or the
d that was already there.
That's when we look here.
So if this guy is true, it is right here that means our
insertion was successful.
Had it been false?
That means that i already had a duplicate in there.
Okay, I know it can be a little confusing, but it's it makes
sense when you think about it, and this is pretty cool.
If you think about it what's going on here is I've got a return from a
function that's returning multiple items, right, which is kind of neat.
It's really wrapping it up into a one pair, but even so I can still
get to those pieces of the pair.
Some other functions return tuples, which can have even more than 2.
Okay, so let's do that last one right here.
And in this case, I am inserting the a.
And I'm right here.
This is where I'm at right now.
I'm inserting the a and I'm displaying s.
Now the a was already in there.
So I'm displaying it right here.
And now what I'm doing is what's first.
Well, first was the a.
It's the iterator that's pointing to the a that was already there,
that's why I'm getting that.
And when I display the results with the second attribute,
now I'm getting the false.
So right here I know that that insertion was not successful because
there was a duplicate in there already.
So that covers sets.
What we're going to do in the next video is cover maps.
And then the challenge for the sets and the maps is going to
incorporate using sets and maps together, which is kind of cool.
All right, so in the next video, we'll talk about maps.