C++, STL basics

STL basics

This is my first tutorial, and English isn't my first language, so bear with me. :)

For this tutorial, it is assumed that you already know the basics of C++. You've written one or two small programs, tried to write or use a class, and you have been working with arrays/strings. Possibly you have survived your first core dump or access violation too. Or maybe you already know some STL, and are looking for new tricks.

The STL (Standard Template Library) provides some container classes and functions to manipulate them. Very basic things that you will need every time: strings, arrays, search functions... And yes, libraries like the MFC already have wonderful string classes, but it's hard to use them if you compile your programs with Borland or Gnu C++. One of the merits of the STL is that it is supported by virtually all modern compilers. Maybe MS Visual C++ 5 could stumble over some of the examples.

But before we start...
Everything in the STL resides in the "std" namespace. There are three ways of dealing with this:

Code:

using namespace std;

This statement hoists the entire std namespace into the global namespace, so it works just like ordinary classes and functions would. In other words, it pretends like the std namespace doesn't exist at all, which kind of defeats the whole purpose of having them in the first place. This is okay for a quick hack.

Code:

using std::string;

With this statement, you are telling the compiler that you are using 'string' from the std namespace. You can put it at the top of your file, or inside a function.

Finally, you can write 'std::string' explicitly.

In the examples, I will use all three methods, so you can see what they look like in code. Pick one you like.

The container classes

Strings
The workhorse of almost any program is the string class. You can store and manipulate bits of text in it. 'std::string' does initialisation, concatenation, and printing to streams in an intuitive way:

Code:

#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;

int main (int argc, char **argv)
{
    string message1 ("The first message");
    string message2;

    message2 = "The second";
    message2 += " message";

    cout << message1 << endl 
         << message2 << endl;
}

Vectors
Vectors are souped-up arrays. Probably you already know how to use an array of integers in C++:

Code:

int my_integers[100];
int index;

// First we put something in the array.
for (index = 0; index < 100; ++index)
{
    my_integers[index] = index;
}

// Then we print the array's contents to the screen.
for (index = 0; index < 100; ++index)
{
    std::cout << my_integers[index] << std::endl;
}

If you suddenly need more than 100 elements at runtime, you're in trouble. You can use new and delete to allocate bigger arrays, or you can switch to std::vector and let the STL sort out the hairy details:

Code:

#include <vector>

// ...

std::vector<int> my_integers;
int index;

for (index = 0; index < 100; ++index)
{
    my_integers.push_back (index);
}

for (index = 0; index < 100; ++index)
{
    std::cout << my_integers[index] << std::endl;
}

Note that you need to specify what kind of elements you want to use in your vector between pointy brackets, in this case an integer. This is a so-called template parameter. For now, just remember that you can tell std::vector what type it will contain this way -- templates are a complex subject that could take up a good handful of tutorials all by themselves.

Also note that we use 'push_back' here to insert new elements at the back. The vector will grow along as needed. This is a feature of the push_back member function: just like with an ordinary array, you cannot ask for 'my_integers[345]' and hope it will grow to the right size. If you do need 346 elements right away, you can tell std::vector so at the constructor:

Code:

std::vector<int> my_vector (346);

my_vector[345] = 42;

Or maybe you decide somewhere halfway your program that your vector should be at least 346 elements big:

Code:

if (my_vector.size() < 346)  // Is it too small?
{
    my_vector.resize (346);  // Then make it big enough.
}

my_vector[345] = 42;

And now for a pleasant surprise: everything you learned about vectors also works for strings:

Code:

std::string test ("fooxar");
test[3] = 'b';
std::cout << test << " is " << test.size() << " characters long." << std::endl;

Iterators
In the previous examples, we used the trusty old for-loop construct to print all elements of a vector. Another way to accomplish this is the use of iterators. You can think of an iterator as a pointer to one of the elements in your vector or string.

std::string and std::vector both define an iterator type within their own class. So, you'll need yet another '::' to access it:

Code:

std::vector<int> my_vector;
std::vector<int>::iterator my_iterator;

The iterator isn't pointing anywhere yet. All containers in the STL have two member functions 'begin' and 'end' that return an iterator to -- you guessed it -- the beginning and the end of that container. Let's use these functions to print all the elements in 'my_vector':

Code:

using namespace std;

vector<int>::iterator vec_iterator;

vec_iterator = my_vector.begin();

// Keep going while the end isn't reached.
while (vec_iterator != my_vector.end())
{
    // Print the element that vec_iterator is pointing at.
    cout << *vec_iterator << endl;
    
    // Move the iterator to the next element.
    ++vec_iterator;
}

A word of warning: my_vector.end() does not return an iterator that points to an actual element, and it is not NULL either. It points right after the last element of my_vector.

You might be thinking, "why not use a for loop and index it with [ ]? It's shorter and more readable". Yes, that is true. However, not every STL container supports the indexing operator [ ]. Suppose that one day you decide std::vector just doesn't cut it, and you need a std::list. If you use iterators consistently, you can just drop in a list and compile.

List?
Yes, there is also a thing called std::list. Everything you learned here about vectors also works for lists, except the indexing operator. Which means lists are not very useful at the moment. Lists do become important once the speed of your application becomes an issue. So, keep 'em in the back of your head, and use vectors in the meantime.

Algorithms
Lots of things that you would like to do with your containers, can be done with algorithms: searching, sorting, looping, copying, just to name a few things.

Loops
Let's start with loops. We have already printed the contents of a vector using a for loop and using iterators in a while loop, but there are more ways. Enter std::for_each ...

Code:

#include <iostream>
#include <vector>
#include <algorithm>

void show (int number)
{
    std::cout << number << std::endl;
}

int main (int argc, char** argv)
{
    std::vector<int> my_vector;
    
    my_vector.push_back (2);
    my_vector.push_back (3);
    my_vector.push_back (5);
    
    std::for_each (my_vector.begin(), my_vector.end(), show);

    return 0;
}

Instead of hand-crafting your own while-loop, you can let std::for_each call show() with every element in my_vector. This little program will produce the numbers 2, 3, and 5 as its output.

Searching
An example of searching: we'll look for the number six in my_vector, using the function
std::find. It takes two iterators (a start and an end point) and a value to look for. It returns an iterator to the found element, or if it wasn't there, to the end.

Code:

std::vector<int>::iterator found;

found = std::find (my_vector.begin(), my_vector.end(), 6);

if (found == my_vector.end())
{
    std::cout << "The number six was not found." << std::endl;
}
else
{
    // We can safely dereference the iterator (using the asterix: *found),
    // because we already checked if it isn't pointing to the end.
    //
    std::cout << "Look mom I found sumthin': " << *found << std::endl;
}

Copying
The function std::copy, well, copies everything between one range of iterators into another iterator. Say, the first ten elements of my_vector to the beginning of another_vector:

Code:

std::vector<int> another_vector (10);

std::copy (my_vector.begin(), my_vector.begin() + 10, another_vector.begin());

It would be more interesting if we didn't have to change that first '10' to some other number if we want to copy more or less elements. Any mistakes there are rewarded with a spectacular runtime error. The STL has some adapters that turn classes into iterators with a special property. The one we are looking for here is std::back_inserter -- everything that is put into this iterator, is added to the back of some other container using 'push_back'. This is particulary useful in cases you want to add elements to an already filled vector, or you don't know how many elements you are going to copy. In the following example, the contents of my_vector are copied into another_vector, from the beginning to the first occurrence of the number 42. In case my_vector doesn't contain 42, std::find returns my_vector.end() and the whole container is copied:

Code:

std::vector<int> another_vector;

std::copy (my_vector.begin(), 
           std::find (my_vector.begin(), my_vector.end(), 42),
           std::back_inserter (another_vector));

There are more useful adapters besides back_inserter. One is std::ostream_iterator, which does something similar, but to a stream instead of a container. By wrapping one of these around std::cout, we have yet another way of printing a list of numbers to the screen:

Code:

std::copy (my_vector.begin(), my_vector.end(), 
           std::ostream_iterator<int> (std::cout, "\n");

As you can see, we must tell std::ostream_iterator what kind of elements it is handling with a template parameter. The first argument is an output stream. Here we are using cout, but you can also write it to a file stream if you like. The second argument of ostream_iterator is something that will be streamed to cout after each element of my_vector. In this case, it's a newline, but you could also put a space there, or your favourite poem.

Sorting
Using the std::sort function should be easy, now that you already know how to search and copy things. You specify a range of elements, and they are sorted. No sweat. Since it's such a boring function, let's spice up the example code with some other concepts from this tutorial. This piece of code will allow the user to enter a few words (stop with ctrl-D on Unix-ish environments, or ctrl-Z on Windows), and it will show the words again in alphabetical order.

Code:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

int main (int argc, char** argv)
{
    // This vector of strings will be holding the words as the user
    // enters them.
    vector<string> words;
    
    // std::ostream_iterator's evil twin, std::istream_iterator, can
    // be used for doing the opposite: turn an input stream into an
    // iterator. Here we keep copy all strings from cin to the back of
    // the words vector:
    copy (istream_iterator<string> (cin), 
          istream_iterator<string> (),    // "end"
          back_inserter (words));
    
    // Sort them alphabetically.
    sort (words.begin(), words.end());

    // We draw a line and copy the sorted words vector to cout.
    cout << "-----------------------------------" << endl;
    copy (words.begin(), words.end(), 
          ostream_iterator<string> (cout, "\n"));

    return 0;
}

Fooling around
This tutorial is quite long, and is probably too much to grasp all at once. The best way to get the hang of the STL, is taking the last example, and play around with it. Change the strings to something else, like integers or floats. Maybe use file streams instead of cin and cout. What happens if you sort one string instead of a vector of strings?

For the adventurous, there's also the reverse_iterator, and the member functions rbegin() and rend(). Can you guess what happens if you sort (words.rbegin(), words.rend())? Or if you use copy() and find() with reverse iterators?

(printer friendly format)

	Page 1 of 1