CUED Talk: C++ and the STL (Standard Template Library)
Contents
C++ was designed to support object-orientated programming.
It also supports "polymorphism", allowing
routines to be written without needing to worry at a high level about the
type of the data, thus allowing "generic" programming. This is useful,
not least because it is often as
easy to write a general (and reusable) solution to a problem as it is
to tackle a particular case.
However, this support hasn't always been easy to use.
Templates (which were introduced into C++ in 1989) helped.
In 1995 the Standard
Template Library (STL) was developed, which uses templates to
provide users with easy access to powerful generic routines. The STL is now
part of the C++ Standard. With it programmers can express concepts in a more
natural way, and at a higher level of abstraction, without losing the
efficiency and power of C.
Furthermore, by reducing the need for loops and the
"switch" keyword the STL helps make code more sequential, so
that it's simpler as well as more powerful.
In C, user-defined data types can be created using "typedef" and
"struct". In Pascal, the RECORD mechanism does a similar thing.
C++'s class mechanism is an extention of this, providing extra
features that allow data plus associated functions to be encapsulated
into objects.
C++'s Templates are parameterized types. They support generic programming
by obviating the need for explicit switch statements to deal with
various data types.
Let's look at an example.
The following code swaps 2 integers in the usual C++ way
void swap (int& a, int& b) {
int tmp = a;
a = b;
b = tmp;
}
If you wanted to swap other types of variables (including those
you've defined) you could copy this code, replacing int
by (say) float. But in situations like this, where the
code is potentially generic, templates can be used.
template <class T>
void swap (T& a, T& b) {
T tmp = a;
a = b;
b = tmp;
}
Here the "T" name is arbitrary (like a formal parameter in a function
definition). Note that the function
is written much as before. When the compiler is now given the
following code
int a = 3, b = 5;
float f=7.5, g=9.5;
swap (a, b);
swap (f, g);
it will create a version ("instantiation") of swap for
each type required.
Templates help reduce the amount of code you need to write.
Imagine software components as a three-dimensional space. One dimension represents the data
types (int, double, char, ...), the second dimension represents the way these
types can be collected (array, linked-list, ...)
and the third dimension represents the algorithms (sort, merge, search, ...).
To deal with all cases in C would require i*j*k routines. Use of templates
collapses 1st dimension - the type doesn't matter. The Standard Template
Library (STL) reduces the number of routines further, providing algorithms that
can operate on various types of collections. Almost every component
in the STL is a template.
The STL consists of five main components, 3 of which we'll concentrate
on first
- Container: object that is able to keep and administer objects
- Algorithm: computational procedure that is able to work on different containers
- Iterator: abstraction of "pointer" or "index" - a means to access
the appropriate element.
The STL includes container classes:
classes whose purpose is to contain other objects. There are
classes for vectors, lists, etc. Each of
these classes is a template, and can be instantiated to contain any type of object. You can, for
example, use a vector<int> in much the same way as you would use an ordinary C array, except
that vector eliminates the chore of managing dynamic memory allocation by hand.
vector<int> v(3); // Declare a vector of 3 elements.
v[0] = 7;
v[1] = v[0] + 3;
v[2] = v[0] + v[1]; // v[0] == 7, v[1] == 10, v[2] == 17
The STL also includes a large collection of algorithms that manipulate the data stored in containers - reverse, insert,
unique, transform etc. Note that these operations
act on the elements without explicit use of loops.
A container can be treated as a single entity, but you
sometimes need a way to access individual items. Iterators are generalised
pointers. They are needed as arguments to the algorithms mentioned
above. For a container "v", v.begin() returns an
iterator pointing to the
first element and v.end() "points" to one beyond
the last, so
reverse(v.begin(), v.end());
would reverse the whole of the above vector.
It's possible to iterate through the values in much the way as one
would do in C.
void print(vector <int>&v)
{
for (vector<int>::iterator it = v.begin();
it != v.end();
it++)
cout << *it << " ";
cout << endl;
}
A file can have the properties necessary to be treated like a container
(it can be treated as a sequence of items of the same type),
so perhaps it's not too surprising that the following is another way
to print the integer elements of a vector.
copy (V.begin(),V.end(), ostream_iterator<int>(cout," "));
If you wanted you could stop reading at this point and use the ideas
so far presented to do sorting, finding, etc in your programs, introducing
these new ideas bit by bit until you feel comfortable with them. Even
simple uses offer great benefits and you can replace as much (or little)
of your old C-style C++ code as you want.
For the sake of completeness I'll mention the other 2 STL component types
now. They're used sometimes in the examples but don't worry about them;
you can get a long way without them.
- Function Object (or Functor): an object of a class that has the
function-call operator (operator() ) defined (e.g. "set")
- Adaptor: encapsulates a component to provide another
interface (e.g. make a stack out of a list, or make an existing class
look like an STL
collection)
The previous section became a little technical so let's first take a
very simple example to show how the mechanisms described above needn't be
visible to the user.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
s="hello";
s=s+" world";
cout << s << endl;
}
This uses string which is a sort of container. Note that the
string header file needs to be included. I think that this code
is as short and understandable as one could reasonably hope for. Note
that the string is "elastic" - it grows as required. Compare this code
with the old character-array method of C (though it's also legal in C++).
#include <iostream>
using namespace std;
int main()
{
char s[10];
strcpy(s,"hello");
strcat(s," world");
cout << s << endl;
}
This code does the same as the first fragment does but is less readable
and contains a bug - the s array is only big enough to contain
10 characters. So C++'s more recent features are not only easier
to use than the old methods, they're safer too!
The following examples demonstrate some further features. Some
of the details are dealt with in the
next section.
On the CUED Teaching System compile these using "aCC -AA".
- Create a stack of integers
#include <deque>
#include <stack>
#include <iostream>
using namespace std;
int main() {
stack<int> S;
S.push(1);
S.push(2);
S.push(3);
S.pop();
cout << "Top element is " << S.top()
<<endl;
S.pop();
S.pop();
cout << "Number of elements is now " <<
S.size() <<
endl;
};
- Create a stack of complex numbers that have integer components
#include <deque>
#include <stack>
#include <complex>
#include <iostream>
using namespace std;
int main() {
stack<complex<int> > S;
// the space between the '>' signs matters
complex<int> a(1,2), b(4,7);
S.push(a);
S.push(b);
S.push(a);
S.pop();
cout << "Top element is " <<S.top()<<endl;
S.pop();
S.pop();
cout <<"Number of elements is now "<<S.size()
<<endl;
cout << "Stack empty? (1 means yes) " <<
S.empty() <<
endl;
};
- Create a vector of integers. Copy it into a list, reversing as you do so, then
copy selected items into another vector
(adapted from
Silicon Graphics)
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
vector<int> V;
V.push_back(0);
V.push_back(1);
V.push_back(2);
copy(V.begin(), V.end(), ostream_iterator<int>
(cout, " "));
// Output: 0 1 2
cout <<endl;
list<int> L(V.size());
reverse_copy(V.begin(), V.end(), L.begin());
copy(L.begin(), L.end(), ostream_iterator<int>
(cout, " "));
// Output: 2 1 0
cout <<endl;
vector<int> V2;
//copy the elements from V that are not <1 into V2
remove_copy_if(V.begin(), V.end(), back_inserter(V2),
bind2nd(less<int>(), 1));
copy(V2.begin(), V2.end(), ostream_iterator<int>
(cout, " "));
cout <<endl;
exit(0);
}
- Create a Boolean vector of bits. Flip the values
- Create a vector. Use count_if, remove_if and sort on it
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
int main()
{
int sum=0;
vector<int> V;
V.push_back(1);
V.push_back(4);
V.push_back(2);
V.push_back(8);
V.push_back(5);
V.push_back(7);
copy(V.begin(), V.end(), ostream_iterator<int>
(cout, " "));
count_if (V.begin(), V.end(), bind2nd(greater<
int>(),5),
sum);
cout << endl <<
"There are " << sum << "
number(s) greater than 5" << endl;
// "remove" all the elements less than 4
vector<int>::iterator new_end =
remove_if(V.begin(), V.end(), bind2nd(less<
int>(), 4));
// remove_if doesn't actually remove elements. It moves the unwanted
// elements to the end and returns an iterator pointing to the first
// of these unwanted elements. It works this way because
// it's a generic routine and it doesn't "know" whether the size of
// the underlying data structure can be changed.
// But V.erase "knows" about vectors.
V.erase(new_end, V.end());
copy(V.begin(), V.end(), ostream_iterator<int>
(cout, " "));
cout << endl <<
"Elements less than 4 removed" << endl;
sort(V.begin(), V.end());
copy(V.begin(), V.end(), ostream_iterator<int>
(cout, " "));
cout << endl << "Elements sorted" <<
endl;
}
- Create a routine to operate on all the elements
of a container.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int square(int i) { return i * i; }
int main()
{
vector<int> V;
V.push_back(0);
V.push_back(1);
V.push_back(2);
transform(V.begin(),V.end(), V.begin(), square);
copy(V.begin(),V.end(), ostream_iterator<int>
(cout, " "));
cout <<endl;
};
- Create a queue (adapted from
Silicon Graphics)
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
deque<int> Q; // pronounced "deck" - double-ended queue
Q.push_back(3);
Q.push_front(1);
Q.insert(Q.begin() + 1, 2);
Q[2] = 0;
copy(Q.begin(), Q.end(), ostream_iterator<int>
(cout, " "));
// The values that are printed are 1 2 0
cout <<endl;
exit(0);
}
- Sets - (adapted from
Silicon Graphics)
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
// define how the items are to be tested for equality
struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};
int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
const char* b[N] = {"flat", "this", "artichoke",
"frigate", "prosaic", "isomer"};
set<const char*, ltstr> A(a, a + N);
set<const char*, ltstr> B(b, b + N);
set<const char*, ltstr> C;
cout << "Set A: ";
copy(A.begin(), A.end(),
ostream_iterator<const char*>(cout, " "));
cout << endl;
cout << "Set B: ";
copy(B.begin(), B.end(),
ostream_iterator<const char*>(cout, " "));
cout << endl;
cout << "Union: ";
set_union(A.begin(), A.end(), B.begin(), B.end(),
ostream_iterator<const char*>(cout, " "),
ltstr());
cout << endl;
exit(0);
}
- Multimaps - This example of a look-up table uses
some non-trivial C++ to make the main routine simpler.
#include <string>
#include <map>
#include <iostream>
using namespace std;
typedef multimap <string, string, less<string> >
names_type;
// Print out a pair
template <class First, class Second>
ostream& operator<<(ostream& out,
const pair<First,Second>& p)
{
cout << p.first <<"belongs to the"<<
p.second << " family";
return out;
}
// Print out a multimap
ostream& operator<<(ostream& out, names_type l)
{
copy(l.begin(),l.end(), ostream_iterator
<names_type::value_type>(cout,"\n"));
return out;
}
int main(void)
{
// create a multimap of names
names_type names;
typedef names_type::value_type value_type;
// Put the names in the multimap
names.insert(value_type(string("Sue"), string("Smith")));
names.insert(value_type(string("Jane"), string("Smith")));
names.insert(value_type(string("Kay"), string("Smith")));
names.insert(value_type(string("Kurt"), string("Jones")));
names.insert(value_type(string("Sue"), string("Jones")));
names.insert(value_type(string("John"), string("Jones")));
names.insert(value_type(string("Sophie"), string("Mackay")));
names.insert(value_type(string("Steve"), string("Mackay")));
names.insert(value_type(string("Sue"), string("Mackay")));
// print out the names
cout << "All the names" << endl << names << endl;
// Find the people called Sue
pair<names_type::iterator,
names_type::iterator> p =
names.equal_range("Sue");
// print them out
cout << endl << "People called Sue" << endl;
copy(p.first,p.second,
ostream_iterator<value_type>(cout,"\n"));
return 0;
}
The examples gloss over a few details
- Note that end() returns an Iterator value that points past
the last element of the corresponding container. This value is called the
past-the-end value. This value is also returned if a find()
can't find a match. NULL isn't used.
- Because so many functions provided by the standard library take other
functions as arguments, the library includes classes that let you build new
function objects out of old ones. bind2nd takes as arguments
a binary function object and a value to be used as the 2nd argument of the function.
So "bind2nd(greater<int> (),3)" is true when an integer is
greater than 3. bind1st exists too.
For a list of alternatives to greater, see the
Function Objects page in the local documentation.
- Performance - you may be thinking that all this extra power must come
at the expense of speed, but one reason that templates were chosen for
the STL is that the resulting code should be fast. Indeed, the templated
version of the swap routine introduced at the start should generate
the same code as the hand-crafted version. However, compilers have to be
good to generate code that is both small and fast, and some ANSI C++ compilers
are rather raw.
Once you've mastered the programs above, you should be able to use
other components of the STL without too much trouble
- More containers - bit_vector, multiset, hash_set, hash_multiset,
hash_map, and hash_multimap
- More algorithms - for_each, random_shuffle, partial_sort , partition,
etc.
- More types of iterators.
Local users can start exploring from the locally installed
standard library documentation
contents page.
Because of the generic approach SL algorithms are able to work on
user-built containers and user-built algorithms can work on STL containers - if the user takes some
strict requirements for building the components into consideration.
|
LINUX