The Standard Template Library (STL) is a part of C++ (Since 1999) that allows you to more rapidly develop software. I claim that they improve my productivity by at least 40% over not using it. As a C++ programmer, you will be looked on as out of date or incompetent if you don't use STL.
Once you learn how to use it, it will be rare that you will every have to write code to implement a data structure. In data structures you will learn about binary trees to support quick lookups for rapidly changing structures. There is a tool to work with these in STL. So, why write a code to do a tree structure? Question: why do we learn about data structures if model of it is provided for us by STL?
This document is an introduction to STL. This documentation is neither comprehensive nor complete. A full presentation of STL would take at least half a semester. We will do more later. The material discussed here is presented in Chapter 22 (page 1057) of the text. The goal of this document is to get you to the point where you can start using STL and are more able to read references.
The purpose of STL is to expedite the writing of software. It provides you with most of the data structures you have or will learn about in the Data Structures course and tools to manipulate them. The data structures are constructed so that they can handle any type of data elements. This is accomplished through the use of class and function templates. Using STL seems strange and difficult until you become accustom to it. Then it is very easy to use. (I will mention my own experience in class.) It will also greatly reduce your need to use new and delete since it worries about this for you.
There are three components that make up STL. These are containers, algorithms, and iterators. Each will be discussed below.
Containers. Containers embody the data structures supported by STL. It accomplishes this by defining a template class for each of these data structures There are functions in the classes that allow the efficient manipulation of its elements. The following is a list of the containers.
vector - allows us to define dynamic arrays.
deque - doubly ended queues.
queue - supports a queue. Officially not a container - it is an adapter (Don't worry about the difference), but we can think of it as a container.
list - allows us to create linked lists.
stack - implements a pushdown stack.
maps and multimaps - allows us to create sorted tree structures. This gives us quick access to data stored in table form. The data may be accessed using a key.
set and multi-set - allows us to organize a set of data in a tree structure.
Missing is hash tables. But, even though they are not officially part of C++, many compilers have a hash container. Visual Studio .NET and most C++ compilers also have hash_map, hash_multimap, hash_set, and hash_multiset classes.
Note: Most often used containers are vectors, maps, sets, hash maps and hash_sets. These are the containers that I will introduce first.
Containers are implemented using template
classes. This allows the containers to hold a lot of different types of
data.
Algorithms. There are a set of algorithms
supplied to manipulate data in containers. Sort, lower bound (a binary search)
and replace are examples of algorithms. A good rule: if the container contains
a function that does the same thing as a function in the algorithms, use the
function in the container class.
Note: In order for algorithms to be applied to a variety of data type, they are
template functions.
Iterators. Iterators are a fancy word for
pointers. They are pointers relative to containers. Because of the structure
of the various containers they are not always as powerful as the standard C++
pointers. I will show in class that the iterator to a map cannot be as
general as a standard pointer.
There are forward iterators (the standard ones) and reverse iterators. That
is, they give you the ability to step forward and backwards through a
container. Some of you wonder why this is important. But, consider a map and
iterating through it.
In order to get started with STL, I will give you two examples. One will illustrate the use of vectors and the second the use of maps. We will look at these examples in Visual Studio.
Vectors are "super" arrays. They look a lot like arrays with the exception that no size is associated with them. We will discuss in class how they are implemented.
Keep in mind that we are dealing with a template class. Since it is a class, we can have and do have all kinds of extra functionality associated with vectors. We will play with these in our example. The following is a list of the functionality that I consider important.
Create a vector of data type int by writing vector<int> x;
push_back - adds an entry to the end of the vector. The vector is resized if we run out of space.
size - returns the size of a vector.
capacity - the number of elements that may be recorded in a vector before we need more storage. It is an interesting challenge to see the algorithm used by MS to increase the size of a vector.
resize - changes the size of a vector.
back - returns the last element in a vector.
erase - deletes a range of elements from a vector.
pop_back - deletes the last element in a vector.
reserve - sets aside space for a vector.
insert - records an element at a particular position in the vector.
clear - erases all the elements in a vector.
empty - returns true if the vector is empty.
Note: There has been every attempt to be consistent in STL. So, many of the member functions discussed here are also available in other containers.
An iterator is like a pointer. A vector has an iterator data and has functions to get the address of the first element (begin) and one plus the last element. (end) We will see these in the example.
Example 1 - vectors
Notes on example:
Check out how IntelliSense will tell you about classes like vector.
The capacity member function indicates how much space is allocated for the vector.
The size member function indicates the actual number of elements in the vector.
The push_back member function allows you to push data onto the vector. The pop_back member function allows you to delete from the vector.
Assignment works with vectors.
There is a resize member function to change the size of a vector.
There is an erase member function to delete elements from the vector. To use must have iterators to the position or positions to be erased.
Note the pragma to disable a warning. Why would you want to do this? The warning I disabled was from version 6. They used to give warnings about variables in templates being too big. I leave it in to remind us that the pragma directive can be used to do more than just preventing the compiler from including the same file twice.
You will note a similarity to strings.
Tell me how you would deduce the way that vectors grow. Let try it.
Let's look up the sort algorithm and sort the array.
Let's see if the replace and sort works on arrays.
Let's look up sort under help. I want you to note that compare function that it allows as a third argument. Let's add one. I will talk it through as if this was my first time using it.
Allows us to specify a binary tree of <key, data> elements. To define a tree with key of string and data of int, type map<string, int> y.
Although maps represent a very different data structure from vectors, there is a lot of similar functionality. We will see this as we go over the example. But, first I have a list of interesting member functions. Recall that this allows you to relate a key to associated data.
clear - to erase all the elements of the map.
empty - returns true if map is empty.
size - returns the number of elements in the map.
find - returns an iterator to the element searched for.
begin, end - same as vectors.
rbegin, rend - used with reverse_iterator to step backwards through a tree.
[] - allows you to access a data element of a map by its key.
erase - deletes a particular element or range of elements. You can specify a key or a range of iterators.
Example 2 - maps
Notes on example 2
A map is the implementation of an ordered binary tree. It is kept balanced for search efficiency.
Elements of a map are from a pairs class. You can access them by the member variables first and second. So, if you use iterator im, to get the first element by im->first and the second by im->second.
Data is organized as a binary tree whose elements are ordered by the first element of each pair.
You can use the empty member function to determine if a map is empty. The size function indicates the number of elements in the map.
The find member function will return an iterator to the element you want to find. The iterator to the end of the map is returned if the element is not found.
hash_map which is available in Visual Studio works the same way as map, with the exception that the data is organized into a hash table and displaying it will not give you an ordered list. In class we will convert the map example to a hash_map example. Note: hash_map is not in the std namespace. It is in the stdext namespace. That is the problem I had when I first demonstrated this in class.
If there is time, we will talk a little more about STL later.
If the user enters one word per line, write a program to display the number of times each word is entered. Use a map to solve this problem.