Contents

• The C++ Standard Library
• : Quick Reference
• : Also See
• : Vectors
• : Stacks
• : Queues
• : Deques
• : Lists
• : Containers
• : Iterators
• : Pairs
• : Maps and Sets
• : Strings and Streams
• : Algorithms
• : More
• : Errors
• : See Also
• Notes
• Glossary
• Acknowledgements
• Glossary

The C++ Standard Library

This is a short primer on a powerful new set of libraries for the C++ language. The official terminology (circa 1998) is to talk about the "Standard Library" (or SL). One of the special features of this "SL" is the use of templates (template) and so the older nickname "STL" (Standard Template Library) is still(1999) in use by most programmers. I will use the abbreviation "STL" for a collection C++ libraries that allow you to use many well known 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 efficient implementations. It allows us to produce programs using the data structures discovered by computer scientist without going through the effort of developing the code for them each time.

These are designed to be general, efficient, and powerful rather than easy to use. Some of them allow you to easily access items inside the data structure, one at a time. To help you do this C++ has Iterators. An iterator is a kind of generalized subscript. An iterator selects one item in a data structure. An iterator can be moved to different items in the structure.

The C++ library also has a large number of useful Algorithms. These are designed to make it quick to create programs that do well known procedures efficiently.

Quick Reference

Here is an alphabetical list of the most useful libraries.
Table

#include	Description[See]
<algorithm>	ready-to-use functions that manipulate containers of all types [ Algorithms ]
<bitset>	A subset of of a fixed and small set of items [ More ]
<deque>	Double Ended Queue with pop and push at both ends plus indexing. [ More ]
<list>	A randomly changing sequence of items [ Lists ]
<map>	An collection of pairs of items indexed and ordered by the first one [ Maps and Sets ]
<queue>	A Sequence of items with pop and push at opposite ends [ Queues ]
<set>	An ordered collection of items [ Maps and Sets ]
<stack>	A sequence of items with pop and push at one end only [ Stacks ]
<utility>	Defines what a pair is and some other simple classes.
<vector>	A dynamic array [ Vectors ]


(Close Table)
Here is a table of some data structures in the STL and what you can do to them:
Table

Name	Properties	Insert/Delete	Other Operators	Assignment/copy
stack	empty(), size()	pop(),push(T)	top()	operator =
queue	empty(), size()	pop(),push(T)	front(), back()	operator =
vector	empty(), size()	push_back(T), pop_back()	front(), back(), operator[index], at(index)[see note1], Iterators	operator =
deque	empty(), size()	push_back(T), pop_back(), push_front(T), pop_front()	front(), back(), operator[index],	operator =
list	empty(), size()	push_back(), pop_back(), push_front(T), pop_front(), insert(...), erase(...)	front(), back(), sort(), clear(), reverse(), merge(l), Iterators,	operator =
string	empty(), length()	-	operator[index], substr, +(concatenate), Iterators,	operator =
map, multimap	empty(), size()	-	operator[key_type], find(...), count(...), Iterators,	operator =
set, multiset	empty(), size()	insert(...), erase(...)	find(...), count(...), Iterators,	operator =


(Close Table)


Also See

[ cppcontainers.html ] (New Zealand).

Vectors

Vectors are good when we have an unknown sequence of items to store and we want to access them by their sequence numbers. They can have items added and removed at their ends only. They are therefore like a special kind of stack where the items inside the stack can be accessed but not inserted or deleted.
Table

Purpose	Code
To be able to use STL vectors	#include <vector>
To declare an empty vector of items with type T.	vector<T> v;
To declare a vector of n items with type T.	vector<T> v(n);
test to see if v is empty:	v.empty()
find how many items are in v:	v.size()
push t in T onto the end of v:	v.push_back(t)
pop the back 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]
Assign a copy of v1 to v:	v = v1
Sorting and operating on all items efficiently	see Iterators below.


(Close Table)
For an introduction to vectors see [ vectors.html ]

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

Stacks

Stacks are only accessed at one end. We call the accessible end the top. They are useful for calculators, compilers, and any time we want to reverse a sequence of items.

 	void reverse(string & x)

 	{

 		stack<char> s; //creates empty stack of characters

    	//Put characters from x onto the stack

 		   for(int i=0; i<x.length(); ++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();

 	}


Table

Purpose	Code
To use stacks	#include <stack>
Declare an empty stack of items of type T	stack<T> s;
test to see if s is empty:	s.empty()
find how many items are in s:	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;


(Close Table)
Note: You may meet a compiler with the draft version of the STL, see [ Errors ] below.

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

Queues

Queues allow data to be added at one end and taken out of the other end.

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

 		// then taking them off the queue.

 		#include <iostream>

 		#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();

 		}


Table

Purpose	Code
To be able to use STL Queues	#include <queue>
To declare an empty queue of items of type T	queue<T> 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)
remove the front from 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;


(Close Table)
[ Errors ] below. If the above does not work on your system try: [ Older Queues ] below.

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

Deques

A deque is a Double Ended QUEu -- pronounced "deck". You can push and pop both front and back (like a list) and you can access items inside it(like a vector). A deque combines the operations of a list and a vector. But being a Jack-of-all-trades it may be slower than the more specific contianers.
Table

Purpose	Code
To be able to use STL deques	#include <deque>
To declare an empty deque of items of type T	deque<T> 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;
Access the i'th item (0<=i<size()) without checking to see if it exists:	v[i]
Assign a copy of q1 to q:	q = q1
Insert and erase items inside a Deque(slow)	[ Insert and Delete ] below.
Efficiently visit each item in turn	see Iterators below.


(Close Table)


Lists

Lists are good when data needs to be reorganized after it has been stored. They waste space if you only need to change the ends of the list. You can not access them using an index. If you want to do index items use a Vectors or Deques.

Here is an example:

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

 #include <iostream>

 #include <list>

 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)

 }


Table

Purpose	Code
To be able to use STL lists	#include <list>
To declare an empty list of items of type T	list<T> 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 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	[ Insert and Delete ] below.
Efficiently visit each item in turn	see Iterators below.


(Close Table)


Splicing

Given iterators it is often simple and efficient to reorganize a list by splicing ranges from one container to another. See Iterators below. Thus splice is a generic algorithm that most people don't know about.

For example if iterator1 refers to a place in list1 and iterator2 to an element in list2 before this command:

 		list1.splice(iterator1, list2, iterator2);

then the iterator2 item will be moved inside list1 afterwards. The iterators become invalid.

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

Containers

Lists, Vectors, Stacks, Queues, Deques, Sets, Maps, etc. are all Containers. A container is a data structure that holds a number of objects of the same type or class. The oldest example of a Container an array. Some of the features of modern containers are partly inspired by arrays. Here is a simple example:

 	const int max = 10;

 	float a[max];

 	...

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

 		process(a[i]);

 	...

Here is what must be done if the size of an array is determined at run time rather than at compile time:

 	int max;

 	...

 	float * a;

 	a= new float[max];

 	...

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

 		process(a[i]);

 	...

 	delete []a;

Arrays are a primitive data structures. Once declared they stay the same size: no popping or pushing! No insert or erase. They can be accessed by using a subscript, and this access is extremely fast. There is no test for emptiness or a function to find their size! However there is a tricky expression you can use:

 		sizeof(array)/sizeof(array[0])

There is no test to see if the item you ask for exists. Programs can easily crash themselves or the operating system by manipulating nonexistent array items.

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

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

 		process(*p);

 	...

Iterators

Items in Containers are referred to by special objects called iterators. An iterator is a kind of sticky note that you can attach to an item in a container to remember where it is. The container is like a book. Iterators are like sticky notelets.

C++ iterators have syntax based on C pointers. For any serial container c you process all the items by writing:

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

 		process(*p);

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

 		list<T>::iterator

 		vector<T>::iterator

 		set<T>::iterator

All Containers have one or more iterators. Container class C has an iterator called

 		C::iterator

To declare an iterator p for container of type C use:

 		C::iterator p;

Iterators are often declared and initialized like this:

 	list<T>::iterator p=c.begin();

 	vector<T>::iterator p=c.begin();

 	set<T>::iterator p=c.begin();

To move an iterator to the next item in a container write

 		++p;

To see if an iterator has gone past the last item in c use this test:

 		p != c.end();

To see the item that p refers to use *p.

For container classes C of objects type T and any object c of type C:
Table

Purpose	Code
Move iterator p onto the next object in c(if any!).	++p
Access the value selected by p in its container.	*p
To change the value selected by p in its container.	*p = expression
The iterator that refers to the first item in c	c.begin()
The iterator that refers to one beyond c.	c.end()
Test to see if iterator p has come to the end of container c:	p != c.end();
Make p refer to the same item as p1	p = p1;


(Close Table)
For an example see print_vector below.

The names for containers and iterators are long winded. C and C++ have a way to define a short name for a complex data type. The statement

 		typedef list< int> L;

defines L to be short for list<int> and then

 		typedef L::iterator LI;

defines LI to be the type list<int>::iterator.

Insert and Delete

Insertion and deletion of items at inside a List of elements is controlled by an iterator(see Iterators below for details). An iterator is like a Post-It note stuck to an item in a container. It indicates our place, it can be moved, and it shows us where to do things. The same operations work on a deque -- but are not efficient. Inserting and deleting general items are not permitted on vectors, stacks, and queues.
Table

Purpose	Code
Insert item x into List l before item pointed at by iterator p	l.insert(p, x);
Erase the element pointed at by iterator q in List l	l.erase(q);


(Close Table)
The following program shows how this works.

 	#include <iostream>

 	#include <list>

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

 	main()

 	{	list <char> l;

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

 		print(l); // l is ('o', 'a', 't').

 		list <char>::iterator p;

 		p=l.begin();

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

 		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);

 	}

Invalid Iterator

If an iterator refers to an item that is erased then the iterator is said to be invalid. You dare not use it (in a *, ++, or a -- for instance) until it is given an item to point at.

Ranges

A pair of iterators can describe a range of items in their container. The items start with the first iterator in the range. The range includes all the following items up to just before the item referred to by the last iterator of the pair. For example, in a list '(a, b, c)' if pa refers to the a and q refers to the c, then the range [p, q) (this is the math notation for a half-open interval, NOT C++) refers to the sub-list '(a, b)' only. If e refers to the end() of the list then [p, e) indicates the whole list, and [q, e) the items (c).

For many containers we have a range that includes the whole container:

		container.begin()

 		container.end()

The above pair encloses the complete container. Given a container c, then c.begin() and c.end() form a range.

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.

Here are two examples - one prints a list and the other a vector:
(print_list):

 void print( list<int> &a)

 {

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

 		cout << *ai << " ";

 	cout << endl;

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

 }


(print_vector):

 void print( vector<int> &a)

 {

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

 		cout << *ai << " ";

 	cout << endl;

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

 }

You can see how alike the code for print_list and print_vector are.

Special Iterators

If the C++ compiler knows that you don't plan to change the data that an iterator refers to then it can use a more efficient implementations. Iterators that can access a sequence of items without changing them are called "const iterators". They have a type like the following:
(const_iterator):

 		Container_type::const_iterator

All operations on iterators work with const_iterators, unless they change the value of the items the iterators refer to. For example if p is a const_iterator then you can not write '(*p) = something'. Further 'p->operation(...)' or '(*p).operation(...)' will only compile when the operation is declared to not change the object to which it applies. In other words it must be a const member function.

An iterator works well for handling existing items in a container. It can access and change existing items. It is not designed to add items. A normal iterator can work incorrectly if it is used to add data to a container before or after the container. An inserter is a special kind of iterator that adds new items to a container. The library <iterator> provides three ready made inserters:
(inserters):
Table

back_inserter(Container& C)	[ inserter.cpp ]
front_inserter( Container& C)	[ front.inserter.cpp ]
inserter(Container & C, Container_iterator p) (insert before p)	TBA


(Close Table)


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

Pairs

In the library <utility> and included in other standard libraries such as <map> there is a class of pairs that implement the mathematical idea of a Cartesian product. They are used to constract maps and for other purposes.
1. pair::=following
   Table

   Purpose	Notation	Meaning
   class name	pair<X, Y>	set of pairs (x,y) where x is in class X and y is in class Y.
   get first	pair.first	the first item in pair
   get second item	pair.second	the second item in pair
   make a new pair	make_pair(x,y)	constructs instance of pair<X,Y> with first=x and second=y.

   
   (Close Table)
   

   Maps and Sets

   A map is a collection of pairs(Pairs above) where for each first element value there is no more than one second element. For example, a map<Name, PhoneNumber> can hold data like this make_pair(Name("Dick"), PhoneNumber(5327)). If this record is r then r.first == Name("Dick) and r.second == PhoneNumber(5327). The map organizes all the names and numbers so that they can be found quickly if you provide a name by using the ordering for Names.

   Maps are often used to organize information in a table or part of a data base.

   In the C++ library <map> allows you to use a very clever data structure that stores pairs of items in it. If you declare a map<A,B> then it will store one B value paired with each A value. Maps give a new meaning to the subscript or array index operator []. If we have a map<A,B> f then 'f[a]=b' adds a new item to the map that associates 'a' with 'b'. We can then recall 'b' as the value f[a].

   We can test to see if a map has a 'a' like this

    		if( f.find(a) != f.end() )

   If we declare map<A,B> f then for each a in A we have the paired item f [ a ]. If p is an iterator then (*p).first will be the A in each pair in turn, and (*p).second is the associated B value.

   Here is a example of a quick and dirty program to help me add up all the scores in particular class. All I have to do is type in all the points scored in the class as a sequence of names and scores.

    adam 10 eve 15 adam 17 eve  5 eve 5 eve 4 adam 10

   It prints out a sorted list of names each with their total score:

    	#include <string>

    	#include <iostream>

    	#include <map>

    	typedef map<string,int> MSI; //abbreviation: MSI's are sets Mapping Strings to Ints

    	int main()

    	{

    		MSI score;

    		string si;//student id on input

    		int sc;//score for student with id si

    		while( cin>>si>>sc )

    		   score[si] = score[si] + sc;

    		   /* for each si on the input, score[si] is the sum of si's scores.

    		   */

    		for( MSI::iterator p= score.begin(); p!=score.end(); p++)

    			cout << (*p).first << "\t" << (*p).second <<endl;

    	}//main

   [ scoring.cpp ] It would be hard to write a program this simple that gave me equal flexibility with out using <map>.

   Here [ fibcache.cpp ] is a way to use a map to keep values in a recursive function (fibonaci again) from re-evaluating the same value more than once.

   If all you want to do is collect some items together and keep them in order you can use the C++ <set> template. Here is a simple example [ stlset.cpp ] of using the standard library set to accumulate a set of strings, print them, remove one, and print them again. Seeing that set is an ordered set of elements you also sort the data as it is stored.

   If you need to store multiple copies of the same data in a map or set then use multimap and multiset instead. They are in the same libraries (<map> and <set> respectively) and work almost identically. However, in a set each items can appear only once, in a multiset an item can appear many times. Similarly in a multimap you can have more than one pair(x,y) with the same x value.

   In general the standard C++ set<T> and map <T> only works if you have the "<" operator defined on data of type T. This is OK for all elementary data type and for strings. If you want T to be your own class you have to define an operator < in the class:

    		class T{

    			...

    			public:

   				bool operator<(T other){.....}

    			...

    		};// class T

   Sets, multisets, and maps store the data in increasing size. So you can easily sort data by inserting it into a multimap (say) and then using an iterator to get it out in sorted order.

   Strings and Streams

   The designers of the C++ library made sure that the <string> library shares a lot of common features with <vector> and other sequential containers. The main differences are (1) <string>s can only hold characters, and (2)<string>s have some useful extra operations available. See [ string ] (text) [ string.html ] (HTML). which is a summary of the <string> library.

   Similarly input and output streams can be treated like containers. In particular, you can attach an iterator to a stream and use read(istream_iterator) or write(ostream_iterator) functions on it! Because strings and streams have iterators they can be used as sources and targets for many of the algorithms in the <algorithm> library. See Algorithms.

   Algorithms

   The STL has 60 or more ready-to-use algorithms based on using Iterators and Ranges. These are often the easiest code and fastest solution you could do if you work hard reinventing the wheel. For example if you have a type or class of data called T and in a program are working with a vector v of type vector<T> and the operator > is defined for T then you can sort a vector v simply by writing:

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

   Here is a sample of the code:
   (sort_vector):

    //Sorting a vector with 9 integers

    #include <iostream>

    #include <vector>

    #include <algorithm>

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

    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 now in order.

    }

   Here is a quick list of some simpler algorithms in <algorithm>. In each example the elements processed are in range [first .. end):
   Table

   Name	Arguments	Returns	Note
   for_each	(first, end, function)	void	apply a function to all items in range.
   find	(first, end, value)	iterator	find item in range that matches an item.
   count	(first, end, value)	number	count matching items in range.
   equal	(first, end, another)	bool	true iff all items in two ranges are equal.
   transform	(first, end, function)	void	apply transformation to items in range.
   copy	(first, end, another)	void	copy one range to another(works between containers of different types!).
   reverse	(first, end)	void	reverse items in range.
   rotate	(first, end)	void	end of range moved in front of start.

   
   (Close Table)
   

   More

   These notes only scratch the surface of the STL. There are many more ready made data structures and algorithms available, See [ See Also ] below.

   Each instance of a template class is itself a class. It can be used as an element in any of the data structures mentioned here. Thus you can have a vector of lists of ints:

    		vector < list <int> > vli;

   or a list of vectors:

    		list < vector <int> > lvi;

   Or even a stack of vectors each containing a number of queues of strings:

    		stack< vector < queue < string > > > svqs;

   Be careful however to put a space between the ">"s in declarations like these. C++ has a special meaning for the symbol ">>".

   Here are some of the other ready-to-wear templates:

   • Deques (Double Ended Queues, vectors thta grow at both ends).
   • Bitsets, multisets, multimaps, pairs, valarrays, ...
   • Reversed iterators.
   • Higher order functions that do things to all items in a range in an algorithm,
   • Predicates that select items in a range for an algorithm.

   You can also create your own container classes! A Computer Science Data Structures (CS2) class like CSUSB's CS330 will teach you how these data structures are implemented. There are some useful resources on the world wide web, see [ See Also ] below.

   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.

   There must be a space between the two ">" signs below:

    		stack< vector< T > > svt;

   If a program compiles, loads, crashes, and there is a subscript operator ([...]) then check to see if the subscripted item has been put into the container before the subscripted element is accessed. A very common error is to declare a vector with no length and instead of using push_back to add new items, to use [...] as if it created new elements. It doesn't.

   If you are unable to show that a subscript is in range then use a condition like the following to guard thing[i] from errors:

    		0<= i && i < thing.size()

   If a program compiles, loads and crashes and it has a pop, pop_back, or a pop_front function than make sure that there is an item to be "popped"! In code you can use the empty function to guard statements that contain "pop" from blowing up.

   On our currant compiler you will find that 'at' generates an error. Use '[i]' (very carefully) instead!

   On some older compilers and 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.

   If the standard <list> and <vector> is not found then you are using an older C++ compiler.

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

    		stack< vector<T> > s;

   or

    		stack< list<T> > s;

   or

    		queue< list<T> > q;

   or

    		queue< vector<T> > q;

   If you are forced to do this... lookout for the space between ">" and ">"!

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

   See Also

   Here are the parts of C++ standard defining C++ library
   • Chapter 17: Library introduction [lib.library]
   • Chapter 18: Language support library [lib.language.support]
   • Chapter 19: Diagnostics library [lib.diagnostics]
   • Chapter 20: General utilities library [lib.utilities]
   • Chapter 21: Strings library [lib.strings]
   • Chapter 22: Localization library [lib.localization]
   • Chapter 23: Containers library [lib.containers]
   • Chapter 24: Iterators library [lib.iterators]
   • Chapter 25: Algorithms library [lib.algorithms]
   • Chapter 26: Numerics library [lib.numerics]
   • Chapter 27: Input/output library [lib.input.output]
   [ index.html ] for a local copy of an early (1996) draft. SGI maintain an uptodate version: [ http://www.sgi.com/Technology/STL/ ]

   Also see my notes on the C++ language: [ STL in c++ ]

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

Notes


(note1): This feature is not available on the Gnu 2.9 C++ that we use at CSci CSUSB.
(at): at(index) is in theory a safer and slower version of subscripting, and also a non-operator member function that has some advanced uses. However, many libraries make it fast and unsafe, just like [index].

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. at(i)::=an operation that accesses the i'th item in a sequential container as long as i is between 0 and size()-1 inclusive. In theory v.at(i) differs from v[i] in that i is checked to see if it is in range before the computer attempts to access the item.

3. begin::=an operator on a container that returns an iterator value that refers to the front item in the container.
   
4. (above)|-for all containers c, c.begin() == & c.front().

5. back::=a special item in a sequential container that has no items after it. The iterator end() is always the next place after the back item.

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

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

8. empty::= an operation on a container that returns a bool value that is true when nothing is contained in the container and false otherwise.

9. end::=an operation on a container that returns an iterator value. The end() value is a not the back but refers to a nonexistent item after the back of the container. Compare NULL.

10. erase::=an operation on sets and lists that removes an element.

11. deque::=double ended queue. See Deques above.

12. deques::word=plural of deque.

13. front::=a special item in a sequential container that has no other items before it. The front of a sequential container is referred to by iterator begin().

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

15. index::expression=an expression normally written in square brackets that selects one particular value that has been stored in a container. Vectors and deques have int indices, and maps can have any type of index. Some containers do not have indices (sets and lists for example) and we use an iterator in their place.

16. indices::word=plural of index.

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

18. insert::=an operation on sets and lists that place a new item in the container.

19. inserter::iterator=an iterator that creates a new item in a container every time a value is placed in it. See Inserters.

20. instance::=a particular example of a general type, an instance of a template is created by binding the formal arguments to a specific type of data. For example "list<int>" is an instance of "list".

21. iterators::=plural of iterator.
22. 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.

23. length::=an operator on a string that returns an int that is the number of characters in the string. Compare with size in other containers.

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

25. list::container=a sequential container that is organized to allow items to be inserted and erased at any point in the container. [ Lists ]

26. map::=a set of pairs such that each first item in a pair occurs no more than once.

27. maps::word=plural of map.

28. multimap::=a set of pairs where the first elements may repeat.

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

30. operation::=something that can be applied to an object to access information in it or to change its state.
31. operator::=the C++ keyword that indicates the function associated with an operator symbol like: < > = !=, ==, [], (), +, ++, -, --, and so on.

32. pair::class=`A simple structure with two public data members called firs and second, used in maps.
33. push::operation=to add a new item to one or other end of stacks and queues.
34. push_back::operation=to add a new item at one end of a sequential container.
35. push_front::operation=to add a new item at one end of some kinds of sequential containers -- list, deque.
36. pop::operation=to remove an item from one or other end of a stack or queue.
37. pop_back::operation=to erase an item at one end of a non-empty sequential container.
38. pop_front::operation=to erase an item at one end of some kinds of non-empty sequential containers -- list, deque.

39. pointers::=plural of pointer.
40. pointer::=a piece of storage that contains either a NULL value or a single address of another piece of storage.

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

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

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

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

45. set::=an associative container the allows items to be inserted and erased in order efficiently. See [ Maps and Sets ]

46. size::=an operator on a container that returns an int that equals the number of elements in the container. The back of a sequential container is always the item at(size()-1) not at(size()). Compare with length for strings.

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

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

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

50. template::= See http://cse.csusb.edu/dick/cs202/templates.html , notes on templates.

51. top::=the accessible element in a non-empty stack is called the top, this element can be popped of the stack.

52. 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 off 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 ]

    Acknowledgements

    Dr. Botting wants to acknowledge the help and advice given by Dr. Zemoudeh and Mr. Li Qiu with this document. Whatever errors remain are Dr. Botting's mistakes.

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

Glossary