.Open The C++ Standard Template Library
This is a short primer on the $STL or "Standard Template Library"
for the programming language C++ as defined in the 1997 standard.

The $STL is a collection C++ libraries that allow you to use
several well known kinds of data structures with out having to program
them.  They are designed so that the code runs efficiently.  The compiler
does most of the work of generating the efficient implementations.
The libraries include a large number of possibilities.

I describe some of things you can do with
the STL versions of stacks, queues, vectors, and lists.  I
define some important and useful ideas in the
$Glossary below.  The is a table summarizing the methods
used with stacks, queues, vectors and lists at $Summary below.

For each kind of data structure I give working examples of how to
declare, access and use objects of that type.

.Open Standard Templates
The international and American 
Standard for C++ requires there to be
special libraries that implement the following generic data structures:
.Table Library	Description	More Info
.Row <$vector>	A dynamic array
.See $Vectors
.Row <$list>	A randomly changing sequence of items
.Item $Lists
.Row <$stack>	A sequence of items with $pop and $push at one end only
.Item $Stacks
.Row <$queue>	A Sequence of items with $pop and $push at opposite ends
.Item $Queues
.Row <deque> 	Double Ended Queue with pop and push at both ends
.Item $More
.Row <bitset>	A subset of of a fixed and small set of items
.Item $More
.Row <set>	An unordered collection of items
.Item $More
.Row <map>	An collection of pairs of items indexed by the first one
.Item $More
.Close.Table
These are designed to be general, efficient, and powerful rather than easy
to use.
.Close Standard Templates

.Open Stacks
Stacks are only accessed at their top.
To be able to use $STL stacks in a file of C++ source code 
or a header file add
.As_is 	#include <stack>
at the beginning of the file.

Suppose that `T` is any type or class - say an int, a float, a struct, or
a class, then
.As_is 	stack<T> s;
declares a new and empty stack called `s`.
Given `s` you can:
.Set
 test to see if it is empty:
.As_is 		s.empty()
 find how many items are in it:
.As_is 		s.size()
 push a `t` of type `T` onto the top:
.As_is 		s.push(t)
 pop the top off `s`:
.As_is 			s.pop()
 get the top item of `s`
.As_is 			s.top()
 change the top item:
.As_is 			s.top() = expression.
.Close.Set
. Example of an STL Stack
.As_is 	void reverse(string & x) 
.As_is 	//Afterwards x will have the same elements in the opposite order.
.As_is 	{
.As_is 		stack<char> s;
.As_is 		const int n = x.length();
.As_is    	//Put characters from x onto the stack
.As_is 		   for(int i=0; i<n; ++i)
.As_is 			s.push(x[i]);
.As_is    	//take characters off of stack and put them back into x
.As_is 		   for(int i=0; !s.empty(); ++i, s.pop())
.As_is 			x[i]=s.top();
.As_is 
.As_is 	}
. Older Stacks
On some older C++ libraries you are forced to indicate
how the stack is implemented whenever you declare one.  You
write either
.As_is 		stack< vector<T> > s;
or
.As_is 		stack< list<T> > s;
See $Errors below for some common mistakes and problems
(like omitting a space in the wrong place above).
.As_is 	void reverse(string & x) //INOUT: x is a string of characters
.As_is 	//Afterwards x will have the same elements in the opposite order.
.As_is 	{
.As_is 		stack< vector<char> > s;
.As_is 
.As_is 		const int n = x.length();
.As_is 		for(int i=0; i<n; ++i)
.As_is 			s.push(x[i]);
.As_is 		 for(int i=0; !s.empty(); ++i, s.pop())
.As_is 			x[i]=s.top();
.As_is 	}

.Close Stacks
.Open Queues
Queues allow data to be added at one end and taken out of the other end.
To be able to use $STL queues add this before you start using them
in your source code:
.As_is 	#include <queue>
Suppose that `T` is any type or class - say an int, a float, a struct, or
a class, then
.As_is 	queue<T> q;
declares a new and empty queue called `q`.
Given an object `q`:
.Set
 test to see if `q` is empty:
.As_is 		q.empty()
 find how many items are in `q`:
.As_is 		q.size()
 push a `t`:`T` onto the end of `q`:
.As_is 		q.push(t)
 pop the front of `q` off `q`:
.As_is 		q.pop()
 get the front item of `q`:
.As_is 		q.front()
 change the front item:
.As_is 		q.front() = expression.
 get the back item of `q`:
.As_is 		q.back()
 change the back item:
.As_is 		q.back() = expression.
.Close.Set
.See Errors
below.
.As_is 		// A simple example of putting three items into a queue and
.As_is 		// then taking them off the queue.
.As_is 		#include <iostream.h>
.As_is 		#include <list>
.As_is 		#include <queue>
.As_is 		 
.As_is 		int main()
.As_is 		{
.As_is 			queue<char> q;
.As_is 		 
.As_is 			q.push('a');
.As_is 			q.push('b');
.As_is 			q.push('c');
.As_is 		 
.As_is 			cout << q.front();
.As_is 			q.pop();
.As_is 		 
.As_is 			cout << q.front();
.As_is 			q.pop();
.As_is 		 
.As_is 			cout << q.front();
.As_is 			q.pop();
.As_is 		}
. Older Queues
On some older C++ libraries you are forced to indicate
how the queue is implemented whenever you declare one.  You
write
.As_is 		queue< list<T> > q;
in place of
.As_is 		queue< T > q;
.See Errors
below.
.As_is 		// A simple example of putting three items into a queue and
.As_is 		// then taking them off the queue.
.As_is 		#include <iostream.h>
.As_is 		#include <list>
.As_is 		#include <queue>
.As_is 		 
.As_is 		int main()
.As_is 		{
.As_is 			queue< list <char> >q;
.As_is 		 
.As_is 			q.push('a');
.As_is 			q.push('b');
.As_is 			q.push('c');
.As_is 		 
.As_is 			cout << q.front();
.As_is 			q.pop();
.As_is 		 
.As_is 			cout << q.front();
.As_is 			q.pop();
.As_is 		 
.As_is 			cout << q.front();
.As_is 			q.pop();
.As_is 		}
.Close Queues
.Open Lists
Lists are good when data needs to be reorganized a lot.
To be able to use $STL lists add this before you start using them
in your source code:
.As_is 	#include <list>

Suppose that `T` is any type or class - say an int, a float, a struct, or
a class, then
.As_is 	list<T> l;
declares a new and empty list called `l`.
Given an object `l`:
.Set
 test to see if `l` is empty:
.As_is 		l.empty()
 find how many items are in `l`:
.As_is 		l.size()
 push a `t`:`T` onto the end of `l`:
.As_is 		l.push_back(t)
 pop the last off `l`:
.As_is 		l.pop_back()
 push a `t`:`T` onto the start of `l`:
.As_is 		l.push_front(t)
 pop the front of `l` off `l`:
.As_is 		l.pop_front()
 get the front item of `l`:
.As_is 		l.front()
 change the front item:
.As_is 		l.front() = expression.
 get the back item of `l`:
.As_is 		l.back()
 change the back item:
.As_is 		l.back() = expression.

 Sort the list:
.As_is 		l.sort()
 Clear the list:
.As_is 		l.clear()
 Merge in a sorted list into a sorted list:
.As_is 		l.merge(list_of_sorted_elements)
 Reverse the list:
.As_is 		l.reverse()

 Assign a copy of `q1` to `q`:
.As_is 		q = q1
 Insert and delete items inside a List
.See Lists and Iterators
 Efficiently visit each item in turn, see $Iterators below.
.Close.Set
. Example of List Processing
This uses a utility function 'print' that is implemented below
.See An Example of Iterating Through a List
. Building and Sorting a List
.As_is //Using a list to sort a sequence of 9 numbers.
.As_is #include <iostream.h>
.As_is #include <list>
.As_is // #include <algorithm>
.As_is 
.As_is void print(list<int> a);//utility function print lists of ints
.As_is 
.As_is int main()
.As_is {
.As_is 	list<int> a;
.As_is  //Put 9,8,7,6,5,4,3,2,1 onto the list
.As_is 	for(int i=0; i<9;++i)
.As_is 		a.push_back(9-i);// put new element after all the others
.As_is 
.As_is 	print(a); //here the list contains (9,8,7,6,5,4,3,2,1)
.As_is 	a.sort();//in the <list> library!
.As_is 	print(a); //here the list contains (1,2,3,4,5,6,7,8,9)
.As_is }
.Close Lists
.Open Vectors
Vectors are good when we have an unknown sequence of items to store
but we want to access the by their sequence numbers.
To be able to use $STL vectors add this before you start using them
in your source code:
.As_is 	#include <vector>
.See Errors

Suppose that `T` is any type or class - say an int, a float, a struct, or
a class, then
.As_is 	vector<T> v;
declares a new and empty $vector called `v`.
Given object  `v` declare like the above:
.Set
 test to see if `v` is empty:
.As_is 		v.empty()
 find how many items are in `v`:
.As_is 		v.size()
 push a `t`:`T` onto the end of `v`:
.As_is 		v.push_back(t)
 pop the front of `v` off `v`:
.As_is 		v.pop_back()
 get the front item of `v`:
.As_is 		v.front()
 change the front item:
.As_is 		v.front() = expression.
 get the back item of v:
.As_is 		v.back()
 change the back item:
.As_is 		v.back() = expression.

 Access the `i`'th item (0<=`i`<size()) without checking to see if it exists:
.As_is 		v[i] 
 Access the `i`'th item safely:
.As_is 		v.at(i)

 Assign a copy of `v1` to `v`:
.As_is 		v = v1
 Sorting and operating on all items efficiently, see $Iterators below.
.Close.Set
.Close Vectors

.Open Iterators and Containers
. Containers
A Container is a data structure that holds a number of
object of the same type or class.  The oldest example
of a Container in C++ is an array.  Even in C you
had arrays and you would
typically write code like this:
.As_is 	const int MAX = 10;
.As_is 	float a[MAX];
.As_is 	...
.As_is 	for(int i=0; i<10; ++i)
.As_is 		process(a[i]);
.As_is 	...
$Lists, $Vectors, $Stacks, $Queues, etc are all $Containers.

C arrays were designed so that they could be accessed by
using a variable that stores the address of an item.  These
variables are called `pointer`s.  They are used like this with an array:
.As_is 	for(float *p=a; p!=p+MAX; ++p)
.As_is 		process(*p);
.As_is 	...
. Iterators
Items in $Containers are referred to be special objects called:
`iterator`s.  They are generalization of C's pointers.
With an iterator class `Iter` you can process each item in
a vector or a list by similar code:
.As_is 	for( Iter p=c.begin(); p!=c.end(); ++p)
.As_is 		process(*p);

All $Containers C in the STL have a number of iterator objects.  Container
class C has an iterator called 
.As_is 		C::iterator
For any type `T`, list<`T`> and vector<`T`> are $Containers.
So there are iterator classes called
.As_is 		list<T>::iterator
and they are used like this:
.As_is 	for( list<T>::iterator p=c.begin(); p!=c.end(); ++p)
.As_is 		process(*p);

Vector iterators have type
.As_is 		vector<T>::iterator
and used like this:
.As_is 	for( vector<T>::iterator p=c.begin(); p!=c.end(); ++p)
.As_is 		process(*p);

If you change your choice from a $vector to a $list then
the code is almost identical.  This makes your code easier to
modify.

For any $container class `C` of objects type `T` and any object `c` of type `C`:
.Set
 Declare an iterator for $container of type C.
.As_is 		C::iterator p
 Move iterator `p` onto the next object in `c`(if any!).
.As_is 		++p
 The value selected by `p`.
.As_is 		*p

 The iterator that refers to the first item in `c`
.As_is 		c.begin()
 The iterator that refers to one beyond `c`.
.As_is 		c.end()

 Declare an iterator for $container of type `C` and set to the start of `c`.
.As_is 		C::iterator p = c.begin();
 Test to see if iterator p has come to the end of object `c`:
.As_is 		p != c.end();

 assign `p1` to `p` -- afterwards both refer to same item
.As_is 		p = p1;
.Close.Set

. Lists and Iterators
Insertion and deletion of items at the start or inside a List of elements is controlled by an iterator:
.Set
 Insert item `x` into List `l` before iterator `p`
.As_is 			l.insert(p, x);
 Erase the element pointed at by iterator `q` in List `l`
.As_is 			l.erase(q);
.Close.Set
.As_is 	#include <iostream.h>
.As_is 	#include <list>
.As_is 	void print(list <char> );// elsewhere
.As_is 	main()
.As_is 	{	list <char> l;
.As_is 		list <char>::iterator p; 
.As_is 		l.push_back('o'); l.push_back('a'); l.push_back('t');
.As_is 	
.As_is 		p=l.begin();
.As_is 		cout <<" "<< *p<<endl;  // p refers to the 'o' in ('o', 'a', 't')
.As_is 		print(l);
.As_is 	
.As_is 		l.insert(p, 'c');
.As_is 	
.As_is 		// l is now ('c', 'o', 'a', 't') and p still refers to 'o'
.As_is 		cout <<" "<< *p<<endl;
.As_is 		print(l);
.As_is 	
.As_is 		l.erase(p);
.As_is 	
.As_is 		cout <<" "<< *p<<endl; // p refers to an 'o' but it is not in l!
.As_is 		print(l);
.As_is 	
.As_is 		l.erase(l.begin()); //removes front of l
.As_is 		print(l);
.As_is 	}
. Ranges
A pair of iterators describes a $range of items in their $container.
The items in the $range start with the first iterator in the pair.
The $range has all the following items up to just before
the item referred to by the last iterator of the pair.

Suppose that `first` and `last` form a $range and `it` is an iterator
then:
.As_is 		for( it=first; it != last; it++)
will refer to each element in the $range [`first.`.`last`) in turn.  In
the body of the for loop
the value of the element is `*it`.

Given a $container `c`, then
`c.begin()` and `c.end()` form a $range.
. An Example of Iterating Through a List
.As_is 
.As_is void print( list<int> a)
.As_is {
.As_is 	for(list<int>::iterator ai=a.begin(); ai!=a.end(); ++ai)
.As_is 		cout << *ai << " ";
.As_is 
.As_is 	cout << endl;
.As_is 	cout << "----------------"<<endl;
.As_is }

. Algorithms
Ranges and Iterators are used several useful functions and algorithms
in the $STL.
Suppose you have a type or class of data called `T` and in a
program are working with a vector `v` of type `vector<T>` then
.As_is 		vector<T>::iterator
is the class of suitable iterators.  Here are two useful
values:
.As_is		v.begin()
.As_is 		v.end()
These always form a $range of all the items in `v` from
the $front up to and including the $back.
You can sort a $vector v simply by writing:
.As_is		sort(c.begin(), c.end());
.As_is //Sorting a vector with 9 integers
.As_is #include <iostream.h>
.As_is #include <vector>
.As_is #include <algorithm>
.As_is 
.As_is void print( vector<int> ) ;//utility function outputs a $container
.As_is 
.As_is int main()
.As_is {
.As_is 	vector<int> a;
.As_is  // Place 9,8,7,6,5,4,3,2,1 into the vector 
.As_is 	for(int i=0; i<9;++i)
.As_is 		a.push_back(9-i);// put new element after all the others
.As_is 
.As_is 	print(a); // elements of a are (9,8,7,6,5,4,3,2,1)
.As_is 
.As_is 	sort( a.begin(), a.end() ); //in the STL <algorithm> library
.As_is 
.As_is 	print(a); // elements are nor in order.
.As_is }
.As_is 
.As_is 
.As_is void print( vector<int> a)
.As_is {
.As_is 	for(vector<int>::iterator ai=a.begin(); ai!=a.end(); ++ai)
.As_is 		cout << *ai << " ";
.As_is 
.As_is 	cout << endl;
.As_is 	cout << "----------------"<<endl;
.As_is }

.Close Iterators
. More -- See Also
These notes only scratch the surface of the $STL.  It does not mention:
.Set
 Deques (Double Ended Queues)
 Containers that are not sequential but $associative.
 Reversed iterators
 More algorithms
 Iterators for input and output data streams
 Higher order functions that do things to all items in ranges
 	Etc.
.Close.Set
For a complete description you need either a copy of the standard or
a good book.   A computer Science Data Structures (CS2) class
like CSUSB's CS330 will teach you how these data structures are 
implemented.  The are many useful resources on the world wide web,
see
.See http://www/dick/samples/c++.html#STL

Also see
.Set
My CS202 notes
.See http://csci.csusb.edu/dick/cs202/stl.html
.See http://csci.csusb.edu/dick/cs202/stl.review.html
.See http://csci.csusb.edu/dick/cs202/12.html

My notes on the <algorithm> library
.See http://csci.csusb.edu/dick/samples/stl.algorithms.html

My CSCI330 reference docs (Download!)
.See http://www.csci.csusb.edu/dick/cs330/Ref/

The CGI Ref Manual
.See http://www.sgi.com/tech/stl/

My copy of the C++ LRM Chapters 22..24
.See http://www.csci.csusb.edu/dick/c++std/cd2/index.html

.Close.Set
.Set Books:
Our CSCI330 text book (-- the example code has many misprints but there must
be cheap used copies in the bookstore or the used book store near El Polo
Loco)
 Timothy Budd, Data Structures in C++ using the Standard Template Library,
Addison-Wesley

 Bjarne Stroustroup's C++ LRM is definitive, complete, and fairly clear, but
expensive.
In CSUSB library.

In CSUSB Library I found
 Scott Meyers
Effective STL: 50 specific ways to improve your use of the standard Template
Library
Addison Wesley 2001 ISBN 0-201-74962-9
CSUSB: QA76.73.C153.M49

The following includes some stuff on the STL
 Herb Sutter
Exceptional C++: 47 engineering puzzles, programming problems, & solutions
Addison Wesley Longman 2000 ISBN 0-201-61562-2
CSUSB: QA76.73.C153.S88
.Close.Set
. Summary
.Table
.Row Template	Common	push/pop	items	Extras
.Row stack	empty(), size()	pop(),push(T)	top()	-
.Row queue	empty(), size()	pop(),push(T)	front(),back()	-
.Row vector	empty(), size()	push_back(T), pop_back()	front(), back()	[int], at(int), =
.Row list	empty(), size()	push_back(), pop_back(), push_front(T), pop_front()	front(), back()	sort(), clear(), reverse(), merge(l),at(int), =

.Close.Table
. Glossary
associative::=A type of $container that associates a key with a data item when the data is stored and uses the key to retrieve the item.

back::=a special item in a $sequential $container that has no items after it.

container::=A data structure which contains a number of data items that can gain and lose items as the program runs.  Examples include vectors, lists, stacks, ...

contiguous::=a way of implementing data structures so that a continuous block of storage is used and items are found by calculating the address. See $Vectors.

front::=a special item in a $sequential $container that has no other items before it.

generic::code= a function or class that is a template and can be used for data of many different types depending on its parameters.

increment::$operation=moving an iterator/pointer/index on to the next iterator/pointer/index value commonly symbolized by ++ in C-like languages.

iterator::=An object that refers to an item in a $container and used commonly used in for_loops and $generic code.
Iterators for $sequential containers have two special values: begin and end.
The `begin` value refers to the $front item.  The `end` value is a not
the $back but referee to a nonexistent item after the $back of the container.
See $NULL.

linked::=a way of implementing data structures where storage is allocated and deleted as it is needed item by item and the items are linked together by a $pointer.  For example see $Lists.

list::$container=a $sequential container that is optimized to all items to be inserted and erased at any point in the container.
.See Lists

NULL::=the C and C++ standard constant used to indicate that a $pointer does not contain an address.  In tests this value is converted to the boolean false. It is often used as a sentinel indicating the end of a $linked data structure.

operation::=something that can be applied to an object to extract information from it or to change its state.

pop::$operation=to add a new item to one or other end of a $sequential $container.
push::$operation=to remove an item from one or other end of a $sequential $container.

pointer::=a piece of storage that contains either a $NULL value or a single address of another piece of storage.

queue::$container=a $sequential container where $pop adds data at the $back and $push removes data from the $front. See $Queues.
A queue is used in simulations and operating systems when items have to be
stored and their order preserved.

random_access::=being able to do things to items in a container in any unpredictable order typically by using an integer as an index or subscript.

range::=a pair of iterators pointing to items in the same $sequential $container such that a number of steps would move the first iterator to the next one.

sequential::=A type of $container that stores data in a particular order and uses this sequence to access them.
Sequential containers have a $front and $back element and a $size.  You can
$push and $pop items into or from a sequential container.

stack::$container=a $sequential container where $pop and $push both act at the $front (called the $top) and where only the $top item is accessible at any time.
A Stack is useful when something has to be stored while de do something else
that might involve saving some more data and so on.  The data is retrieved
in the reverse order to which it is inserted.
See $Stacks.

STL::=The Standard Template Library.  
.See Standard Templates

TBA::=To Be Announced -- I'm working on this piece of text.

vector::$container=a vector is a sequential container that is optimized to allow efficient $random_access of items by using an index.
Vectors are are allocated in a contiguous block of space.
Vectors are useful whenever data must be stored in
one order accessed in a different one.  A vector is
a dynamic array - an array that can grow when needed.
.See Vectors
. Errors
You must always #include headers if you use the words:
vector, list,string,queue, or stack in your program or
in a header file.

Their must be a space between the two ">" signs below:
.As_is 		stack< vector< T > > s;

If the standard <list> and <vector> is not found then you are using an older C++
compiler.  You may still be able to a slightly different form of stack
and queue however:
.See Older Stacks
.See Older Queues

On some older compilers and currant libraries
when you need a <string> as well as either <list> or <vector>
you need to
.As_is 		#include <string>
before including the list or vector rather in the
reverse order!  Older string library appear to
define some special versions of vector and list operators
and the older compilers can not make up its mind which to use.

. Acknowledgements
Dr. Botting wants to acknowledge the help and advice given by Dr. Zemoudeh
about this document.  Whatever errors remain are Dr. Botting's mistakes.
.Close The C++ Standard Template Library