Click here to Skip to main content
Click here to Skip to main content
Go to top

STL 101 Part A - Vector

, 20 Feb 2002
Rate this:
Please Sign up or sign in to vote.
The first in a series of articles on STL, this one covers vector and some common algorithms

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Christian Graus
Software Developer (Senior)
Australia Australia
Programming computers ( self taught ) since about 1984 when I bought my first Apple ][. Was working on a GUI library to interface Win32 to Python, and writing graphics filters in my spare time, and then building n-tiered apps using asp, atl and asp.net in my job at Dytech. After 4 years there, I've started working from home, at first for Code Project and now for a vet telemedicine company. I owned part of a company that sells client education software in the vet market, but we sold that and I worked for the owners for five years before leaving to get away from the travel, and spend more time with my family. I now work for a company here in Hobart, doing all sorts of Microsoft based stuff in C++ and C#, with a lot of T-SQL in the mix.

Comments and Discussions

 
GeneralTo avoid compilation error on Linux, include 'iterator' header file PinmemberKim Moung Soo30-Jul-07 16:46 
Questionpush_back function code Pinmembertyrgftyhgr13-Jan-07 5:58 
AnswerRe: push_back function code PinmemberSceptic Mole13-Jan-07 6:53 
AnswerRe: push_back function code PinstaffChristian Graus13-Jan-07 11:58 
Generalgood Pinmemberwanghaitaoer23-Aug-06 5:35 
GeneralGive my 5 point PinmemberZhifang Zhao5-Nov-03 19:34 
GeneralThanks CG PinmemberNish [BusterBoy]12-Mar-02 1:16 
GeneralRe: Thanks CG PinmemberChristian Graus12-Mar-02 1:13 
GeneralRe: Thanks CG PinmemberNish [BusterBoy]12-Mar-02 1:21 
GeneralRe: Thanks CG PinmemberChristian Graus12-Mar-02 1:26 
GeneralRe: See the light Nish PinmemberTim Smith12-Mar-02 2:14 
GeneralGeneric design vs. OO design.. PinmemberStan Shannon22-Feb-02 3:09 
GeneralRe: Generic design vs. OO design.. PinmemberWilliam E. Kempf22-Feb-02 9:12 
GeneralRe: Generic design vs. OO design.. PinmemberChristian Graus22-Feb-02 9:46 
Generalusing directive PinmemberNemanja Trifunovic21-Feb-02 12:01 
GeneralRe: using directive PinmemberChristian Graus21-Feb-02 12:10 
Generala typo, CG PinmemberNish [BusterBoy]21-Feb-02 10:02 
GeneralRe: a typo, CG PinmemberChristian Graus21-Feb-02 10:11 
GeneralRe: a typo, CG PinmemberNish [BusterBoy]21-Feb-02 10:54 
GeneralRe: a typo, CG PinmemberChristian Graus21-Feb-02 10:54 
GeneralKeep the good work. PinmemberRamon Casellas21-Feb-02 2:22 
GeneralRe: Keep the good work. PinmemberTim Smith21-Feb-02 4:05 
GeneralRe: Keep the good work. PinmemberTodd Smith21-Feb-02 8:56 
GeneralRe: Keep the good work. PinmemberTim Smith21-Feb-02 10:50 
GeneralRe: Keep the good work. PinmemberTodd Smith21-Feb-02 11:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140916.1 | Last Updated 21 Feb 2002
Article Copyright 2002 by Christian Graus
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid