Let's turn to the Standard Template Library. That's the main topic of today's discussion. The Standard Template Library, the analogy I like to use, is built like a three-legged stool. It's got three legs to it. Those three legs are containers, and the containers are of two kinds, ones that involve sequences. So you can say that there is, an nth element. The other kind, which are associative, so you can't think of them as having an element. But you can think of them as having something, a relation between what you use to look them up, like a name and a value. You have some kind of relation, a built in relation. Those are two major classes of containers. And then we have five kinds of iterators. These are pointers or cursors. Conceptually, they're these pointers, or addresses. They're a way of navigation, they're our navigation tool. And then finally, what do we produce? How are these things to be used and we have many many useful, algorithms, and that's our three legs of the stool and we can because it's a compartmentalized library we tend to have things like numeric algorithms, sorting related algorithms such as sort and merge. And we have things that don't mutate the sequences and things that mutate the sequences. Non mutating means the algorithm when applied to something doesn't change that. As opposed to a mutating algorithm which when applied to something like a vector would change it. Such as this idea of a random shuffle or copy. Okay, so here are some things that are new. I will talk about them over the next set of sessions. Some are very complex, and we won't be able to, in this kind of basic course, to fully explore much of this. But by giving you a road map and if you have a need for it, the libraries are way to big to go into in detail and they have quite an extensive amount of documentation. So, it's really what you need is how to understand it and then how to look at up to make use of it. So, here are some of the things that have been placed into the standard now, based on existing practice, regular expressions. Other have been regular expressions packages in Unix and languages for quite a while, Perl for example is a language that has a lot of regular expression built into its use and now through this standard library, redex gets you to examine typically strings and see if they conform to a particular syntax. Threading. So, were in the edge of multi cores, and multi processors. And we want to be able to parallelize our programming to be more effective and we now have a basic thread library. Now that's not the only library that gets involves in concurrency. The other libraries but I wont be able to get into them in detail, like for example, libraries that allow for atomic operations. Are available as well. In the standard. We have unordered maps and unordered sets added to STL so the ordinary map in STL was based on red black tree and a red black tree has basic operations that frequently require log n operations to work with. A very good hash let's you do very similar things, associated arrays, maps. But do's them in constant time, order one time. So it can be far more efficient, then people started using hash space libraries quite a bit ago, but now they've been standardized. Recall that the 90% rule that I've talked about frequently, The one class you should really go, the one standard template class that you should really get used to using is vector, it buys you all sorts of value. But in some situations, that can be specialized to what is now called an array. A vector can grow in size. This is fixed. There's a lot of commonality between array and vector, very similar. But array, has as a part of its definition a size. Again the original list in STL was doubly link list so you could go previous or next, but that required some extra space. And so what was added was a pure singly linked list, a forward list, and a ton more exist in STL but these are some of the things, we will see in examples and I will describe further. Okay, let's take another brief quiz. Think about your C experience. All of you are experienced C programmers that's why you're in this course. What would be a container in C? What would be an iterator in C? What would be an algorithm, a standard algorithm in C? Can you name those? And here's a little more advanced question. How can you do generic coding in C, or can you? Okay, everybody out there should have gotten, the fact these are standard arrays in C. And arrays in C are really pointers, and a way to manipulate or search through such things is to have pointer declarations. So pointers are cursors. Lets see. And there are a host of standard C algorithms, we've already used, we use them even in the C++ community, so mathematically you can get the C library and find square root. Or you can have pseudorandom number generator, produce random number integers using calling rand. And then this is a more advanced question, there's a special pointer type for each star that allows you to point at anything. And if you're careful and really know to do advance C code. You can use that to produce things like a generic mem copy. So, there is in a standard library and mem copy where you copy one set of things from memory to another set and that all can be done through void star and could be done basically as a generic copy.
