© by Charles Lin. All rights reserved. You must receive written permission from Charles Lin to reproduce this webpage in any form.

Many of you have never seen templates before. Those of you who took the AP exam may have, since some simple version of templates are now assumed for the exam.

Fortunately, you don't have to understand templates very well to use them, and that's one of the goals of the first project: to use templates.

In particular, we're going to use an STL vector. STL stands for "Standard Template Library". The idea for this library is probably about 10 years old. It was incorporated into the C++ standard in 1998.

The goal was to produce container classes to store a bunch of objects of similar types. You've seen some already. Whenever you make an array of objects, you are, effectively, creating a container of such objects.

However, arrays are rather rigid. If you want to resize the array, you have to do dynamic allocation, and while the code isn't difficult, you still have to write code.

STL gives you classes that can hold objects of any type. All you have to do is figure out what operations you want, and how efficient you want those operations to be, and find the appropriate container class.

A vector is basically a dynamic array, which can be resized as needed. Let's look at some basics of vectors.

Declaring vectors

#include <vector>
#include <string>
int main()
{
  vector<int>    list1;
  vector<string> list2;
  vector<Foo>    list3;
  vector<Foo *>  list4;
}

list1 is a vector of int's. list2 is a vector of string's. list3 is a vector of Foo's. list4 is a vector of Foo pointers. As you can see, you can pretty much store anything.

I really shouldn't say anything because it is useful to have a few operations in the class, if they are to be used in vectors:

• default constructor
• copy constructor
• assignment operator

When you declare a vector, initially the size of the vector is 0. That means, it can store no elements at all. There are two ways to store elements. First, you can specify the size of the vector, when declaring it.

#include <vector>
#include <string>
int main()
{
  vector<Foo>    list1( 5 );
}

Using push_back

For example,

#include <vector>
#include <string>
int main()
{
  string s1 = "cat", s2 = "dog";
  vector<string>   list1;

  list1.push_back( s1 );
  // prints 1, since size is 1
  cout << list1.size() << endl;

  list1.push_back( s2 );
  // prints 2, since size is 2
  cout << list1.size() << endl;
}

Using resize

#include <vector>
#include <string>
int main()
{
  string s1 = "cat", s2 = "dog";
  vector<string>   list1;

  list1.resize( 5 );
  list1.resize( 10, s2 );
}

If you use two arguments, then the second argument will be an instance of the class, and each new element constructed will be a copy of this instance.

If the argument, size, is smaller than the actual size of the vector, then the vector simply decreases in size.

Making a vector smaller

  vector<string>   list1( 5 );

  list1.pop_back();
  // prints 4
  cout << list1.size() << endl;
}

Random access

  vector<string>   list1( 5 );

  int size = static_cast<int>( list1.size() );
  for ( int i = 0; i < size; i++ )
    {
      cout << list1[ i ] << endl;
    }
}

However, this makes iterating through a vector something of a pain. Most programmers prefer to use variables of type int to loop through an array. In order to do this successfully, you need to use a static cast, to convert the unsigned int size, to a signed int size. See the example above.

If you don't do this, more than likely, the compiler will produce a lot of error messages.

Sorting

• bool operator<( const Obj &other ) const;
• bool operator==( const Obj &other ) const;

For example,

#include <vector>
#include <algorithm>
int main()
{
  vector<Foo>   list( 5 );

  sort( list.begin(), list.end() );
}

The vector will be sorted in ascending order. To sort in descending order, you sort in ascending order, then call

  reverse( list.begin(), list.end() );

There is one more unusual aspect of sorting. You can sort part of a vector if you want. To do so, you have to indicate which index to begin sorting and which index to end. We won't look at this kind of sorting now. since it's typical to sort the entire vector.

To sort the entire vector, you must pass the name of the vector with .begin() at the end as the first argument, then the name of the vector with .end().

thus,

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