STL 101 Part A - Vector

Introduction

The idea behind this series of articles is to introduce the standard template library, a library of interconnected containers and algorithms that is part of the C++ standard library. The other major part is IOStreams, which will also get a look in from time to time. My goal is to show that not only are these containers standard C++, they are also superior to the MFC equivalents in many respects. The MFC container classes were actually provided because the STL was not part of the standard at the time. However, Microsoft were also unable to upgrade their STL implementation prior to VC .NET for legal reasons, which meant they were hamstrung with an STL that was less than optimal. I recommend installing STLPort as a replacement if you’re on VC++ 6 or earlier. However, where I use code that will not compile without STLPort, I promise I try to remember to tell you.

For this first article I will seek to introduce you to std::vector, which is by far the most commonly used container. It is roughly equivalent to CArray, in that it provides a wrapper for an array. This means that insertions are expensive, and lookups are cheap. I’ll cover std::list, relative efficiency and different types of iterators in the second installment. I do not intend to cover templates, if you don’t know what this does: MyClass<int> MyIntClass; then I’d suggest you read some of the other introductory STL articles on CodeProject before you continue.

Before I start on the actual code I want to point out a few things. First of all, I have included ctime instead of time.h. Most people know to include iostream instead of iostream.h, which is deprecated, but I don’t often see people using the new versions of the C headers, which have a C in front of them as well as dropping the .h. Using the new headers is important, not least because they populate the std namespace instead of the global one. Which brings me to the second point. I do not use namespace std, I use only the functions I need from it. This is because if I put ‘

using namespace
std;

’, I pollute the global namespace with ALL of namespace std, which defeats the purpose of having it. I'm posting the entire code here, rather than provide a zip file. To use it, you just need to create a console application ( hello world will be fine ), and then replace all the code in the main.cpp file with the following:

#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <vector>
#include <algorithm>
#include <functional>

using std::cout;
using std::vector;
using std::endl;
using std::sort;
using std::partition;
using std::less;
using std::bind2nd;
using std::ostream_iterator;
using std::copy;
using std::back_inserter;


int main(int argc, char* argv[])
{
    // Seed random number generator

    srand(time(NULL));

    vector <int> vecInt;

    // declaring it here once will compile under dodgy VC, and also 
    // standards conforming compilers, VC included if you set a flag.
    int i;

    cout << "Inserting values into vector\n\n";

    for (i = 0; i <= 20; ++i)
    {
        vecInt.push_back(rand() % 200);
        cout << vecInt.at(i) << ", ";
    }

    cout << "\n\nIterating through vector and doubling values" << endl;

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

    for (it = vecInt.begin(); it != vecInt.end(); ++it)
    {
        *it *= 2;
        cout << *it << ", ";
    }

    cout << "\n\nPartitioning values under 200\n";

    std::vector<int>::iterator itBelow200 = partition(vecInt.begin(),
                                                            vecInt.end(), 
                                                            bind2nd(less<int>(), 200));

    copy (vecInt.begin(), vecInt.end(), ostream_iterator<int>(cout, ", "));

    cout << "\n\nCopying values below 200 to new vector\n";

    vector<int> vecInt2;

    copy(vecInt.begin(), itBelow200, back_inserter(vecInt2));

    copy (vecInt2.begin(), vecInt2.end(), ostream_iterator<int>(cout, ", "));

    cout << "\n\nSorting the first vector and output the result\n";

    sort(vecInt.begin(), vecInt.end());

    copy (vecInt.begin(), vecInt.end(), ostream_iterator<int>(cout, ", "));

    cout << endl;

    return 0;
}

Anyhow, the first thing you’ll notice is that a vector is a templated class, as any generic container must be. The syntax for adding an element is vector::push_back(element). To remove an element we can use vector::pop_back, which returns the element. You’ll notice that we use the member function at() to reference each item and send it to cout. In truth, it would be more efficient to have a tempory which we use to store the int and print it, but the example is written to instruct, not to be optimised. You can also use the [ ] operators to access an element, but at() is bounds checked. In truth, the bounds check will ASSERT if it fails, so the net result is probably not all that dissimilar.

The next thing to notice is that we create an iterator for our vector type. An iterator is somewhat like a POSITION in CList, except iterators work with all STL containers, in fact this is how the process of stepping through a container is made generic, which allows algorithms to be written to work with (nearly) all containers. Part 2 will explain the nearly bit.... We can get an iterator which equates to the start of a container using the begin() function, and one which equates to the position one past the end with the

end() 

function. Why one past ? So that we can create a loop to go through the container, it's in line with the idea of zero indexing generally. This is not the best way of doubling the values in the vector, I've done it this way purely to show you one way of stepping through a container. As you can see, dereferencing the iterator gives us a reference to the underlying value ( so if we change it, the value in the vector is changed ). This can lead to trouble if you have a container of pointers, I'll cover that issue in depth later also.

The point of using the standard containers is not so much the containers themselves, it's more that the come with a rich library of functions which can be used on them. They are declared in <algorithm> and <numeric>. We are going to use the partition algorithm, because it gives me a chance to show off a couple of other things as well. The partition algorithm allows you to set a rule, and everything that conforms will be moved to the leftmost half of the container ( but not sorted ) stable_partition will do this as well, but will also guarantee that the order of items on each half will be preserved. As we filled the vector with ints under 200 and then doubled them all, I'm going to partition so that numbers less than 200 which is hopefully roughly half of them ) are all moved to the front. This function returns an iterator which represents the position of the last item that has been partitioned.

A quick word about this - because a vector is an array, some functions such as insertion make it possible that the entire vector has had to be rebuilt elsewhere in memory. This means you should be on the lookout for such eventualities and realise that when they occur, it is possible that any iterators you are storing have become invalid. Also, if a partition action finds that all items match, it will return the end() iterator. Dereferencing this iterator is an invalid operation, so it is a case that should be checked for first.

The syntax for partition takes two iterators to define a range to work with, as pretty much all STL algorithms do. The last parameter is a little more confusing at first. less <int> is a templated binary function, which means it takes two arguments, and in this case, it means it returns true if the first is less than the second. It is defined in <functional>, as is bind2nd, which converts a binary function into a unary one ( one which takes one argument ), by taking as it's first parameter the function, and as it's second the value to 'bind' to the second parameter every time it is called. This means we are going to step through the vector, and for each value call less<int> to see if the value is less than 200.

The next line is also very cool. We use the copy algorithm to copy the entire vector, but we copy it to cout. This piece of magic is performed with an ostream_iterator, which, as the name implies is an iterator satisfying the requirements of the algorithm ), but it pipes the things written to it to an osteam, in this case cout. The second parameter is a delimiter, which is output between each item passed in. The net result is that this one line prints our entire vector to the console, and could as easily output it to a file, or any other ostream we might choose to write for ourselves.

Next we create a new vector and use the return value of partition to fill it with only the values below 200, which we then output also. Finally we do a full sort of the first vector and output that.

The point of this article has been to introduce vector, iterators, some common algorithms and some common functors and adaptors. Don't worry if parts of this don't make as much sense as you'd like, they will all be more fully covered in a future installment.