I have been playing with the Standard Template Library (which I will refer to as "STL" from now on, rather than "the STL") and am making some notes now for my own benefit, and any other C++ programmers that are interested in using STL in their programs.
What is STL?
STL is a collection of useful algorithms which are implemented using the C++ "template" mechanism, which allows you to use them for virtually any "type" of data.
Containers
A fair bit of STL is based around the idea of containers - groups of related things - for examples lists, vectors, queues and so on. STL is designed to be consistent in its interface so that once you are used to one container you can pretty-much use them all.
Iterators
STL relies heavily on "iterators" which I will explain in a minute. Basically you use iterators to access elements in a container.
Elements
Containers contain things, which since STL uses templates, can be virtually any C++ type (eg. integer, string, pointer).
Algorithms
STL provides a whole lot of useful algorithms, like sort, merge, generate, find, replace and so on. Generally speaking the algorithms work with iterators, and can be applied to virtually any container. However some algorithms (like sort) need certain types of containers (in this case, one that can be randomly accessed).
Example 1
First, let's illustrate the idea of containers with some straight C++ ...
Output
This example shows an ordinary array as a container of numbers, and the iterator "i" (which is a pointer).
The important thing about the iterator is that you can increment it to move to the next element, and dereference it (*i) to get the element's contents.
Now let's do that the STL way ...
Example 2
Output
You are probably thinking the straight C way was easier, but the example is really to illustrate the concepts of iterators and containers.
Also, it shows how using STL adding 1 to an iterator moves onto the next element, however in a more general way. If that example was changed so that the vector became a list, or a queue, it would still work exactly the same way.
To simplify things, we can copy from a C array into a vector, using the "copy" algorithm, thus saving a bit of effort ...
Example 3
Output
This example illustrates using "copy" to copy from one container to another. In this case the C array can be used as a container, and the vector as a second container. The "back_inserter" is needed to add elements to the end of the vector, otherwise the copy would copy beyond the end of the vector, and the program would crash.
The second "copy" uses an ostream_iterator (an output stream iterator) to copy to cout, thus simplifying displaying all the values.
Example 4
Output
This example illustrates using a user-written function to generate a range of numbers, and then randomly shuffle it with the STL random_shuffle algorithm.
I found the "srand" line made the numbers come out differently each time, without it they were always the same. However on Linux (Red Hat Linux 9) I needed the srand48 instead.
What is STL?
STL is a collection of useful algorithms which are implemented using the C++ "template" mechanism, which allows you to use them for virtually any "type" of data.
Containers
A fair bit of STL is based around the idea of containers - groups of related things - for examples lists, vectors, queues and so on. STL is designed to be consistent in its interface so that once you are used to one container you can pretty-much use them all.
Iterators
STL relies heavily on "iterators" which I will explain in a minute. Basically you use iterators to access elements in a container.
Elements
Containers contain things, which since STL uses templates, can be virtually any C++ type (eg. integer, string, pointer).
Algorithms
STL provides a whole lot of useful algorithms, like sort, merge, generate, find, replace and so on. Generally speaking the algorithms work with iterators, and can be applied to virtually any container. However some algorithms (like sort) need certain types of containers (in this case, one that can be randomly accessed).
Example 1
First, let's illustrate the idea of containers with some straight C++ ...
#include <iostream>
using namespace std;
int main (void)
{
// container
int v [] = { 22, 33, 66, 102 };
// iterator
int * i;
i = v; // iterator is at start
cout << *i << endl; // display one element
++i; // move to next element
cout << *i << endl; // display one element
return 0;
} // end of main
Output
22
33
This example shows an ordinary array as a container of numbers, and the iterator "i" (which is a pointer).
The important thing about the iterator is that you can increment it to move to the next element, and dereference it (*i) to get the element's contents.
Now let's do that the STL way ...
Example 2
#include <iostream>
#include <vector>
using namespace std;
int main (void)
{
// container
vector<int> v;
// add elements to the container
v.push_back (22);
v.push_back (33);
v.push_back (66);
v.push_back (102);
// iterator
vector<int>::iterator i;
i = v.begin (); // iterator is at start
cout << *i << endl; // display one element
++i; // move to next element
cout << *i << endl; // display one element
return 0;
} // end of main
Output
22
33
You are probably thinking the straight C way was easier, but the example is really to illustrate the concepts of iterators and containers.
Also, it shows how using STL adding 1 to an iterator moves onto the next element, however in a more general way. If that example was changed so that the vector became a list, or a queue, it would still work exactly the same way.
To simplify things, we can copy from a C array into a vector, using the "copy" algorithm, thus saving a bit of effort ...
Example 3
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
#define NUMITEMS(x) (sizeof(x) / sizeof(x[0]))
int main (void)
{
// C container
int v1 [] = { 22, 33, 66, 102 };
// STL container
vector<int> v;
// add elements to the container
copy (v1, &v1 [ NUMITEMS (v1) ], back_inserter (v));
// iterator
copy (v.begin (), v.end (), ostream_iterator<int> (cout, " "));
cout << endl; // end of line
return 0;
} // end of main
Output
22 33 66 102
This example illustrates using "copy" to copy from one container to another. In this case the C array can be used as a container, and the vector as a second container. The "back_inserter" is needed to add elements to the end of the vector, otherwise the copy would copy beyond the end of the vector, and the program would crash.
The second "copy" uses an ostream_iterator (an output stream iterator) to copy to cout, thus simplifying displaying all the values.
Example 4
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
template <class ForwardIterator>
void increment_fill (ForwardIterator first, int n)
{
int value = 0;
for (int i = 0; i < n; i++)
*first++ = value++;
};
int main (void)
{
// STL container
vector<int> v;
increment_fill (back_inserter (v), 100);
srand(time(NULL));
// srand48(time(NULL)); // use on Linux
// shuffle them
random_shuffle (v.begin (), v.end ());
// display results
copy (v.begin (), v.end (), ostream_iterator<int> (cout, " "));
cout << endl; // end of line
return 0;
} // end of main
Output
4 19 57 41 36 30 27 87 18 24 66 16 34 69 83 23 97 55 91 15 33 1 31 3 98 2 37 95
90 49 32 48 52 54 96 59 10 8 70 42 71 38 5 94 25 72 84 89 39 73 64 11 12 40 45 92
85 78 86 62 99 79 67 53 46 7 6 56 77 74 75 35 88 26 93 17 14 82 0 58 65 29 28
63 43 9 60 47 13 51 80 50 61 76 22 81 68 20 21 44
This example illustrates using a user-written function to generate a range of numbers, and then randomly shuffle it with the STL random_shuffle algorithm.
I found the "srand" line made the numbers come out differently each time, without it they were always the same. However on Linux (Red Hat Linux 9) I needed the srand48 instead.