In the last lecture, we discussed the fundamentals of templates, including function templates and class templates, and how they encourage software reusability. They are especially appropriate when the logic required is the same for many different types. In this lecture, we will discuss the Standard Template Library or STL, sometimes just called the Standard Library. The data structures and algorithms in this library allow you to work with a lot of different types as a result of the power offered by templates. The three broad categories of data and functionality offered in the STL are containers, iterators, and algorithms. STL containers are used for the purpose of storing data and organizing it. The majority of containers are divided into sequence containers and associative containers. Sequence containers organize their data in a sequence accessible by an index. Associative containers organize data so that it is accessible by a special key value. STL iterators as the name suggests, help you iterate through a container. They essentially help you move through containers and find elements that you are looking for. STL algorithms perform tasks on data stored in the STL containers. These algorithms are function templates like we learned about earlier, and can perform operations on the elements in the containers. We will start by taking a look at some containers. Iterators sometimes work behind the scenes and sometimes we request them specifically by asking for the begin or end iterators. We'll discuss algorithms later on. As you can see, we have quite a few really interesting containers we can work with. So, we have sequence containers such as, array and vector we've seen before. The array having a fixed size and the vector being expandable, but we also have deques, D-E-Q-U-E, this is a doubly ended queue. It's similar to a vector, but elements are intended to be added and removed from the front and the back. But you don't really access elements in the middle. A forward list is what we call a singly linked list, where the data is connected to each other data moving forward or in one direction. Data can be removed or inserted anywhere in that data structure. And then there's the regular list type which is a doubly-linked list which means it can go forward and backward really easily. But that's usually handled by the iterators themselves. We also have associative containers. You have the map type which is known as a dictionary in some languages. It maps keys to elements. So like, key value pairs. Duplicates are not allowed in maps. The multimap which is also in the map header file, is the same as the map, but it allows duplicates. Then there's set which stores a sorted set of values. Duplicates are not allowed in a set, but they are allowed in a multiset which is the same as a set except it allows duplicates. A multiset is also in some context is called a "bag." And then you have unordered versions of the maps, sets, and their multimap, multiset counterparts. And of course, we also have something called Container Adapters which aren't really containers themselves. They are used to restrict containers, so that they behave in a particular way. These are based on very well known abstract data types or ADT's  that are used extensively in software engineering and computer science. These consist of the stack, the queue, and the priority_queue. A stack is used to adapt containers such as the deque by default and provide last-in first-out life LIFO access. The queue adapts the deque by default to provide first-in, first-out access. And then, there's the priority_queue which is similar to the queue, and adapts the vector by default. But it is used to retrieve the element with the greatest value. Not just chronologically like the queue but kind of like if you were in an emergency room or something like that and you got in before someone else but the person who came after you had a bigger problem and there's only one doctor. They would get to see them first even though you chronologically came in with your really sore fingernail that got a hangnail or something. The person behind you might be having a stroke, They get priority. That's the same thing as a priority_queue. It's like it does triage. So, obviously an entire course could be made out of using all these containers and container adapters. So, we'll take a couple of the containers along with their adapters, and make some really awesome code, so you get at least a taste of what's going on. So, let's start our exploration by working with the deque. Let's create a project called STLFun1. Create a new project. Empty project, and STLFun1. So, Standard Template Library Fun1. Let's give this a main file, New, and then main.cpp. Include, it helps to spell right. Include iostream. Include deque since we're going to be using it. I think that's it. All right, there's our skeleton. So, deques are made so that you can add elements to the front or the back and also remove elements from the front or the back. So, I'm going to actually set it up so that we'll be able to print the deque fairly easily. So, that usually involves a function. So, deque int deck. And we will paste it down here. Got to get rid of get rid of that extra C. For printDeque, it's fairly straightforward. For all the numbers in the deck, it's going to be just printing it out and then after the for loop, I'm also going to add an additional new line just to make it a little cleaner. And I guess we got to probably use this or it's not going to do much. All right, there's myDeck. I'm putting C K on this one, deck, but it could be myD-E-Q-U-E. myDeck.push_back(1). Don't know why that happened. myDeck.push_back(5). myDeck.push_back(10). And then let's say, First print, printDeque(myDeck) is what's passed to it. And then myDeck.push_front just to test this out, pushing up 20 at the front. myDeck.push_front again, let's say 30 and then we'll say, Next print, and we'll say printDeque(myDeck) and we could of course pop from the front or the back. Also popping means removing. So, pushing ads popping removed. So, this should be familiar to you from the vector push back, but there's also push front and that's kind of how you interact with the deck, is push back, push front and also pop back and pop front. So, let me see here. Let's run this and see what we get. So, debug, start without debugging. All right, the first print as expected, the order that we added them in is the order that they are printed, right? Because it starts at the beginning and since this was pushed to the back, then the next element, then the next element. Each of these were pushed to the back. They become the new back. So, that means this one, the first one that was added, is the first one that gets printed. The next print after we pushed the 20 and the 30 on the front, you'll notice those are in reverse order because they were pushed to the front. Initially we had the 1, 5, 10 when we called push front on 20, 20 would become the new front. So, it would be in front of 1, 5 and 10 but then the 30 gets pushed to the front, so it's the new front and it's in front of 20, and then that's in front of all these. Pretty cool. There are some situations though where we might want to treat the deck a bit differently under the hood. For that, there are container adapters that we looked at briefly just a little bit ago on our tables. We're going to work with the stack container adapter in just a little bit. If you recall, we discussed stacks before in the course. You remember where, when we were exploring functions. Remember that the runtime maintains a stack to keep track of which functions are called and in what order. A stack as we've seen is LIFO, last-in first-out data structure. These are great for any situation in which the most recent element we add to a container is the first element we want to get back. A stack is quite restrictive. It only allows access at one location. It's top, the top is where items are added and from where they are removed. Adding an element to a stack is called pushing an item onto the stack, and removing an element from the stack is called popping an item off of the stack. Let's create another project called StackFun. So, we'll close this project and I'm going to create a new project and we will call this one StackFun. All right. So, let us create a main file here. We'll add some more as we need it after I described what I'm about to do. So, we're going to make a cool little program instead of just a semi boring little tiny, tiny trivial example, which we sometimes do because it's appropriate and it's just simple. Super simple. We're going to do something a little bit more interesting this time though. So, this is going to test if a string is a palindrome. There are other ways to do this, but we'll use a stack. A palindrome if you don't know is a string in which the letters are the same backward as they are forward. We will assume that punctuation is removed, spaces are removed and everything is lower case just to keep things simple. We could enforce all of this in the code but we'll just be good users and this time we'll just pass invalid data. Examples of palindromes are madam, I'm Adam. So, m- a-d-a-m, madam, I-m A-d-a-m, so madam, I'm Adam that's a palindrome. Racecar is a more simple single word palindrome. Civic, c-i-v-i-c is also a palindrome, same back and front. Solos, so like if you have a group of people and they each have solos in a band, s-o-l-o-s. Read it backwards, It's s-o-l-o-s, right? There's many more. We'll take advantage of our stack by placing the letters of the string in it  one by one and then comparing the letters of that string to the characters on the stack. Since the stack characters will be popped in reverse order of what they were added. This is a perfect opportunity to test out what a stack can do. So, enough talk. Let's write some code. So, we need string of course and we need stacks. So, we'll put stack, string and I'm going to write a couple of functions  to help us here, just to make main a little cleaner. So, storeReverse is going to take an original string and the stack is going to be a stack of character reference, reverseStack. We should probably also have an is Palindrome all that does is take the original string. PrintResults will also take an originalString and we'll talk about what each of these does as we fill in some code. All right? I like to give them body's first just like I do with member functions for classes. All right? So, then we'll come back to main and fix it. So, let's see what we're going to do here. So, store reverse is fairly simple. What you do, you can actually do this which is kind of cool, since a string is kind of an array of characters and it actually has an iterator associated with it, we can actually do this. So, we can say for each char c in the originalString, it will allow us for each character to take the reverseStack that's passed in and push. Notice it's not push back or push front, it just pushes under the stack and it's going to push that character. But remember they're going in reverse order because it's last in first out or first in last out, whichever way you'd like. That means the first character we add in is going to be the last thing to come out. The last character we add in which will be the end of the string will be the first character to come out of the stack once we pop the elements. All right. Let me see here. Okay, so is palindrome. Alright. Let's see here. So, a stack of characters will create inside here, reverseStack and we're going to call store reverse. We're going to pass in the originalString that was passed into us from main, will assume, and the reverseStack, there we go. Bool result equals true. And here we go. If the originalString's length is equal to the reverseStacks size, then there's at least a possibility that they're the same because if they're not even the same length there's no way that they're palindromes. Okay? So, results set to false if they're not the same length and then at the very end we return the result. We could return directly here but we're just storing a result value. So, for the original string length we're going to say for char c in the originalString very similar to what we did before currentCharacter equals reverseStack.top So, we can grab the top of the stack and then if currentChar is not equal to c, then we're going to set the result to false and break. Below the if statement, we're going to say reverseStack.pop. So, let's explain this. When we come in here and we're going through every character in the original string. We grab them, the current character from the reverse from the reverse stack. It's actually just a stack but it will have the reverse string in backwards order, basically the string and backwards order on the stack. So, it'll grab the top of the stack which should match the first character. Okay? We could actually stop halfway through but that's an optimization we don't have to worry about. But as it comes down towards the center it's actually cross near the middle but it'll start on each end like racecar, it will be an r as the current character, the first character of the string and then the top of stack will have an r in it also because of car c-a-r. So, then when you come in from each side, because of the pop on the stack and then you go forward in the string it is going down on the stack and forward on the string. The next top will be an a because of c-a-r on the end and r-a-c on the beginning. So, then it keeps on going and then it crosses the middle and reverses, but that's totally fine. We are continuing to do this. And if it ever finds a current character that doesn't equal the character in the original string, then we know it's not a palindrome, so it'll break out. if we started our result as true, we have what we call an optimistic view that means that we assume we have a palindrome and if we're never proven that it's not a palindrome, it is a palindrome. So, I hope that makes sense. Now printResult is just to make our lives a little bit easier. This is going to be is and an origString, a palindrone question, palindrome. Sorry. \t, that's for tab. We'll use boolalpha, so it doesn't print zeros and ones. And then we'll call isPalindrome on the originalString. So, you see how I've divided the labor here. I'm not making is palindrome responsible for doing all the printing or if I'm storing the characters in the string, and I'm not making print do all the work of finding out if it's palindrome, I just break it out into a function because that makes it easier. Alright. Now let's back it up in the main and see what we can get. I think to make it easier, I'm going to make a small string array just size five with some different test cases in it. To make this easy, we could just use strings but we'll have racecar. There as our demonstrative example. This is going to be fudge which is not a palindrome should be a non or a false. Array at 2 is civic. Where 3 is Bob and Array at 4 is dogs which is not a palindrome. So, we then want to print them out each at a time and this will actually go through the whole thing because print result actually calls isPalindrome and isPalindrome calls storeReverse. So, just at the very top level, all we're going to do is say for each string str in the string array, we're going to perform that test on it. So, we're just going to call printResult on str. Maybe print on an extra new line at the bottom. That's pretty much all we've got. That's all we need. So, let's run the program. Debug 'Start Without Debugging'. Alright. So, is racecar palindrome? Yes. Is fudge a palindrome? No. Is Civic? Yes. Is bob? b-o-b? Yes. And then is dogs a palindrome? No. So, it looks like we've got the answers we wanted. So, looks pretty good. So, hopefully that gives you an idea how we can use the stack type to help us. Before we move on though, I'd like to issue you a challenge. You're going to create a project called Queue Project. Even though we didn't test it out yet, another of the container adapters is the queue. Instead of LIFO, last in first out like a stack. A queue is FIFO, first in, first out. For American students, we usually call these lines like you stand in a line at the bank or the gas station or at the grocery store checkout and things like that. For many other countries, the word queue is actually quite natural. We assume nothing can cut ahead of anything else in the queue, so it's strictly first in, first out. if you got in line or in queue, first then you're the first person or entity out. Queues like stacks are used extensively in computer science and software engineering. Print queues, task queues and all sorts of situations requiring FIFO, first in, first out or first come, first serve behavior can use queues. You can still use the push and pop for adding items to and removing items from the queue. So, use those methods just like you would with the stack. Those are the names of the member functions used for consistency, but you should be aware that if you formally study data structures in detail, you will probably use the term n-q-e-n-q-u-e-u-e for adding or pushing an item to the back of the queue and d-q-d-e-q-u-e-u-e for removing or popping an item from the front of the queue. That's actually the reason deque data structures pronounced deck and not d-q, because it would be super confusing because DQ is a method on queues. Alright? Hopefully that makes sense. So, knowing that you can use the member functions, push and pop, and can also use the member function front for accessing the element at the front of the queue, much like we use top for our stack, I'd like you to create a fairly simple program. I want you to enqueue the names: John, Sally, Bob, Sam, Ali and Karen. And then I want you to remove the elements from the queue using pop, which performs dequeuing, to prove that the elements leave through the front of the queue. Instead of reversing the order of elements that were added like a stack does, a queue preserves the chronological order. So, this one shouldn't be too difficult. Just remember to include the queue library q-u-e-u-e library q-u-e-u-e and to use push pop in front to your advantage. You can also use the empty method of the queue which returns a boolean that tells you if the queue is empty or not. So, the empty method e-m-p-t-y. So, pause the video, when you're done, come back and we'll work on it together. How did that go for you? Let's see what we can do together. All right. So, we have our project here. So, I believe we can call it just QueueProject. Right? I think that's what I said. Okay. So, empty project and then QueueProject. And then main file name.cpp using namespace standard. All right? So, we'll just put everything in here. This is very simple. A queue of strings called names and then names.push. This is nqueueing John. So, John gets in line first, then sally, push this is Bob also a palindrome, push Sam, Ali and Karen. All right. So, while not names.empty. Sorry, not names.dot empty. What are we going to do with that? Well, we're going to print out names.front for the front of the queue and names.pop because that's going to dequeue. So, these are all anqueues. All right? Enqueues. We enqueue six different names and they should be dequeued, popped in the same direction we added them; same order we added them. All right. So, let's test this out. Debug 'Start Without Debugging' and there we go. John, Sally, Bob, Sam, Ali, Karen. Good job. That went really well. So, it looks like we're getting the queue-like behavior, FIFO, that we desired. In the next lecture, we'll continue our discussion of the STL and introduce maps, as well as some really interesting and awesome algorithms. I'll see you there.