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.
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 |
. . . . . . . . . ( end of section Standard Templates) <<Contents | End>>
#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:
s.empty()
s.size()
s.push(t)
s.pop()
s.top()
s.top() = expression.
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();
}
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
#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:
q.empty()
q.size()
q.push(t)
q.pop()
q.front()
q.front() = expression.
q.back()
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();
}
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
#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:
l.empty()
l.size()
l.push_back(t)
l.pop_back()
l.push_front(t)
l.pop_front()
l.front()
l.front() = expression.
l.back()
l.back() = expression.
l.sort()
l.clear()
l.merge(list_of_sorted_elements)
l.reverse()
Assign a copy of q1 to q:
q = q1
//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
#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:
v.empty()
v.size()
v.push_back(t)
v.pop_back()
v.front()
v.front() = expression.
v.back()
v.back() = expression.
Access the i'th item (0<=i<size()) without checking to see if it exists:
v[i]
v.at(i)
Assign a copy of v1 to v:
v = v1
. . . . . . . . . ( end of section Vectors) <<Contents | End>>
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);
...
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::iteratorFor any type T, list<T> and vector<T> are Containers. So there are iterator classes called
list<T>::iteratorand they are used like this:
for( list<T>::iterator p=c.begin(); p!=c.end(); ++p)
process(*p);
Vector iterators have type
vector<T>::iteratorand 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:
C::iterator p
++p
*p
The iterator that refers to the first item in c
c.begin()
c.end()
Declare an iterator for container of type C and set to the start of c.
C::iterator p = c.begin();
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:
l.insert(p, x);
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);
}
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>::iteratoris 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:
Also see
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 ]
In CSUSB Library I found
The following includes some stuff on the STL
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), =
|
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>>