Lecture 15: Standard Template Library (STL)

Introduction to the Standard Template Library (STL)

One of the newest areas in the development of C++ is the Standard Template Library (STL). It is so new that some compilers do not yet have this feature available at all or they have not fully implemented it. The STL was originally developed by Alexander Stepanov and Meng Lee of Hewlett Packard. The STL is expected to be the major tool of C++ in the future and all C++ programmers in the future will need to know how to implement it. These notes will only introduce this topic.

 Note:  The discussion in this lecture is based upon C++ in Visual Studio .NET 2005. Previously the examples were written in C++ from Visual Studio .NET 2003. Several of them did not work when they were moved to .NET 2005. The theory and examples of this lecture therefore had to be modified to meet these changes. If you try these examples using other compilers, you may also run into similar problems because not every compiler vendor implements these concepts exactly the same. One of the reasons for some of the modifications was to reduced security problems.

Central to the STL is what is incorporated in its name. That is the keyword: template. To work with the STL requires the use of template classes, general template functions, and objects of template classes. In order to do this requires the inclusion of new header files. At first reading, a discussion of this topic is frequently more difficult to understand than using the concepts because the ideas and the tools are not fully developed in some compilers and in some textbooks discussing the concepts.

The STL is based on three entities: containers, algorithms and iterators. Containers are template classes that are used to store data to include the storage of objects of programmer defined classes as well as system data types. In addition to the template member functions of the container classes there are also non-member template functions that can be used to manipulate the objects of the container classes. These template functions are called algorithms. The third entity mentioned above is the iterators that are objects which act like pointers. Using iterators, the programmer can manipulate the elements of a container as a pointer can be used to manipulate the elements of an array.

There are several different types of containers in STL that are organized into three different categories: sequence containers, associative containers and adaptor containers.

A good visualization of a sequence container is an array. The elements in a sequence container are arranged so that they are in an order with a relationship of an element which proceeds and one which follows it. Examples of sequence containers are: vectors, lists and deque (a double ended queue).

An associative container is not sequential but uses keys to access data instead. Examples of associative containers are: the map, the multimap, the set and the multiset. The map and the multimap have pairs of data one of which is a key and the other is some object. In the map the key is unique while in the multimap the key is not unique. The set and the multiset contain keys only. In the set the keys are unique and in the multiset there can be duplicate keys. This type of container will not be considered in these notes.

The adaptor containers include: priority_queue, queue and stack. The adaptor containers are similar to the ADTs of the same names that were created previously in the lecture notes.

Associated with each of the containers is a header. The containers and their corresponding headers are listed in the following table:

Open table as spreadsheet

Container	Required Header
deque	<deque>
list	<list>
map	<map>
multimap	<map>
multiset	<set>
priority_queue	<priority_queue>
queue	<queue>
set	<set>
stack	<stack>
vector	<vector>

Creating an instance of a container is similar to creating an instance of a template class. For example:

 vector<int> intVector 

creates the integer vector whose name is intVector and

 list<Invoice> sales 

creates the list of objects whose data type is Invoice and the list has the name sales.

In addition to the headers required by the respective containers other headers may be required. For example in some compilers you may also need to use the headers: <iterator>, <utility> and <functional>. You should check your compiler's manual to determine how these headers have been implemented. The header <iterator> contains general iterators some of which can be used to I/O the elements of a container. The header <functional> contains a group of functions that may be used on certain containers. These headers will not be discussed further in these notes.

Since each of the containers is itself a template class, there is associated with each class a collection of member functions. While the member functions of each class are different, there is a collection of member functions that are common to all of these classes. They are the following:

Open table as spreadsheet

Member Function	Purpose
size()	returns the number of elements in the container
empty()	returns true if container is empty
max_size()	returns size of the largest possible container
begin()	returns an iterator to the start of the container for iterating forward through the container
end()	returns an iterator to the past-the-end location in the container use to end forward iteration
rbegin()	returns a reverse iterator to the end of the container for iterating backward through the container
rend()	returns a reverse iterator to the beginning of the container used to end backward iteration

Algorithms are template functions but they are not member functions. They are included in the header: <algorithm>. These functions may be used to manipulate the data in the containers. Some of the algorithms are in the following table:

Open table as spreadsheet

Algorithm	Purpose
find(theElement)	returns the first element equivalent to a particular value
count(theElement)	counts the number of elements that have a particular value
equal(theContainer)	compare the contents of two containers and returns true if all corresponding elements are equal
search(theElement)	seeks a sequence of values in a container that corresponds to the same sequence in another container
copy(theContainer)	copies a sequence of values from one container to another
swap( )	interchanges a value in one location with a value in another location
fill( )	places a value into a sequence of locations
sort( )	sorts according to a particular ordering
merge( )	combines two sorted ranges of elements to make a larger sorted range of elements
	Note:  In Visual Studio .NET 2005 a warning is created because the algorithm merge() has been deprecated for security reasons.

The algorithms may be used on arrays as well as on containers. For example see stl1.cpp which uses the sort() algorithm to sort the elements of an array or see stl2.cpp which uses the algorithm merge() to merge two sorted arrays to obtain a sorted merged array with the elements in numeric order. As can be seen in these two examples, using these algorithms can make programming much easier. Try these on your compilers to see how they are different. Notice the use of the header <algorithm>.

Some of these topics will be discussed later in this lecture. A complete study of STL, its containers and their individual properties as well as the algorithms and iterators are beyond the objectives of these lectures. Therefore this lecture will provide a simple example of a vector container and a list container as well as some of their member functions. More will be discussed about these two containers later in this lecture. For example see stl3.cpp which considers vectors and see stl4.cpp which considers lists. Notice the use of the headers: <vector> and <list> in these two examples.