Section 4 - Using and Benchmarking vectors

2A.4.1 Using FHvector

Once we incorporate the header file FHvector.h into our project, we use it as we would any template. Here are a few simple tests.

// Test and demo of FHvector class template
// CS 2C, Foothill College, Michael Loceff, creator

#include <iostream>
#include <string>
using namespace std;

#include "FHvector.h"

// --------------- main ---------------
#define MAX_SIZE 100000

int main()
{
   int k;
   double avg;

   // use [] to write to a pre-allocated FHvector
   FHvector<int> vectorOf_FH_ints(MAX_SIZE);

   for (k = 0; k < MAX_SIZE; k++)
      vectorOf_FH_ints[k] = k;

   for (k = 0, avg = 0.; k < MAX_SIZE; k++)
      avg += vectorOf_FH_ints[k];
   avg /= MAX_SIZE;
   cout << endl << "The average is: " << avg << endl;
  
   // use push_back() to write to an initially empty FHvector
   FHvector<int> vectorOf_FH_ints2;

   for (k = 0; k < MAX_SIZE; k++)
      vectorOf_FH_ints2.push_back(k);

   for (k = 0, avg = 0.; k < MAX_SIZE; k++)
      avg += vectorOf_FH_ints[k];
   avg /= MAX_SIZE;
   cout << endl << "The average is: " << avg << endl;

   // chop off 50,000 items from the array:
   cout << endl << "Size before: " << vectorOf_FH_ints2.size() << endl;
   vectorOf_FH_ints2.resize(50000);
   cout << endl << "Size after: " << vectorOf_FH_ints2.size() << endl;

   // test front and back
   cout << endl << "First item: " << vectorOf_FH_ints2.front() << endl;
   cout << endl << "Last item: " << vectorOf_FH_ints2.back() << endl;

   // test pop_back() - should leave 30,000 elements in the vector
   for (k = 0; k < 20000; k++)
      vectorOf_FH_ints2.pop_back();
   cout << endl << "Last item after pop_backs: " << vectorOf_FH_ints2.back() << endl;

   // test range checking
   try
   {
      vectorOf_FH_ints2[0] = 27;
      vectorOf_FH_ints2[30001] = 27;
      vectorOf_FH_ints2[0] = -27;     // should never be reached
   }
   catch (FHvector<int>::OutOfBoundsException &e)
   {
      cout << "out-of-bounds detected \n";
   }
   cout << endl << "First item still 27? : " << vectorOf_FH_ints2.front() << endl;

   // test iterators
   FHvector<int>::iterator iter;
   for (iter = vectorOf_FH_ints2.begin(); iter != vectorOf_FH_ints2.end(); iter++)
   {
      if ( *iter % 5000 == 0)
         cout << *iter << endl;
   }

   cout << endl << "------------ end of FHvector test --------------- \n\n";

   return 0;
}

/* -------------------------- RUN --------------------------

The average is: 49999.5

The average is: 49999.5

Size before: 100000

Size after: 50000

First item: 0

Last item: 49999

Last item after pop_backs: 29999
out-of-bounds detected

First item still 27? : 27
5000
10000
15000
20000
25000

------------ end of FHvector test ---------------

Press any key to continue . . .
-------------------------- END RUN -------------------------- */

It works. That's comforting.

This example is very important for you to study because it shows:

How we declare (or "specialize") our template class, using common syntax
How we use iterators to hop through collections
How we use exceptions to guard against program aborts in case of bounds violations
How we use the FHvector functions (which are identical to their STL vector counterparts)

2A.4.2 Benchmarking FHvector

We've done benchmarking before, so this is not new. We just apply what we know to the new FHvector container, creating, then computing the average of 100,000 ints. We compare it with raw arrays and STL vectors, remembering that our [] operator incorporates all the protection of the at() function, making an at() function unnecessary for our FHvector template.

Here is the source and the run.

// Analysis of arrays vs. vectors using various access techniques
// CS 2C, Foothill College, Michael Loceff, creator

#include <iostream>
#include <string>
using namespace std;

#include <vector>
#include "FHvector.h"

// for timing our algorithms
#include <time.h>
clock_t startClock();
double computeElapsedTime(clock_t startTime);
void displaySeconds(string message, double time_in_secs);

// --------------- main ---------------
#define ARRAY_SIZE 200000

int main()
{
   int k;
   double avg;
   int arrayOfInts[ARRAY_SIZE];
   vector<int> vectorOfInts(ARRAY_SIZE);
   vector<int> vectorOfInts2;
   FHvector<int> vectorOf_FH_ints(ARRAY_SIZE);
   FHvector<int> vectorOf_FH_ints2;

   clock_t startTime; 
   double elapsedTime;

   startTime = startClock();   // simple array START TIME START TIME ----------
   for (k = 0; k < ARRAY_SIZE; k++)
      arrayOfInts[k] = rand()%100;

   for (k = 0, avg = 0.; k < ARRAY_SIZE; k++)
      avg += arrayOfInts[rand()%ARRAY_SIZE];
   avg/=ARRAY_SIZE;

   cout << endl << avg << endl;
   elapsedTime = computeElapsedTime(startTime);
   displaySeconds("Time for simple array: ", elapsedTime);

   startTime = startClock();   // stl vector [] START TIME START TIME ----------
   for (k = 0; k < ARRAY_SIZE; k++)
      vectorOfInts[k] = rand()%100;

   for (k = 0, avg = 0.; k < ARRAY_SIZE; k++)
      avg += vectorOfInts[rand()%ARRAY_SIZE];
   avg/=ARRAY_SIZE;

   cout << endl << avg << endl;
   elapsedTime = computeElapsedTime(startTime);
   displaySeconds("stl vector using []: ", elapsedTime);

   startTime = startClock();   // stl vector push_back() START TIME START TIME --------
   for (k = 0; k < ARRAY_SIZE; k++)
      vectorOfInts2.push_back(rand()%100);

   for (k = 0, avg = 0.; k < ARRAY_SIZE; k++)
      avg += vectorOfInts2[rand()%ARRAY_SIZE];
   avg/=ARRAY_SIZE;

   cout << endl << avg << endl;
   elapsedTime = computeElapsedTime(startTime);
   displaySeconds("stl vector using push_back(): " , elapsedTime);

   startTime = startClock();   // stl vector at() START TIME START TIME ----------
   for (k = 0; k < ARRAY_SIZE; k++)
      vectorOfInts.at(k) = rand()%100;

   for (k = 0, avg = 0.; k < ARRAY_SIZE; k++)
      avg += vectorOfInts.at(rand()%ARRAY_SIZE);
   avg/=ARRAY_SIZE;

   cout << endl << avg << endl;
   elapsedTime = computeElapsedTime(startTime);
   displaySeconds("stl vector using at(): ", elapsedTime);

   startTime = startClock();   // FHvector [] START TIME START TIME ----------
   for (k = 0; k < ARRAY_SIZE; k++)
      vectorOf_FH_ints[k] = rand()%100;

   for (k = 0, avg = 0.; k < ARRAY_SIZE; k++)
      avg += vectorOf_FH_ints[rand()%ARRAY_SIZE];
   avg/=ARRAY_SIZE;

   cout << endl << avg << endl;
   elapsedTime = computeElapsedTime(startTime); 
   displaySeconds("FHvector using []: ", elapsedTime);
  
   startTime = startClock();   // FHvector push_back() START TIME START TIME ----------
   for (k = 0; k < ARRAY_SIZE; k++)
      vectorOf_FH_ints2.push_back(rand()%100);

   for (k = 0, avg = 0.; k < ARRAY_SIZE; k++)
      avg += vectorOf_FH_ints2[rand()%ARRAY_SIZE];
   avg/=ARRAY_SIZE;

   cout << endl << avg << endl;
   elapsedTime = computeElapsedTime(startTime);
   displaySeconds("FHvector using push_back(): " , elapsedTime);

   return 0;
}

// for timing our algorithms
clock_t startClock()
{
   return clock();
}

double computeElapsedTime(clock_t startTime)
{
   clock_t stopTime = clock();
   return (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC;
}

void displaySeconds(string message, double time_in_secs)
{
   cout << "Elapsed time for " << message 
      << time_in_secs  << " seconds." << endl;
}

/* -------------------------- RUN --------------------------

49.6864
Elapsed time for Time for simple array: 0 seconds.

49.3352
Elapsed time for stl vector using []: 0.015 seconds.

49.112
Elapsed time for stl vector using push_back(): 0.016 seconds.

49.7352
Elapsed time for stl vector using at(): 0.015 seconds.

49.7503
Elapsed time for FHvector using []: 0 seconds.

49.4243
Elapsed time for FHvector using push_back(): 0.016 seconds.
Press any key to continue . . .

-------------------------- END RUN -------------------------- */

Optinimization was on in this trial. We see that there is no discernable different between FHvectors and raw arrays to within 1/1000 of a second for this 200,000 element array run (they are both clocking 0 seconds). Meanwhile Microsoft STL vectors seem to be slower using [], push_back() and at().

For a second comparison, here is the program run on a Unix platform, without optimization, this time using 400,000 elements (twice as many as in Windows, which limited the size of the array to 200,000):

49.4273
Elapsed time for Time for simple array: 0.012241 seconds.


49.5874
Elapsed time for stl vector using []: 0.011233 seconds.


49.4447
Elapsed time for stl vector using push_back(): 0.024066 seconds.


49.5397
Elapsed time for stl vector using at(): 0.016664 seconds.


49.5007
Elapsed time for FHvector using []: 0.015209 seconds.


49.5064
Elapsed time for FHvector using push_back(): 0.018607 seconds.

FHvector is slightly faster in the push_back() race but slightly slower in the bracket, [], race. This remains true as the array size increases.