In the previous lecture, we began our discussion of the STL or Standard Template Library. We looked at decks and also used two container adapters, stack and queue, which used the deck under the hood in order to provide LIFO and FIFO access to the elements, respectively. Since we discussed a sequence container already, the deck, in the previous lecture, we will discuss an associative container in this lecture. We will look at the map data structure and see what we can do with it. We will also look at the algorithm library and see some of the cool stuff we can do with that as well. First, let's work with the map data structure. A map is sometimes called a dictionary in other programming languages. It is a data structure representing key-value pairs. Examples would be, of course, actual dictionaries, glossaries of terms, or even the contacts in your phone.

The value of a map type can be quite complex or remarkably simple. You can think of the key as like an index but one that isn't restricted to be an integer type. We often use a string as the key regardless of the values type. Let's create a project called ContactsFind. So, create new project. Empty project.

ContactsFind. Let's create a main file, main.cpp, and fill in some skeletons. So, we need iostream. We're going to need strings. We're also going to need the map type. All right, so pretty simple. So, let's just make a simple map. Now, what we have here. You'll note that I have map and then string, string. So, there's not just one type here like there would be for vectors or decks or things like that. That's because you have to specify the key type and also the value type. In this case, we're using string for both. And we can kind of use array's syntax but we're not restricted to integers. So, let's say John Baugh is at 313-555-5555. Bob Robinson. Is that? I guess we probably need to make this a string. That's funny. Let's fix that. Got a little bit too excited about the phone number, 734-555-5050. And then we have Sally Snorkle who is 810-555-8888. go. Now, the actual types that we use here, the actual type the map holds is actually called a pair. And these are specific types. In this case, it's a pair of strings we'll call element, and the pairs, each pair. As we go through the contact we'll have element.first which is the key, and element.second which is the value. All right.

So, of course, we need to run it. Give it a test and then we'll come back and talk about it. Debug. Start without debugging and we have, as expected, all the different key-value pairs. So, the first gives us the key like Bob Robinson, John Baugh and Sally Snorkle. Then we have the value, you'll notice that is the phone numbers associated with each of the keys. Excellent. So, what we actually find from the code is that the elements of the map, again, are type pair. This is what we call a structured type or struct, which is similar to a class, but its members are usually simpler and are all public by default. The pair type has two public fields: the first and second. They do exactly what you think they would. First is the key and second is the value. Now, it's important to note that many C++ developers like to use shortcuts and simplify their coding. In fact, developers of almost all languages do this. So, when working with maps, it's actually more common to iterate over them using the auto keyword instead of explicitly spelling out the map paratype. So, we could change the code to look like this instead of pair string-string. We just put auto.

Now, this does not make C++ a weak typed or weakly typed language. What it does is it infers the data type from context automatically for us. So, it's still a strong data type. So, let's run it and make sure we get the same type of output, and as expected, we do. So, Bob Robinson, John Baugh, Sally Snorkle and the corresponding phones. So, it works like we expected. Excellent. Now, let's take a quick detour and look at a couple algorithms provided for us in the STL. We need to include the algorithm library to get anything to work right. And there are over 80 algorithms that help you work with the STL containers and much more. Everything from searching to swapping ranges, to replacing, removing elements, rearranging elements, and permutations. You name it, there's probably an algorithm available for it. We're just going to look at a couple of them. The count algorithm and the replace algorithm. The count algorithm, as you probably guessed, counts occurrences of a particular element, and replace, as the name suggests, replaces occurrences of an element with something else. Let's start by creating a new project called AlgorithmFun.

File close to get rid of this solution, create a new project. Empty project and AlgorithmFun. All right. Let's make main, main file right here. We're going to put main.cpp and we need a whole lot of libraries, iostream, the C standard library. We'll make use of this and C time. So, maybe randomizer, include vector. Include algorithm. Using namespace std, int main, and return zero. Now, we're going to actually do some kind of cool stuff. We're going to generate some random numbers and put them in a vector. And we're also going to count the number, of say, 5s that we see here, and do a couple other things with replace. So, we're going to use some functions that we write to make our lives a little bit easier. So, the first one is going to be called fillVector, takes a vector reference. Remember this is more efficient. Now, since it's modifying the vector, we cannot make it constant. void printVector, this one we can make constant, a constant reference, because we are just going to print it. We're not modifying the vector and also count fives. We can make another constant reference to the vector. All right. So, far so good. I'm going to copy these three right here.

Ctrl + C on windows, command + C on mac. We're going to go down here and paste, so ctrl + V or command+V, depending on what system you're on. And we have the bodies of the different functions. Let's fill these in first. So, for fillVector it takes a vector and fills it. So, we need to seed the random number generator. So, we don't have to explicitly type out numbers. And let's say that I'm going to make 20 Different numbers ranging from 1 to 5. So, for int i equals zero, i less than 20, i++. And we're going to maybe have a temporary variable we'll use. So, let's actually do that. That'll be making a little bit cleaner. Have attempt declared outside the loop. And we're going to say temp equals now to get it one through five. Remember that random returns an arbitrary number up to it's maximum. If we do modulus five, that will mean it will never get to five. It'll go up to four. And then since it's imagers will be 0, 1, 2, 3, 4. But remember with random number generators, we can shift the value up by one and that will make it go from one through five. We 're going to say one through 5 inclusive. Right, awesome.

Now, once we have that temporary number, we want to fill the vector with them. All right, looks good to me. printVector should be pretty simple. So, there's nothing to be intimidated about when we get to writing functions. Obviously we've been doing it for a really long time, so hopefully some of this stuff is becoming less intimidating. When you first started functions, it might have been, "Wow. This is really crazy how I'm ever going to learn it." And now it's hopefully like second nature. So, this we're going through each element of the int holding vector, int element in each in the vector, we go through it. Print out the element. And what do we do with count fives? Well, we're going to use explicitly instead of doing it manually with a loop, which we could do. We're going to use the count algorithm. So, the way we do this, a lot of algorithms are like this, I'm going to say numFives count and you pass it three arguments in this case, we're going to pass it the iterator begin, the iterator to the end, which is actually one step beyond the actual last element, begin points essentially to the first element and end points to a space after the last element. And then you pass in the value that you're looking for and then we'll say, "number of fives:" and then just print numFives. All right, so let's fill in main. We'll make a vector, oops, and we'll call fillVector, printVector, and we'll call countFives and then we'll put Replacing 5s with 99s. So, what we're going to do now is use another algorithm of the STL. I'm going to call it replace, and this particular one takes four arguments. myVector.begin() Many of them, or most of them start like this. myVector.end(), find a 5, and anytime you do, replace it with 99. So, that's what those arguments mean. And you can look that up, obviously, on the C++ references we've used throughout the course, google.py, whatever you prefer. printVector we count the fives again and then print the whole vector out one more time. All right. Sounds good. Let's run it and see what we get. Debug, Start Without Debugging. So, this prints out the initial list here of values or vector values. It'll tell me how many fives were in it because it counted them. There's one there and two, no other ones, and that says Replacing 5s with 99s. And then it does another count of the fives proves that there's no fives left. And you notice the stick out like a sore thumb now because they have two digits, 99s. Pretty good. Let's run it again and see what we get, and this time there are 6 fives. So, there's actually quite a few. So, we know it's randomly generated so. 1, 2, 3, 4, 5, 6. There we go, six of them out of the 20. And then it replaces them with 99s and again they stick out like a sore thumb. Pretty cool. So, you keep running and getting different answers most of the time. Pretty much all the time sufficiently random for us. So, it's looking pretty good. So again, note our use of the iterations return by begin and end on the vector class. These methods are available on many other containers as well.

Note that begin points to the first element again and, and is actually an iteration that is immediately beyond the scope of the container so it doesn't represent the last element. Great work everyone. Before we move on, I have a short challenge for you. Using the AlgorithmFun project. I'd like you to call the sort function from the STL algorithms. It can simply take the beginning and ending iteration as its two Parameters. So, once you sort the vector, print it out again and verify that it's now sorted. So, when you're ready, pause the video come back when you're done or if you need some help. How was that little exercise? Hopefully not too bad. Let's work on it together and add a little bit of fun to the algorithm project. So, let's see what we want to do here. So, all I want to do really is inside of this, inside of main. After the final print vector, I'm going to add some stuff. So, just maybe an in endl just to keep things organized and then say "sorted." And then we want to call sort(myVector.begin(), myVecto.end()). And that's really it. So, then we're going to printVector(myVector). Right? So, that's how simple it is. You just, it's literally simpler than the replace and even the count two arguments. There are versions of it with more arguments, and you can look at those on your own time where you can define how do we sort this if it doesn't know how to sort them. But let's see what this does. Debug, Start Without Debugging. And we have a bunch of 1s, a bunch of 2s, a bunch of 3, 4s, and then 99s which were 5s at one point. Right. Pretty cool. This is pretty awesome. So, using the sorting algorithm made available through the STL, we can easily sort elements in our vector. Nice work everyone. In the next lecture, we'll move on to another topic. Smart pointers. I'll see you there