In this video, we'll learn more about the stl vector container.
We already know a lot about it since we've been using it
since very early in the course.
As you know, in order to use the vector container, you have to
include the vector header file.
The vector is probably the main workhorse of the stl.
It's used in a lot of applications.
The vector allows us to create dynamically sized arrays.
The cool thing is that the vector can expand and contract as needed, and
it's handled automatically by the stl.
We don't have to worry about the details, but the vector does give us
some control as to how it can grow.
The vector elements themselves are stored in contiguous memory.
So as the vector expands a new larger area in memory is allocated and the
current elements are moved to it.
Like the std array the vector provides, fast direct access in constant time.
It also allows for rapid insertion and deletion at the back of
the vector in constant time.
However, inserting elements into any other part of the vector other
than the back is not as efficient.
It happens in linear time, which means that the running time increases
linearly with the size of the vector.
The vector supports all of the iterators, and the iterators may become invalid.
This is especially true when the vector resizes and a new area in memory
is allocated for the extra storage.
In this slide, we see a diagram of what a simple vector might look like.
We declare vec as a vector of integers and initialize it to 1 2 and 3.
The vector has a front and a back.
The front in this case is element 1 and the back is element 3.
We typically add elements to the back of the vector using the pushback method.
So in this case, we're adding the element 4 using push back and the 4
is added to the back of the vector.
We can add elements anywhere in the vector, but the back is
the location where the addition of elements is most efficient.
If there's no room and the vector needs to allocate more
space, it will automatically.
Usually, twice the amount of the current space is allocated and the
current elements are moved over to the newly allocated area and then the
new element is placed at the back.
Let's look at a few ways to initialize vectors, and then we'll
see some of its member methods.
In the first example in this slide, I declare vec as a vector of integers
and initialize it to 1 2 3 4 and 5.
In the second example, I declare vect1 is a vector of integers.
And I'm using an overloaded constructor here to create 10 integers
and initialize them all to 100.
Of course, the vector supports copy and move semantics for
initialization and assignment.
In the third example, I'm declaring stooges as a vector of std strings.
And I'm initializing those strings with both std strings and c-style strings.
Vectors also support assignment via an initializer list, just
like we did with std array.
So let's look at some other methods provided by the vector.
Again, please refer to the c++ stl documentation for more detail
on these and other methods.
There's a lot there, and that's the place to look for information,
but let's see some other methods.
Let's start with size.
This method returns the number of elements that are in the vector.
That's pretty straightforward.
The capacity method tells us the current capacity of the vector.
When this capacity is exceeded, that's when the vector will expand dynamically,
and max size tells us what the max size of a vector would be in our system and that's
the number of elements that it can hold.
Usually, this is a really large number.
Vectors also let us access individual elements either using
the subscript operator or the .at method, just as we've seen before.
The subscript operator does not do any bounce checking, and the .at method does.
You can see in the example code that vec at 0 will refer to the 1,
and vec sub-1 will refer to the 2.
As previously mentioned, the vector allows for efficiently inserting
elements at the back of the vector.
This is done with the pushback method.
In this case, we have a vector of person objects.
We can create a person p1 named Larry who's 18 years old, and we
can use the pushback method to insert p1 at the back of the vector.
Remember, all container classes make copies of the elements they store.
So in this case, a copy of p1 is made.
In the second example, we're creating an unnamed person object and adding it to the
back of the vector using move semantics.
The last method we haven't seen yet and it's awesome, it's called emplace back.
This method expects the parameters that would normally be passed
into the person constructor.
And that's what it does it constructs the person object using a person constructor right in place
where it's supposed to be in the vector.
That's really efficient.
No moves, no copies.
It just puts it right where it's supposed to be.
Use this method, it's awesome.
The empty method will return true if the vector is empty and false
otherwise, just as we saw with std arrays, we can swap 2 vectors.
But in the case of vectors, the vector elements have to be the same
type, but the sizes can be different.
And finally, we can use the sort algorithm and any other kind of algorithm to sort
vectors with iterators to copy vectors.
We'll see some of those examples in the IDE.
So let's see how we can insert elements into a vector at a
place other than the back.
First, we'll create 2 vectors of integers,
vec1 and vec2. Vec1 is 1 2 3 4 5,
and vector is 10 20 30 40 and 50.
Now let's say we want to insert some data before the 3 and vec1.
First, we need an iterator to point to the location of the
vector where we want to insert the data before, in this case, the 3.
We can use the find algorithm to easily find the 3 as we've already seen.
Once the it iterator is pointing to the 3 in the vec1, then we could call
the insert method and pass in the iterator it and the element we want to
insert before it, in this case, the 10.
That's it.
Now vect1 contains 1 2 10 3 4 and 5.
So we inserted the 10 before the 3.
That was pretty easy, but we can also insert a sequence of
elements, how, with iterators.
Let's insert the entire contents of vec2 before the 4 in vec1.
We first find the 4 and get an iterator to it.
We'll call it it.
Then we can use the insert algorithm and pass in the iterator it that we want to
insert before and the 2 iterators that will provide the sequence of elements
from vec2 that we want to insert.
In this case, all of vec2.
That's it.
Now vec1 will be 1 2 10 3 10 20 30 40 50 4 and 5.
We inserted a copy of vec2 before the 4.
Very powerful and easy to do.
All right, so let's head over to the IDE.
We'll see these examples, and we'll see some more complex examples as well.
Okay, so I'm back in the IDE.
I'm in the section 20 workspace in the vector project.
And this project has a lot of examples.
I really believe that the best way to learn the stl is through examples, a
real example-driven approach make it a little boring sometimes as I'm giving
you example after example after example.
But I think it's really the best way to learn it.
I've got a lot of examples here.
I'm going to go through them pretty quickly.
So please feel free to pause the video, look at the example
and then continue again.
Let's get started.
I'm including iostream, vector and algorithm.
Obviously, I'm going to use vectors in this example, and we're going
to use some algorithms as well.
And I'm going to use integers mostly, but I'm going to use this
person class in a few places.
It's the same kind of person class we've used before.
A person has a name and an age, it's a string and an integer.
I've also overloaded the stream insertion operator, just to make life easier.
I've got a default constructor.
I've got an overloaded constructor.
And remember, when we're using our own classes with the stl,
always, always overload less than and the quality operator.
Okay, those are the 2 Boolean operators that are being used
by the stl on your own objects.
So that's it.
I'm comparing 2 people.
And I'm comparing whether one is less than the other.
I'm not really using them in this demo, but it's good habit to do.
As far as the operator -- the insertion operator it's right
here same as we've always done.
And then what i did was i created these 2 display functions, one is called display
2, and one is just called display.
I'm going to use display mostly, but I'm going to use display 2.
And the reason I did display 2, just so you can see a different way to write this.
Of course, I could use a range-based for loop to do this,
and I'm doing that right here.
But I wanted you to see the for each algorithm.
We've seen this before as well.
So give me a vector of integers.
And I'm going to do for each.
What's my sequence from the beginning to the end of the vector that was passed
in, so in other words the entire vector.
At each iteration, this lambda expression is going to be called.
X will be passed into it.
X will be each one of those elements in that sequence.
And all I'm doing is just display it.
So it's really the same effect as the range-based for loop.
This function here I wrote as a template function because sometimes
I want to be able to print vectors of integers, other times I want to
be able to print vectors of persons.
So it's nice just to have one function to let you do it.
Here's my template parameter right here t, so I can pass in a vector of anything.
And I can loop through here using my range-based for loop and the auto takes
care of figuring out the type for me.
So it makes life really, really easy.
Okay, so let's start going through these examples.
The first few are going to be really straightforward.
I'm sure you've seen them before.
What I've done is I've already run this, and the output is
over here on the right side.
You can see here in the console.
But what we'll do is we'll go through these examples and
then we'll look at the console.
And like I said, the first few are really, really straightforward.
So let's look at this first one.
I've got vec as a vector of integers, and I'm initializing it to 1 2 3 4 and 5,
and I'm calling that display function.
That's the template function.
It's going to display the vector, and you can see the vector being
displayed right up here, 1 2 3 4 and 5.
Now what I'm doing is -- remember, vector has already been initialized,
so right now I'm using assignment.
This is assignment using an initialization of list, which
is really really cool and handy.
So now vec is 2 4 5 6.
And I'm displaying it using that other display function.
So here I'm displaying vec again.
And you can see vec is now 2 4 5 6.
And then in this case, I'm creating vec1.
It's an object and it's also a vector of integers, but I'm not
using the curlies here, right.
So I'm not using an initialization list.
I'm using an overloaded constructor, that's part of the vector class.
This tells me how many do I want.
This tells me what is each one going to be.
So this is going to create 10 100s.
And on a display vec1, you can see them right up here, all 10 100s.
There are other constructors.
There's a lot of different ways to do that refer to the documentation.
Some of them are are real interesting.
These are the one's that I use all the time.
Okay, so now let's look at test 2.
Test 2 is all about the size, the capacity.
So we understand how this works.
So what I'm doing here is I'm saying vec is again a vector of integers 1 2 3 4 5.
I'm displaying it.
You can see it's displaying right here.
Then I'm asking what's the size of the vector.
What's the max size of the vector.
And what's the capacity of the vector.
So you can see here the size is 5, I've got 5 elements in there right now.
The max size is a really big number, that's how many
elements that vector can hold.
And the capacity is 5 in this case.
What does that mean?
That means that if i exceed that capacity, this vector will increase in size, right.
In other words, the stl is going to allocate space for a larger vector.
Remember, it's all contiguous in memory and copy stuff into it.
So that's exactly what I'm going to force right now.
I'm going to push back 6.
So I'm going to add 6 to the back of this vector.
It's going to be a 6 right in there now.
Then I'm going to display it again, and then display the size max sizing capacity.
We would expect max size not to change right now because
I'm not doing anything else.
So I'm pushing it back and displaying it.
So right here, you can see the 6 at the end here.
What's the size of the vector 6, max size is the same.
But look at the vex capacity here.
Now it's 10.
This is pretty typical.
Whenever you exceed the capacity what'll do, it'll double.
So the next time the capacity will be 20 and then 40 and then 80 and so forth.
That's a very, very typical behavior.
Keep that in mind because if you've got 10000 elements in here.
And you add that 10000 and 1, it's going to go to 20000 big.
When you only maybe need 10000 in a little bit.
So there's ways to help that and l'll show you a couple.
We've got this method called shrink to fit, which is pretty cool.
And this just came about in c++ plus11.
So if I call shrink to fit, it'll shrink the amount of storage
allocated to exactly the vector size.
Okay, so remember, right now we had capacity 10.
Then i called shrink to fit, and I'm displaying it again.
And you can see what's happening here.
Notice that now the capacity is exactly 6.
There's one more method I wanted to talk about we don't use it
very often but it's nice to know that it's there, it's reserve 100.
What you're doing here is you're reserving 100 spaces for
elements, contiguous in memory.
And I'm displaying this memory, this vector again here.
And you can see right here the only difference is right there.
This vector now has a capacity of a 100.
So it won't expand until it hits that 101 element.
All right, so now let's take a look at test 3.
L'll scroll both of these up.
Again, I've got my vec1 2 3 4 5.
I'm displaying it so you can see it displaying right here.
And here all I'm doing is using the subscript operator and the .at method.
Remember, the subscript operator does no bounce checking.
The at method does do bounce checking.
So if we exceed the bounds, we get an exception.
So all I'm doing is I'm putting 100 here, and I'm putting 200 here, and
I'm displaying the vector, and you can see that's exactly what we expect.
So let's move on to test 4.
And again, I know these are a lot of examples.
But after doing this for many many years, I think this is the
best way to really learn this.
For test 4, we've created stooges is a vector of person objects.
Remember, we created that person class earlier.
P1 is Larry and he's 18.
That's a person.
Let's display stooges.
Right now it should be empty, right.
There it is empty.
Now I'm going to push back p1.
That's Larry and display it again.
So now you can see that the stooges vector has just 1 person in it, Larry.
In this case I'm going to push back Moe.
Moe is 25.
I'm not creating a named object here.
So this is going to use move semantics, and it's going to push it in the back.
When I display again, you can see that now I've got Larry and Moe.
And then the last example I'm using the in place back.
And this is awesome, as I said, in these slides.
What we do here is we pass in the arguments that we would have passed
into a constructor, you can see right here, right, the name and the age.
And what it's going to do behind the scenes is actually call the constructor
for us and put curly at the back.
And then when I display again, you can see that I've got Larry Moe and Curly.
Let's move on to test 5.
In this case, I've got the stooges vector again right here.
And I've initialized it to Larry Moe and Curly.
And I'm displaying it, and you can see it displaying right there.
You can see Larry Moe and Curly being displayed.
We can have the front method, and we have a back method.
The front method returns a reference to the front of the front element of the
vector, the back to the back element.
Well, the front one is Larry, and the back one is Curly.
You can see front and back.
So when we display that, we can see front is Larry, back is Curly.
We also have the pop back.
And it removes the element from the back of the vector.
For vectors, when we insert and delete from the back, it's very, very efficient.
And that's typically how we use vectors.
So we're going to get rid of Curly in this case and then display the
stooges and you can see here, Larry and Moe are there, Curly's gone.
So here in test 6.
There's my vector of integers, 1 2 3 4 5, and I'm displaying it right there.
I can use the clear method to get rid of everything in the vector.
So I just removed everything, and I'm displaying the vector
right here, it's empty I'm.
Assigning those 10 integers to the vector and displaying it again.
You can see that being displayed right over here.
And now what I want to do is I want to use the erase method to
erase a piece of this vector.
So I'm going to say vec.erase.
And where do I want to start, at the beginning.
Where do I want to stop, right before that guy, vec began plus 2.
So here's vec begin.
Here's vec begin plus 2.
So what it's going to do is going to get rid of those 2 elements.
And then when I display, you can see right here the 1 and the 2 are gone.
Great, now this example is a little bit more complicated, but it's
really straightforward as well.
And I'm just using a while loop here.
I'm assigning 1 through 10 to the vec again.
And then I'm getting an iterator to the beginning of it.
And I'm calling it it.
And all I'm doing is moving along that vector.
And if I see an even number, I'm deleting it or erasing it.
So in this case, while it is not equal to vec end.
If what I'm pointing to with the iterator is even, then I'm erasing it now.
I don't want to increase the iterator here, right, because I just erased
it so that would kind of skip items.
Otherwise, I do want to increase the iterator because
I didn't see an even number.
And then when I'm done, I just want to display vec.
And you can see right there vectors even numbers are all gone.
For test 7, we've got 2 vectors, and all we're going to do is swap them.
So here's vec 1, here's vector.
I'm displaying both of them.
And you can see them right here.
Then I'm just saying vect2 swap vec1.
And I'm displaying those 2 again.
And you can see that they've swapped.
What's cool about vectors is they both have to be the same type in this
example, but they can be different sizes.
So it's a little different from the std array that we saw.
In test 8, what we're doing is we're sorting.
So we've got a vector of a bunch of integers. They are unsorted.
I'm displaying that guy right here.
You can see test right over here, test 8.
So that's displaying the vector.
I'm calling the sort algorithm, vect1.began vec1.end are my iterators,
so the whole vector, and I'm displaying it again, and it's sorted.
We can use reverse to sort it in reverse.
Let's take a look at this one.
This one is really cool.
This is one of my -- let me spell that right here instructs, this is
one of my favorite inserters to use.
It's called a back inserter.
So let me show you what's going on here.
What we want to do is we've got vec1, which is 1 2 3 4 and 5, and
we've got vec2, which is 10 and 20.
So what I want to do is I want to basically insert 1 2 3 4 and
5 right after the 10 and 20.
Now we can do this a whole bunch of different ways, but I wanted to show
you the back inserter because it's a really, really cool inserter to use.
First thing we do is let's display the 2 vectors, vec1 and vec2.
Remember, we're in test 9.
So we're right here.
We've just displayed them.
Now I'm going to use the copy algorithm.
What am I going to copy.
Well, I'm going to copy vec1 from vec1 beign to vec1 end.
So I'm copying the entire vector1.
But where am I copying it to vector2, and I'm using this guy right here,
which is a really cool output iterator called back inserter.
And what it'll do is it'll insert everything that's
passed into it based on vec2.
So what it's going to do -- remember, the sequence we're going to
get is every integer in vec1 here, that's what we're saying.
Each one of those is going to be passed into the back inserter, and it's
going to insert into the back of vec2.
So when I display vec1 and vec2 again, look what happened right here.
see the 10 and the 20.
And now you see the 1 2 3 4 and 5, this is really cool.
Let's do the same thing now except that's only copy if the elements are even.
So in order to do that, we can start from scratch right here.
So here's my vec1 and vec2.
I'm displaying both of them.
You can see them being displayed right here.
And then I'm saying copy if.
This is a little different from copy.
This has a predicate.
So I'm going to copy from vec1 begin to -- sorry, let me say that again.
I'm going to copy from vec1 begin to vec1 end.
That's where I'm copying from.
In other words, the entire vector1.
And I'm copying it to vector 2 using this back inserter.
Now what do I want to copy, that's where the predicate comes in.
And we're doing it with a lambda.
So what does that say even only, right.
Mod 2 is 0, so even only.
And then I'm displaying these 2 guys again.
You can see right here I'm just playing vec1 hasn't changed, but look at vec2.
It had a 10 and a 20.
But now it has the 2 the 4 the 6 the 8 and the 10 that came from vec1/.
These 2 guys the back inserter and the copy and copy if really
get to know those things.
And if you're ever in a technical interview or a job interview and
you're asked one of these questions blow the person away by using
this, you'll get the job trust me.
I do that all the time.
There's just a couple left here.
Test 10 is a real interesting one.
We're going to use the transform algorithm right here.
And the idea here is I've got these 2 vectors.
And I want to transform over both ranges.
So what I want to do is I want to transform over the ranges so I
want -- the one in the 10 and the 2 and the 20 and the 3 and the 30 and 4
and the 40 and the 5 and the 50 being handled at the same time.
So this is what's going on here.
I'm using transform, and I'm starting at vec1.begin.
And I'm going all the way to the end of vec1.
And I'm just starting at vec2 began.
You don't have to say the end here because it's only going to do this 5 times.
This guy could be really long.
So what's going to happen.
Well, I'm going to use my back inserter and insert the results
of this into vec3, which is empty.
But what am i inserting.
Well, that's the really cool part.
This is going to be called -- this lambda here will be called with both
the 1 and the 10 the 2 and the 20.
So that would be x and y.
And all I'm doing is multiplying them.
And then I'm putting those back into vec3 using this back inserter.
So when i display vec3, you can see right here, this is test 10.
Check it out 10 40 90 160 250.
What is that?
Well, that's 1 times 10 is 10, 2 times 20 is 40, 3 times 30 is 90.
You can see what's happening here.
This is really really neat.
We actually did a challenge that was similar to this when
we did erase way back when.
You could tweak that to make this like a 1-liner.
It's not exactly the same, but you can certainly get it to work that way.
All right, and the last one is inserting and that would be test 11.
And that's where we're at right here.
We've got vec1 and vec2.
Vec1 is 1 through 10, and vec2 is 100 200 300 and 400.
And what do we want to do. We want to insert the constent of vec2
into vec1 before that 5 right here.
So here I'm displaying the 2 vectors.
You can see them right here just as we would expect.
So how do I do this?
Well, I have to use an iterator to do this.
Remember, it's not as efficient to insert things into the center of a
vector as it is on the back of the vector, back is really efficient.
So what I'm doing here is I'm finding that 5 in vec1, right
begin end, the entire vector.
I'm finding the 5, and I get back an iterator.
If the iterator is not equal to the end, I found the 5.
Otherwise, I display this.
So in this case, I did find the 5.
And I'm outputting inserting.
You can see that right here.
And then what I'm calling is I'm calling vec1.insert.
I'm passing in the iterator, and I'm passing the sequence of elements I want to
iterate to insert rather the entire vec2.
So what that's going to do is it's going to insert all of vec2 before the 5.
And you can see right here 1 2 3 4.
Then there's vec2 and then 5 6 7 8 9 and 10.
So that covers this lecture.
There's a lot here to understand.
Please take your time going through this.
Pause the video, go back, try some examples, make these your
own and really learn from this.
That's the best way to do it.