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.

Standard Templates

The international and American Standard for C++ requires there to be special libraries that implement the following generic data structures:

Library	Description	More Info
<vector>	A dynamic array [ $Vectors ]
<list>	A randomly changing sequence of items	Lists
<stack>	A sequence of items with pop and push at one end only	Stacks
<queue>	A Sequence of items with pop and push at opposite ends	Queues
<deque>	Double Ended Queue with pop and push at both ends	More
<bitset>	A subset of of a fixed and small set of items	More
<set>	An unordered collection of items	More
<map>	An collection of pairs of items indexed by the first one	More

These are designed to be general, efficient, and powerful rather than easy to use.

. . . . . . . . . ( end of section Standard Templates) <<Contents | End>>

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

 	#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

 	stack<T> s;

declares a new and empty stack called s. Given s you can:
• test to see if it is empty:

   		s.empty()

• find how many items are in it:

   		s.size()

  
  push a t of type T onto the top:

   		s.push(t)

  
  pop the top off s:

   			s.pop()

  
  get the top item of s

   			s.top()

• change the top item:

   			s.top() = expression.

Example of an STL Stack

 	void reverse(string & x)

 	//Afterwards x will have the same elements in the opposite order.

 	{

 		stack<char> s;

 		const int n = x.length();

    	//Put characters from x onto the stack

 		   for(int i=0; i<n; ++i)

 			s.push(x[i]);

    	//take characters off of stack and put them back into x

 		   for(int i=0; !s.empty(); ++i, s.pop())

 			x[i]=s.top();

 	}

Older Stacks

On some older C++ libraries you are forced to indicate how the stack is implemented whenever you declare one. You write either

 		stack< vector<T> > s;

or

 		stack< list<T> > s;

See Errors below for some common mistakes and problems (like omitting a space in the wrong place above).

 	void reverse(string & x) //INOUT: x is a string of characters

 	//Afterwards x will have the same elements in the opposite order.

 	{

 		stack< vector<char> > s;

 		const int n = x.length();

 		for(int i=0; i<n; ++i)

 			s.push(x[i]);

 		 for(int i=0; !s.empty(); ++i, s.pop())

 			x[i]=s.top();

 	}

. . . . . . . . . ( end of section Stacks) <<Contents | End>>

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:

 	#include <queue>

Suppose that T is any type or class - say an int, a float, a struct, or a class, then

 	queue<T> q;

declares a new and empty queue called q. Given an object q:

test to see if q is empty:

 		q.empty()


find how many items are in q:

 		q.size()


push a t:T onto the end of q:

 		q.push(t)


pop the front of q off q:

 		q.pop()


get the front item of q:

 		q.front()

• change the front item:

   		q.front() = expression.

  
  get the back item of q:

   		q.back()

• change the back item:

   		q.back() = expression.

[ Errors ] below.

 		// A simple example of putting three items into a queue and

 		// then taking them off the queue.

 		#include <iostream.h>

 		#include <list>

 		#include <queue>

 		int main()

 		{

 			queue<char> q;

 			q.push('a');

 			q.push('b');

 			q.push('c');

 			cout << q.front();

 			q.pop();

 			cout << q.front();

 			q.pop();

 			cout << q.front();

 			q.pop();

 		}

Older Queues

On some older C++ libraries you are forced to indicate how the queue is implemented whenever you declare one. You write

 		queue< list<T> > q;

in place of

 		queue< T > q;

[ Errors ] below.

 		// A simple example of putting three items into a queue and

 		// then taking them off the queue.

 		#include <iostream.h>

 		#include <list>

 		#include <queue>

 		int main()

 		{

 			queue< list <char> >q;

 			q.push('a');

 			q.push('b');

 			q.push('c');

 			cout << q.front();

 			q.pop();

 			cout << q.front();

 			q.pop();

 			cout << q.front();

 			q.pop();

 		}

. . . . . . . . . ( end of section Queues) <<Contents | End>>

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:

 	#include <list>

Suppose that T is any type or class - say an int, a float, a struct, or a class, then

 	list<T> l;

declares a new and empty list called l. Given an object l:

test to see if l is empty:

 		l.empty()


find how many items are in l:

 		l.size()


push a t:T onto the end of l:

 		l.push_back(t)


pop the last off l:

 		l.pop_back()


push a t:T onto the start of l:

 		l.push_front(t)


pop the front of l off l:

 		l.pop_front()


get the front item of l:

 		l.front()

• change the front item:

   		l.front() = expression.

  
  get the back item of l:

   		l.back()

• change the back item:

   		l.back() = expression.

• Sort the list:

   		l.sort()

• Clear the list:

   		l.clear()

• Merge in a sorted list into a sorted list:

   		l.merge(list_of_sorted_elements)

• Reverse the list:

   		l.reverse()

  
  Assign a copy of q1 to q:

   		q = q1

• Insert and delete items inside a List [ Lists and Iterators ]
• Efficiently visit each item in turn, see Iterators below.

Example of List Processing

This uses a utility function 'print' that is implemented below [ An Example of Iterating Through a List ]

Building and Sorting a List

 //Using a list to sort a sequence of 9 numbers.

 #include <iostream.h>

 #include <list>

 // #include <algorithm>

 void print(list<int> a);//utility function print lists of ints

 int main()

 {

 	list<int> a;

  //Put 9,8,7,6,5,4,3,2,1 onto the list

 	for(int i=0; i<9;++i)

 		a.push_back(9-i);// put new element after all the others

 	print(a); //here the list contains (9,8,7,6,5,4,3,2,1)

 	a.sort();//in the <list> library!

 	print(a); //here the list contains (1,2,3,4,5,6,7,8,9)

 }

. . . . . . . . . ( end of section Lists) <<Contents | End>>

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:

 	#include <vector>

[ Errors ]

Suppose that T is any type or class - say an int, a float, a struct, or a class, then

 	vector<T> v;

declares a new and empty vector called v. Given object v declare like the above:

test to see if v is empty:

 		v.empty()


find how many items are in v:

 		v.size()


push a t:T onto the end of v:

 		v.push_back(t)


pop the front of v off v:

 		v.pop_back()


get the front item of v:

 		v.front()

• change the front item:

   		v.front() = expression.

• get the back item of v:

   		v.back()

• change the back item:

   		v.back() = expression.

  
  Access the i'th item (0<=i<size()) without checking to see if it exists:

   		v[i]

  
  Access the i'th item safely:

   		v.at(i)

  
  Assign a copy of v1 to v:

   		v = v1

• Sorting and operating on all items efficiently, see Iterators below.

. . . . . . . . . ( end of section Vectors) <<Contents | End>>

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:

 	const int MAX = 10;

 	float a[MAX];

 	...

 	for(int i=0; i<10; ++i)

 		process(a[i]);

 	...

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 pointers. They are used like this with an array:

 	for(float *p=a; p!=p+MAX; ++p)

 		process(*p);

 	...

Iterators

Items in Containers are referred to be special objects called: iterators. 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:

 	for( Iter p=c.begin(); p!=c.end(); ++p)

 		process(*p);

All Containers C in the STL have a number of iterator objects. Container class C has an iterator called

 		C::iterator

For any type T, list<T> and vector<T> are Containers. So there are iterator classes called

 		list<T>::iterator

and they are used like this:

 	for( list<T>::iterator p=c.begin(); p!=c.end(); ++p)

 		process(*p);

Vector iterators have type

 		vector<T>::iterator

and used like this:

 	for( vector<T>::iterator p=c.begin(); p!=c.end(); ++p)

 		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:

• Declare an iterator for container of type C.

   		C::iterator p

  
  Move iterator p onto the next object in c(if any!).

   		++p

  
  The value selected by p.

   		*p

  
  The iterator that refers to the first item in c

   		c.begin()

  
  The iterator that refers to one beyond c.

   		c.end()

  
  Declare an iterator for container of type C and set to the start of c.

   		C::iterator p = c.begin();

  
  Test to see if iterator p has come to the end of object c:

   		p != c.end();

  
  assign p1 to p -- afterwards both refer to same item

   		p = p1;

Lists and Iterators

Insertion and deletion of items at the start or inside a List of elements is controlled by an iterator:

Insert item x into List l before iterator p

 			l.insert(p, x);


Erase the element pointed at by iterator q in List l

 			l.erase(q);

 	#include <iostream.h>

 	#include <list>

 	void print(list <char> );// elsewhere

 	main()

 	{	list <char> l;

 		list <char>::iterator p;

 		l.push_back('o'); l.push_back('a'); l.push_back('t');

 		p=l.begin();

 		cout <<" "<< *p<<endl;  // p refers to the 'o' in ('o', 'a', 't')

 		print(l);

 		l.insert(p, 'c');

 		// l is now ('c', 'o', 'a', 't') and p still refers to 'o'

 		cout <<" "<< *p<<endl;

 		print(l);

 		l.erase(p);

 		cout <<" "<< *p<<endl; // p refers to an 'o' but it is not in l!

 		print(l);

 		l.erase(l.begin()); //removes front of l

 		print(l);

 	}

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:

 		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

 void print( list<int> a)

 {

 	for(list<int>::iterator ai=a.begin(); ai!=a.end(); ++ai)

 		cout << *ai << " ";

 	cout << endl;

 	cout << "----------------"<<endl;

 }

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

 		vector<T>::iterator

is the class of suitable iterators. Here are two useful values:

		v.begin()

 		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:

		sort(c.begin(), c.end());

 //Sorting a vector with 9 integers

 #include <iostream.h>

 #include <vector>

 #include <algorithm>

 void print( vector<int> ) ;//utility function outputs a $container

 int main()

 {

 	vector<int> a;

  // Place 9,8,7,6,5,4,3,2,1 into the vector

 	for(int i=0; i<9;++i)

 		a.push_back(9-i);// put new element after all the others

 	print(a); // elements of a are (9,8,7,6,5,4,3,2,1)

 	sort( a.begin(), a.end() ); //in the STL <algorithm> library

 	print(a); // elements are nor in order.

 }

 void print( vector<int> a)

 {

 	for(vector<int>::iterator ai=a.begin(); ai!=a.end(); ++ai)

 		cout << *ai << " ";

 	cout << endl;

 	cout << "----------------"<<endl;

 }

. . . . . . . . . ( end of section Iterators) <<Contents | End>>

More -- See Also

These notes only scratch the surface of the STL. It does not mention:
• 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.
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 [ STL in c++ ]

Also see

My CS202 notes [ stl.html ] [ stl.review.html ] [ 12.html ]

My notes on the <algorithm> library [ stl.algorithms.html ]

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

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

My copy of the C++ LRM Chapters 22..24 [ index.html ]

• 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

Summary

Template	Common	push/pop	items	Extras
stack	empty(), size()	pop(),push(T)	top()	-
queue	empty(), size()	pop(),push(T)	front(),back()	-
vector	empty(), size()	push_back(T), pop_back()	front(), back()	[int], at(int), =
list	empty(), size()	push_back(), pop_back(), push_front(T), pop_front()	front(), back()	sort(), clear(), reverse(), merge(l),at(int), =

Glossary

1. 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.

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

3. 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, ...

4. 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.

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

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

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

8. 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.

9. 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.

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

11. 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.

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

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

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

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. STL::=The Standard Template Library. [ Standard Templates ]

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

23. 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. [ 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:

     		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: [ Older Stacks ] [ Older Queues ]

    On some older compilers and currant libraries when you need a <string> as well as either <list> or <vector> you need to

     		#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.

. . . . . . . . . ( end of section The C++ Standard Template Library) <<Contents | End>>