In this video, I'd like to do an overview of the basic elements
of the c++ standard template library and see what it's all about.
The stl is a library of powerful, reusable, adaptable,
generic classes and functions.
Okay. So what do all those words mean.
Well, the stl is powerful.
We've already seen a bit of that power when we use the vector class.
The stl is reusable.
Remember, when we created vectors of integers and doubles and accounts and so forth,
we didn't have to do anything except tell the vector what we wanted it to hold.
The stl is adaptable.
It provides containers, iterators and algorithms
that we can adapt to make them do whatever we need them to do with our programs.
Finally, the stl is implemented using template, functions and classes.
We'll learn about c++ templates in the next few videos.
They're one of the features that makes c++ so powerful.
The stl is a huge class library.
We'll only be scratching the surface in this section.
But once you understand how to use the stl,
the principles we'll learn will apply across the entire stl.
The stl was developed around 1994
by Alexander Stepanov, and even today is considered one of the best
designed generic class libraries ever created.
So what is the stl?
Well, at its core, the stl is an assortment of commonly used containers.
We'll see some of these containers in the next slide.
The algorithms provided by the stl
have published and well understood time and size complexity information.
That means that when you use the containers and algorithms in the stl,
there are no surprises.
You know exactly how the algorithms behave as the size of the collection increases.
Complexity theory is beyond the scope of this course,
but it's an important part of software development.
The stl has been around a long time.
It's been tried and tested across many millions of lines of code.
The stl is consistent, fast, type safe as well as extensible.
The stl has three main components:
containers, algorithms and iterators.
Containers are collections of objects or primitive types.
These include array, vector, deck, stack, set, map and more.
Algorithms are functions for
processing sequence of elements from containers.
The stl has about 60 algorithms that can be used
and extended to work with any type of data.
These algorithms allow us to find a specific element in a container,
find the max or min element in a container
count, the number of elements in a container, accumulate
or sum up the values of container elements,
sort containers. And that's just a few examples,we can do much, much more.
Finally, iterators generate the sequences of elements from the
containers that the algorithms use.
There are several types of iterators that allow us to generate sequences of elements
in various ways.
Note that one of the beautiful aspects of the design of the stl is that the containers,
algorithms and iterators are designed totally independently from one another.
Yet, they work together seamlessly.
Also note that I said the stl has three main components.
It also has a few other components such as functors and allocators,
but we won't be covering those in this section.
Before we get into the details of the stl,
let's see a simple example of how we could use some of its functionality.
We'll use a vector of integers for these examples since we're already familiar with vectors.
In this example, I'm including the vector and algorithm header files.
Vector allows me to work with vectors and algorithm allows me to use the stl algorithms.
So let's create a simple vector of integers.
We'll call it v, and initialize it to three integers 1 5 and 3.
Now suppose we want to sort that vector.
We can use the stl sort algorithm to do that,
but the sort algorithm needs a sequence of objects to sort.
That's where the iterator comes in.
We provide the sequence using v.begin and v.. End
this provides the sort algorithm with the integers in the vector v
from the beginning element to the ending element, in other words, the entire vector.
That's it.
Now we can display the vector using a range-based for loop,
and we can see the elements in the vector are now sorted.
Pretty easy, right. The iterator we used
produced a sequence of all the integers in the vector,
but we could have easily provided only a subset if that's what we needed.
So suppose we had a need to only sort the first half of a vector,
we could modify the iterator to produce just the first half of the elements.
Also we aren't restricted to using a vector.
We can sort just about any stl container exactly the same way.
Also, we can extend the sort algorithm to tell it exactly how to compare
the elements when sorting.
For example, maybe we have a vector of account objects,
and we want to sort them by balance.
Suppose that now we want to reverse the order of the integers in this vector.
We can use the stl reverse algorithm to do that.
The code is exactly the same, but we use the reverse function instead of sort.
And when we display the vectors elements, we get 5 3 1, as we expect.
Also, I should mention that behind the scenes,
the ranged based for loop is itself an iterator. We'll talk more about that later.
Now let's see a different type of algorithm function, the accumulate function.
In this case, I want to add up
all the integers in the vector and store the result in a variable called sum.
To do this, I can use the accumulate function.
Notice that the function has parameters. The first two are iterators:
where do I start, where do I end.
This produces the sequence of elements that the accumulate function will process.
The third parameter 0, in this case,
is what the running sum will start at, typically 0, but we can use any number.
We want the type of this third parameter is very important.
So if you want to sum integers, use 0.
If you want to sum doubles, use 0.0
the total is stored in sum and in this case we display 9, which is 1 plus 3 plus 5,
the sum of the elements in the vector
From these simple examples, you can see how powerful using containers,
iterators and algorithms can be.
Now let's talk about the various types of containers provided by the stl.
We have three basic categories of containers:
sequence, associative and container adapters.
Sequence containers are containers that maintain the ordering
of inserted elements.
These containers include array, vector, list,
forward list and deck.
We'll discuss each of these containers in this section of the course.
Associative containers insert elements in a predefined order
or no order at all.
For example, a set is a collection of elements where there are no duplicates,
but there may be an order associated with it or not
we've got the option to choose whatever one we want.
A map is like a dictionary, where we associate a word
with its definition. There are many variants of this category.
So we can have ordered sets, unordered sets, sets that allow duplicates,
maps that allow duplicates and so forth.
These are very powerful data structures that are often underused.
We'll talk about them in this section, and I'll show you how to use them.
The last category container adapters
are variations of the other containers.
This category does not support iterators so they can't be used with stl algorithms,
but they're so commonly used in programming that the stl provides support for them.
These include the stack, the queue and the priority queue.
In this slide, you can see that the stl has several types of iterators.
Input iterators make container elements available to your program.
Output iterators can iterate over a sequence
and write an element to a container.
Forward iterators can iterate forward over a sequence and can read or write any element.
Bi-directional iterators are like forward iterators,
but they can iterate over a sequence in both directions.
And finally, random access iterators can use the subscript operator
to directly access elements. We saw that with the vector class.
Finally, we have the stl algorithms. As I mentioned previously,
there are about 60 algorithms in the stl.
And the algorithms are classified into two major groups:
non-modifying and modifying algorithms.
Depending on whether the algorithm modifies the sequence, it acts upon.
As you can see, there is a lot to the stl,
and we can't possibly cover it all in detail in a single section.
In fact, entire books have been written about the stl.
But by the time you get to the end of this section,
you'll understand the fundamentals of the stl
and be able to use stl containers, iterators and algorithms
to solve real problems.
But before we get to the stl, let's talk a little bit about generic
programming and templates so that we can understand the design behind the stl.