Please visit the following sites for STL -
STL Tutorial:
Ready-made Components for use with the STL
Main STL sites -
The STL offers the programmer a number of useful data structures and algorithms. It is made up the following components.
I will be considering the use of the vector, list, set and map containers. To make use of these containers you have to be able to use iterators so I shall have something to say about STL iterators. Using the set and map containers can mean having to supply a simple function object to the instantiation so I shall also have something to say about function objects. I will only briefly mention the algorithms supplied by the STL. I will not mention adaptors at all.
I have taken liberties with some of the types of function arguments -- for example most of the integer arguments referred to in what follows actually have type size_type which is typedef'ed to an appropriate basic type depending on the allocation model being used. If you want to see the true signatures of the various functions discussed have a look at the Working Paper or the header files.
There are a number of utility classes supplied with the STL. The only one of importance to us is the pair class. This has the following definition:
template<class T1, class T2>
class pair {
public:
T1 first;
T2 second;
pair(const T1& a, const T2& b) : first(a), second(b) {}
};
and there is a convenient function make_pair with signature:
pair<T1,T2> make_pair(const T1& f, const T2&,s)
as well as implementations of operator== and operator < . There is nothing complicated about this template class and you should be able to use it without further guidance. To use it #include the header file pair.h. It crops up in a number of places but particularly when using the set and map classes.
To use the various bits of the STL you have to #include the appropriate header files. These may differ slightly from compiler to compiler but for g++ the ones of interest are:
If you don't want to remember which is which you could just use stl.h which includes all the above (and all the other header files of the STL as well).
The container classes have many member functions that have the same names. These functions provide the same (or very similar) services for each of the classes (though, of course, the implementations will be different). The following table lists the functions that we shall consider in more detail. A star opposite a function name indicates that the container type heading the column provides a member function of that name.
|
Operation | Purpose | Vector | List | Set | Map | |
| == | comparison | * | * | * | * | |
| < | comparison | * | * | * | * | |
| begin | iterator | * | * | * | * | |
| end | iterator | * | * | * | * | |
| size | no. of elements | * | * | * | * | |
| empty | is container empty | * | * | * | * | |
| front | first element | * | * | |||
| back | last element | * | * | |||
| [ ] | element access/modification | * | * | |||
| insert | insert element(s) | * | * | * | * | |
| push_back | insert new last element | * | * | |||
| push_front | insert new first element | * | ||||
| erase | remove element(s) | * | * | * | * | |
| pop_back | remove last element | * | * | |||
| pop_front | remove last element | * | ||||
|
|
If the following discussion leaves something unclear (and it will) you can always write a small test program to investigate how some function or feature behaves.
A vector is an array like container that improves on the C++ array types. In particular it is not neccessary to know how big you want the vector to be when you declare it, you can add new elements to the end of a vector using the push_back function. (In fact the insert function allows you insert new elements at any position of the vector, but this is a very inefficent operation -- if you need to do this often consider using a list instead).
vector is a class template so that when declaring a vector object you have to state the type of the objects the vector is to contain. For example the following code fragment
vector<int> v1; vector<string> v2; vector<FiniteAutomaton> v3;
declares that v1 is a vector that holds integers, v2 a vector that holds strings and v3 holds objects of type FiniteAutomaton (presumably an user defined class type). These declarations do not say anything about how large the vectors are to be (implementations will use a default starting size) and you can grow them to as large as you require.
You can give an inital size to a vector by using a declaration like
vector<char> v4(26);
which says that v4 is to be vector of characters that initially has room for 26 characters. There is also a way to initailise a vector's elements. The declaration
vector<float> v5(100,1.0);
says that v5 is a vector of 100 floating point numbers each of which has been initialised to 1.0.
Once you have created a vector you can find out the current number of elements it contains by using the size function. This function takes no arguments and returns an integer (strictly a value of type size_type, but this gets converted to an integer) which says how many elements there are in the vector. What will be printed out by the following small program?
<vector-size.cc>=
#include <iostream.h>
#include <vector.h>
void main()
{
vector<int> v1;
vector<int> v2(10);
vector<int> v3(10,7);
cout << "v1.size() returns " << v1.size() << endl;
cout << "v2.size() returns " << v2.size() << endl;
cout << "v3.size() returns " << v3.size() << endl;
}
To check on wether your vector is empty or not you can use the empty function. This takes no arguments and returns a boolean value, true if the vector is empty, false if it is not empty. What will be printed out by the following small program (true prints as 1 and false prints as 0)?
<vector-empty.cc>=
#include <iostream.h>
#include <vector.h>
void main()
{
vector<int> v1;
vector<int> v2(10);
vector<int> v3(10,7);
cout << "v1.empty() has value " << v1.empty() << endl;
cout << "v2.empty() has value " << v2.empty() << endl;
cout << "v3.empty() has value " << v3.empty() << endl;
}
You can access a vector's elements using operator[]. Thus, if you wanted to print out all the elements in a vector you could use code like
vector<int> v;
// ...
for (int i=0; i<v.size(); i++)
cout << v[i];
(which is very similar to what you might write for a builtin array).
You can also use operator[] to set the values of the elements of a vector.
vector<int> v;
// ...
for (int i=0; i<v.size(); i++)
v[i] = 2*i;
The function front gives access to the first element of the vector.
vector<char> v(10,'a'); // ... char ch = v.front();
You can also change the first element using front.
vector<char> v(10,'a'); // ... v.front() = 'b';
The function back works the same as front but for the last element of the vector.
vector<char> v(10,'z'); // ... char last = v.back(); v.back() = 'a';
Here is a simple example of the use of [].
<vector-access.cc>=
#include <vector.h>
#include <iostream.h>
void main()
{
vector<int> v1(5);
int x;
cout << "Enter 5 integers (seperated by spaces):" << endl;
for (int i=0; i<5; i++)
cin >> v1[i];
cout << "You entered:" << endl;
for (int i=0; i<5; i++)
cout << v1[i] << ' ';
cout << endl;
}
Along with operator[] as described above there are a number of other ways to change or access the elements in a vector.
Note that insert and erase are expensive operations on vectors. If you use them a lot then you should consider using the list data structure for which they are more efficient.
<vector-mod.cc>=
#include <iostream.h>
#include <vector.h>
void main()
{
vector<int> v;
for (int i=0; i<10; i++) v.push_back(i);
cout << "Vector initialised to:" << endl;
for (int i=0; i<10; i++) cout << v[i] << ' ' ;
cout << endl;
for (int i=0; i<3; i++) v.pop_back();
cout << "Vector length now: " << v.size() << endl;
cout << "It contains:" << endl;
for (int i=0; i<v.size(); i++) cout << v[i] << ' ';
cout << endl;
int a1[5];
for (int i=0; i<5; i++) a1[i] = 100;
v.insert(& v[3], & a1[0],& a1[3]);
cout << "Vector now contains:" << endl;
for (int i=0; i<v.size(); i++) cout << v[i] << ' ';
cout << endl;
v.erase(& v[4],& v[7]);
cout << "Vector now contains:" << endl;
for (int i=0; i<v.size(); i++) cout << v[i] << ' ';
cout << endl;
}
In the above a vector v has been declared then initialised using push_back. Then some elements have been trimmed off it's end using pop_back. Next an ordinary integer array has been created and then some of its elements inserted into v using insert. Finally erase has been used to remove elements from v. The functions used above take arguments as follows.
The simple way to step through the elements of a vector v is as we have done above:
for (int i=0; i<v.size(); i++) { ... v[i] ... }
Another way is to use iterators. An iterator can be thought of as a pointer into the container, incrementing the iterator allows you to step through the container. For container types other than vectors iterators are the only way to step through the container.
For a vector containing elements of type T:
vector<T> v;
an iterator is declared as follows:
vector<T>::iterator i;
Such iterators are constructed and returned by the functions begin() and end(). You can compare two iterators (of the same type) using == and !=, increment using ++ and dereference using *. [In fact vector iterators allow more operations on them - see next section for more information].
Here is an illustration of how to use iterators with vectors.
<vector-iterator.cc>=
#include <iostream.h>
#include <vector.h>
void main()
{
vector<int> v(10);
first is ``less'' than the second
int j = 1;
vector<int>::iterator i;
// Fill the vector v with integers 1 to 10.
i = v.begin();
while (i != v.end())
{
*i = j;
j++;
i++;
}
// Square each element of v.
for (i=v.begin(); i!=v.end(); i++) *i = (*i) * (*i);
// Print out the vector v.
cout << "The vector v contains: ";
for (i=v.begin(); i!=v.end(); i++) cout << *i << ' ';
cout << endl;
}
Note how *i can be used on the left-hand side of an assignment statement so as to update the element pointed at by i, and on the right-hand side to access the current value.
You can compare two vectors using == and <. == will return true only if both vectors have the same number of elements and all elements are equal. The < functions performs a lexicographic comparison of the two vectors. This works by comparing the vectors element by element. Suppose we are comparing v1 and v2 (that is v1 < v2?). Set i=0. If v1[i] < v2[i] then return true, if v1[i] > v2[i] then return false, otherwise increment i (that is move on to the next element). If the end of v1 is reached before v2 return true, otherwise return false. Lexicographic order is also known as dictionary order. Some examples:
(1,2,3,4) < (5,6,7,8,9,10) is false. (1,2,3) < (1,2,3,4) is true (1,2,3,4) < (1,2,3) is false (0,1,2,3) < (1,2,3) is true
The following code illustrates the third example above.
<vector-comp.cc>=
#include <vector.h>
#include <iostream.h>
void main()
{
vector<int> v1;
vector<int> v2;
for (int i=0; i<4; i++) v1.push_back(i+1);
for (int i=0; i<3; i++) v2.push_back(i+1);
cout << "v1: ";
for (int i=0; i<v1.size(); i++) cout << v1[i] << ' ';
cout << endl;
cout << "v2: ";
for (int i=0; i<v2.size(); i++) cout << v2[i] << ' ';
cout << endl;
cout << "v1 < v2 is: " << (v1<v2 ? "true" : "false") << endl;
}
See the section STL References
See the section STL References
The set container type allows an user to store and retrieve elements directly rather than through an index into the container. The set container acts as a mathematical set in that it holds only distinct elements. However unlike a mathematical set, elements in a set container are held in (an user-supplied) order. In practise this is only a minor restriction on treating a set container as an implementation of the mathematical set abstract data type, and it allows for a much more efficent implementation than an unordered approach.
Two template arguments are required to construct a set container -- the type of the objects the set is to contain and a function object that can compare two elements of the given type, that is:
set<T, Compare> s;
(The declaration set < T > s should also be possible -- it would use a default template argument less < T > as the second argument, but many C++ compilers (including g++) cannot as yet cope with default template arguments.)
For simple types T we can use the function object less < T > ( without having to worry about what a ``function object'' is), for example all the following are legal set declarations.
set<int, less<int> > s1; set<double, less<double> > s2; set<char, less<char> > s3; set<string, less<string> > s4;
(Note that the space between the two final >'s in the template is required - otherwise the compiler will interpret >> as the right shift operator.) In each of these cases the function object makes use of the operator < as defined for the the underlying type (that is int, double, char and string).
The following code declares a set of integers, then adds some integers to the set using the insert method and then prints out the set members by iterating through the set. You will note that the set's contents are printed out in ascending order even though they were added in no particular order.
<set-construct1.cc>=
#include <iostream.h>
#include <set.h>
void main()
{
set<int, less<int> > s;
set<int, less<int> >::iterator i;
s.insert(4);
s.insert(0);
s.insert(-9);
s.insert(7);
s.insert(-2);
s.insert(4);
s.insert(2);
cout << The set contains the elements: ;
for (i=s.begin(); i!=s.end(); i++) cout << *i << ' ';
cout << endl;
}
Note that 4 is added twice but only turns up once on the list of elements -- which is what one expects of a set.
One of the nifty features of C++ is the ability to overload operators, so that one can have + mean whatever one likes for your newly designed class. One of the operators C++ allows you to overload is the function call operator () and this allows you to create classes whose instances can behave like functions in many ways. These are function objects.
Here is a simple example.
<function-object.cc>=
#include <iostream.h>
template<class T>
class square {
public:
T operator()(T x) { return x*x; }
};
// This can be used with any T for which * is defined.
void main()
{
// Create some function objects.
square<double> f1;
square<int> f2;
// Use them.
cout << 5.1^2 = << f1(5.1) << endl;
cout << 100^2 = << f2(100) << endl;
// The following would result in a compile time error.
// cout << 100.1^2 = << f2(100.1) << endl;
}
Function objects are used in a number of places in the STL. In particular they are used when declaring sets and maps.
The function object required for these purposes, let's suppose it is called comp, must satisfy the following requirements.
If for any particular objects x and y, both comp(x,y) and comp(y,x) are false then x and y are deemed to be equal.
This, in fact, is just the behaviour of the strictly-less-than relation (ie < ) on numbers. The function object less < T > used above is defined in terms of a < operator for the type T. It's definition can be thought of as follows.
template<class T>
struct less {
bool operator()(T x, T y) { return x<y; }
}
(The actual definition uses references, has appropriate const annotations and inherits from a template class binary_function.)
This means that if the type T has operator < defined for it then you can use less < T > as the comparator when declaring sets of T. You might still want to use a special purpose comparator if the supplied < operator is not appropriate for your purposes. Here is another example. This defines a simple class with a definition of operator < and a function object that performs a different comparison. Note that the overloaded < and () operators should be given const annotations so that the functions work correctly with the STL.
<set-construct2.cc>=
#include <iostream.h>
#include <set.h>
// This class has two data members. The overloaded operator< compares
// such classes on the basis of the member f1.
class myClass {
private:
int f1;
char f2;
public:
myClass(int a, char b) : f1(a), f2(b) {}
int field1() const { return f1; }
char field2() const { return f2; }
bool operator<(myClass y) const
{ return (f1<y.field1()); }
};
// This function object compares objects of type myClass on the basis
// of the data member f2.
class comp_myClass {
public:
bool operator()(myClass c1, myClass c2) const
{ return (c1.field2() < c2.field2()); }
};
void main()
{
set<myClass, less<myClass> > s1;
set<myClass, less<myClass> >::iterator i;
set<myClass, comp_myClass> s2;
set<myClass, comp_myClass>::iterator j;
s1.insert(myClass(1,'a'));
s2.insert(myClass(1,'a'));
s1.insert(myClass(1,'b'));
s2.insert(myClass(1,'b'));
s1.insert(myClass(2,'a'));
s2.insert(myClass(2,'a'));
cout << Set s1 contains: ;
for (i=s1.begin(); i!=s1.end(); i++)
{ cout << ( << (*i).field1() << ,
<< (*i).field2() << ) << ' ';
}
cout << endl;
cout << Set s2 contains: ;
for (j=s2.begin(); j!=s2.end(); j++)
{ cout << ( << (*j).field1() << ,
<< (*j).field2() << ) << ' ';
}
cout << endl;
}
The set s1 contains (1,a) and (2,a) as comparison is on the data member f1, so that (1,a) and (1,b) are deemed the same element. The set s2 contains (1,a) and (1,b) as comparison is on the data member f2, so that (1,a) and (2,a) are deemed the same element.
The way we have printed out the sets in the previous examples is a little awkward so the following header file containing a simple overloaded version of operator<< has been written. It works fine for small sets with simple element types.
<printset.h>=
#ifndef _PRINTSET_H
#define _PRINTSET_H
#include <iostream.h>
#include <set.h>
template<class T, class Comp>
ostream& operator<<(ostream& os, const set<T,Comp>& s)
{
set<T,Comp>::iterator iter = s.begin();
int sz = s.size();
int cnt = 0;
os << {;
while (cnt < sz-1)
{
os << *iter << ,;
iter++;
cnt++;
}
if (sz != 0) os << *iter;
os << };
return os;
}
#endif
The use here of << as an output routine for a set assumes that << has been defined for the set elements, and uses this to print a comma delimited list of the set elements wrapped in curly braces. It will be used without comment in the following examples.
You can determine if a set is empty or not by using the empty() method. You can find out how many elements there are in a set by using the size() method. These methods take no arguments, empty() returns true or false and size() returns an integer.
<set-size.cc>=
#include <iostream.h>
#include <set.h>
#include printset.h
void main()
{
set<int, less<int> > s;
cout << The set s is
<< (s.empty() ? empty. : non-empty.) << endl;
cout << It has << s.size() << elements. << endl;
cout << Now adding some elements... << endl;
s.insert(1);
s.insert(6);
s.insert(7);
s.insert(-7);
s.insert(5);
s.insert(2);
s.insert(1);
s.insert(6);
cout << The set s is now
<< (s.empty() ? empty. : non-empty.) << endl;
cout << It has << s.size() << elements. << endl;
cout << s = << s << endl;
}
Two sets may be checked for equality by using ==. This equality test works by testing in order the corresponding elements of each set for equality using T::operator==.
<set-equality.cc>=
#include <iostream.h>
#include <set.h>
#include printset.h
void main()
{
set<int, less<int> > s1, s2 ,s3;
for (int i=0; i<10; i++)
{
s1.insert(i);
s2.insert(2*i);
s3.insert(i);
}
cout << s1 = << s1 << endl;
cout << s2 = << s2 << endl;
cout << s3 = << s3 << endl;
cout << s1==s2 is: << (s1==s2 ? true. : false.) << endl;
cout << s1==s3 is: << (s1==s3 ? true. : false.) << endl;
}
It is also possible to compare two sets using <. The comparison s1 < s2 is true if the set s1 is lexicographically less than the set s2, otherwise it is false.
The way to add elements to a set is to use the insert method (as we have done above). The way to delete elements from a set is to use the erase method.
For a set holding elements of type T these methods come in following forms:
The following example illustrates these various forms.
<set-add-delete.cc>=
#include <iostream.h>
#include <set.h>
#include printset.h
void main()
{
set<int, less<int> > s1;
// Insert elements in the standard fashion.
s1.insert(1);
s1.insert(2);
s1.insert(-2);
// Insert elements at particular positions.
s1.insert(s1.end(), 3);
s1.insert(s1.begin(), -3);
s1.insert((s1.begin()++)++, 0);
cout << s1 = << s1 << endl;
// Check to see if an insertion has been successful.
pair<set<int, less<int> >::iterator,bool> x = s1.insert(4);
cout << Insertion of 4 << (x.second ? worked. : failed.)
<< endl;
x = s1.insert(0);
cout << Insertion of 0 << (x.second ? worked. : failed.)
<< endl;
// The iterator returned by insert can be used as the position
// component of the second form of insert.
cout << Inserting 10, 8 and 7. << endl;
s1.insert(10);
x=s1.insert(7);
s1.insert(x.first, 8);
cout << s1 = << s1 << endl;
// Attempt to remove some elements.
cout << Removal of 0 << (s1.erase(0) ? worked. : failed.)
<< endl;
cout << Removal of 5 << (s1.erase(5) ? worked. : failed.)
<< endl;
// Locate an element, then remove it. (See below for find.)
cout << Searching for 7. << endl;
set<int,less<int> >::iterator e = s1.find(7);
cout << Removing 7. << endl;
s1.erase(e);
cout << s1 = << s1 << endl;
// Finally erase everything from the set.
cout << Removing all elements from s1. << endl;
s1.erase(s1.begin(), s1.end());
cout << s1 = << s1 << endl;
cout << s1 is now << (s1.empty() ? empty. : non-empty.)
<< endl;
}
We mention two member functions that can be used to test if an element is present in a set or not.
The use of find has been illustrated above. We could use count to write a simple template based set membership function. (This should also provide a version that takes a reference to the argument x.)
<setmember.h>=
#ifndef _SETMEMBER_H
#define _SETMEMBER_H
#include <set.h>
template<class T, class Comp>
bool member(T x, set<T,Comp>& s)
{
return (s.count(x)==1 ? true : false);
}
#endif
Which might be used as follows.
<set-membership.cc>=
#include <iostream.h>
#include <set.h>
#include printset.h
#include setmember.h
void main()
{
set<int, less<int> > s;
for (int i= 0; i<10; i++) s.insert(i);
cout << s = << s << endl;
cout << 1 is << (member(1,s) ? : not) << a member of s
<< endl;
cout << 10 is << (member(10,s) ? : not) << a member of s
<< endl;
}
The STL supplies as generic algorithms the set operations includes, union, intersection, difference and symmetric diffference. To gain access to these functions you need to include algo.h. (In what follows iter stands for an appropriate iterator).
This checks to see if the set represented by the range [f2,l2] is included in the set [f1,l1]. It returns true if it is and false otherwise. So to check to see if one set is included in another you would use
includes(s1.begin(), s1.end(), s2.begin(), s2.end())
The includes function checks the truth of 3#3 ( that is of 4#4). This function assumes that the sets are ordered using the comparison operator <. If some other comparison operator has been used this needs to be passed to includes as an extra (function object) argument after the other arguments.
This forms the union of the sets represented by the ranges [f1,l1] and [f2,l2]. The argument result is an output iterator that points at the start of the set that is going to hold the union. The return value of the function is an output iterator that points at the end of the new set.
The fact that the result argument is an output iterator means that you cannot use set_union in the following, natural, fashion:
set<int, less<int> > s1, s2, s3;
// Add some elements to s1 and s2 ...
// Then form their union. (This does not work!)
set_union(s1.begin(), s1.end(),
s2.begin(), s2.end(),
s3.begin());
The reason is that begin() (also end()) when used with sets (or maps) returns a (constant) input iterator. This type of iterator allows you to access elements of the set for reading but not writing. (And this is a Good Thing since if you could assign to a dereferenced iterator (as in (*i)= ...) then you could destroy the underlying order of the set.)
The solution is to use an insert iterator based on the set type. This, basically, converts an assignment (*i)=value (which is illegal) into a (legal) insertion s.insert(i,value) (where s is the set object that the iterator i is pointing into). It is used as follows:
// Typedef for convenience.
typedef set<int, less<int> > intSet;
intSet s1, s2, s3;
// Add some elements to s1 and s2 ...
// Then form their union.
set_union(s1.begin(), s1.end(),
s2.begin(), s2.end(),
insert_iterator<intSet>(s3,s3.begin()) );
Here is an example illustrating all these operations.
<set-theory.cc>=
#include <iostream.h>
#include <set.h>
#include <algo.h>
#include <iterator.h>
#include printset.h
void main()
{
typedef set<int, less<int> > intSet;
intSet s1, s2, s3, s4;
for (int i=0; i<10; i++)
{ s1.insert(i);
s2.insert(i+4);
}
for (int i=0; i<5; i++) s3.insert(i);
cout << s1 = << s1 << endl;
cout << s2 = << s2 << endl;
cout << s3 = << s3 << endl;
// Is s1 a subset of s2?
bool test = includes(s2.begin(),s2.end(),s1.begin(),s1.end());
cout << s1 subset of s2 is << (test ? true. : false.) << endl;
// Is s3 a subset of s1?
test = includes(s1.begin(),s1.end(),s3.begin(),s3.end());
cout << s3 subset of s1 is << (test ? true. : false.) << endl;
// Form the union of s1 and s2.
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
insert_iterator<intSet>(s4,s4.begin()) );
cout << s1 union s2 = << s4 << endl;
// Erase s4 and form intersection of s1 and s2. (If we don't erase
// s4 then we will get the previous contents of s4 as well).
s4.erase(s4.begin(),s4.end());
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
insert_iterator<intSet>(s4,s4.begin()) );
cout << s1 intersection s2 = << s4 << endl;
// Now set difference.
s4.erase(s4.begin(),s4.end());
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
insert_iterator<intSet>(s4,s4.begin()) );
cout << s1 minus s2 = << s4 << endl;
// Set difference is not symmetric.
s4.erase(s4.begin(),s4.end());
set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(),
insert_iterator<intSet>(s4,s4.begin()) );
cout << s2 minus s1 = << s4 << endl;
// Finally symmetric difference.
s4.erase(s4.begin(),s4.end());
set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
insert_iterator<intSet>(s4,s4.begin()) );
cout << s1 symmetric_difference s2 = << s4 << endl;
// Which is symmetric!
s4.erase(s4.begin(),s4.end());
set_symmetric_difference(s2.begin(), s2.end(), s1.begin(), s1.end(),
insert_iterator<intSet>(s4,s4.begin()) );
cout << s2 symmetric_difference s1 = << s4 << endl;
}
See the section STL References
See the section STL References