Polymorphism

STL: Vector

Intro to the STL

The Standard Template Library, or STL, is a C++ library of container classes, algorithms, and iterators. It provides many basic algorithms and data structures that can be used generically. Almost every component in the STL is a template. If you are not comfortable with templates, please refer to the template lab. For more information about the STL, have a look at SGI's website.

A Look at Vectors

This lab gives you a first look at the vector collection in the Standard Template Library. The vector is basically just a dynamic array. The old C style dynamic array involved using malloc and free and had its problems. Vectors are much nicer to use. Vectors also have the distinction of being one of the more efficient containers in the STL. Since vector is a template, it is declared a bit different that a regular data type. Behold, a vector of ints:

#include <vector>                     //don't forget to include this header!

using namespace std;              //vector lives in std, just like cout, cin and many others

void main(void)
{
       vector <int> some_ints;
}

Puttin' Stuff In

Now that we have have a vector of ints, what do we do with it? Well, how about putting some ints into that vector!

#include <vector>

using namespace std;

void main(void)
{
vector <int> some_ints;

       some_ints.push_back(3);
       some_ints.push_back(5);
       some_ints.push_back(24);

}

Ok, now we have some values in our vector. Using the push_back method appends the value to the end of the vector and resizes it. We now have a vector with a size of 3 elements. The vector contains the values 3, 5, and 24 respectively. To extract those values try this:

#include <vector>
#include <iostream>

using namespace std;

void main(void)
{
       vector <int> some_ints;

       some_ints.push_back(3);
       some_ints.push_back(5);
       some_ints.push_back(24);

       cout << some_ints[0] << endl;

cout << some_ints[1] << endl;

cout << some_ints[2] << endl;

}

The values are accessed by getting the contents of an element in the vector, just like accessing values in an array. The output will be, of course, 3, 5 and 24. If you want to pass a variable to the vector, it is done the same way.

vector <int> some_ints;

int x = 5;

some_ints.push_back(x);

Since vector is a class, you may wonder what its constructor does. You can use the constructor to create a vector of any size and give each element a default value. The following code will create a vector with 30 elements (to start with, it is not static) and assign the value 5 to each element. If you do not pass a second value to the constructor, the default is 0.

vector <int> some_ints(30, 5); //create a vector with 30 elements, each element having the value 5

Takin' Stuff Out

You can add values to the vector, but it is often useful to remove values from the vector. There are a few ways to do this. If you need to remove ALL the values from the vector, simply call the clear method. This is the fastest method.

vector <int> some_ints(30, 5); //creates the vector

some_ints.clear(); //clears the contents of the vector

Obviously, this is not always the best way to get the job done. You might still want some values in the vector, right?! Luckily, there are other methods. The next fastest way is to remove values from back of the vector with the pop_back method (the reverse of push_back). Let's also look at a new method, size(). size() simply returns the number of elements in the vector.

vector <int> some_ints;

some_ints.push_back(3);
some_ints.push_back(5);
some_ints.push_back(24);

for(i = 0; i < some_ints.size(); i++) //this will loop three times, our vector has three elements
cout << some_ints[i] << endl;

some_ints.pop_back(); //removes the last element, in this case element 3 containing value 24

for(i = 0; i < some_ints.size(); i++) //now this will only loop two times
cout << some_ints[i] << endl;

The output will be 3, 5, 24, then pop_back() is called and the output is 3 and 5. pop_back() is useful, but many times you will need to remove an element somewhere in the middle of the vector. That brings us to the final, and slowest, method for doing elements in a vector, the erase() method. Here it is in action.

vector <int> some_ints;

some_ints.push_back(3);
some_ints.push_back(5);
some_ints.push_back(24);

for(i = 0; i < some_ints.size(); i++) //this will loop three times, our vector has three elements
cout << some_ints[i] << endl;

some_ints.erase(&some_ints[1]); //removes the second element containing value 5

for(i = 0; i < some_ints.size(); i++) //now this will only loop two times
cout << some_ints[i] << endl;

The output will be 3, 5, 24, then erase is called on element 1 (the second element) and the value 5 is removed from the vector. The final output is 3 and 24.

More Fun With Vector

Vector is really nice because it can hold any data type, even one of your own. For example, you may have a class called Card declared somewhere. You could create a vector that holds 52 Cards like this.

vector <Card> some_cards(52); //creates a vector of 52 Cards

52 "Card"s are created (using the default constructor of Card) and added to the vector. To add more cards, just use the push_back( ) method and pass the constructor of the class. Like this:

vector <Card> some_cards;

some_cards.push_back(Card( ));

Now that you have a basic understanding of the vector class, use it for all your dynamic array needs.