Courses/CS 2124/Lab Manual/The Standard Template Library

A portion of this lab is to be done during the scheduled lab time. The take-home programming assignment is to be turned in before the next lab; see the lab website. The in-lab portion is worth 40% of the lab credit; the programming assignment is worth the other 60%. See the website for details on how the programming assignment will be graded. You are not responsible for user errors in input unless specified in the assignment. Feedback will be provided explaining your grade on each assignment.

It is important that you complete each step before going on to the next, as the exercises build upon one another. You will find it helpful to diagram the action of each method or function as you go along. If you have difficulty in some step, DO NOT proceed before resolving it; seek assistance from your lab proctor. You will not be able to fully appreciate the remaining content of the lab and you are likely to compound the problem.

Introduction

This lab introduces the use of STL, the C++ Standard Template Library, through a series of examples.

Topics Covered in this Lab:

• STL iterators
• STL algorithms
• STL containers

Questions Answered in this Lab:

• How does an STL iterator differ from a pointer in a conventional program?
• How are STL algorithms used?
• What type of STL container is appropriate to a given situation?

Demonstrable Skills Acquired in this Lab:

• Understanding of how STL containers, iterators, and algorithms work together
• Appreciation for what the STL can replace in a conventional program

Create a project oop12 with the empty C++ header and source files listed below; upon completion of the in-lab portion of this assignment, submit all of these files in zip file oop12iL.zip.

Makefile	// directs compiling and linking of others
main.cpp	// contains main function

The STL Iterator

This exercise begins by using an STL iterator to read integers from the standard input (the keyboard). Put an include for the header file iterator in file main.cpp. Add the following code segment to main(); note the definition and usage of the istream_iterator object input.

Code Illustration

   int a [100];
   int size = 0;
   cout << "Enter an integer (-1 to end): ";
   std::istream_iterator <int> input (cin);
   while (*input != -1)  // dereference
   {
      a[size++] = *input;  // dereference
      cout << "Enter an integer (-1 to end): ";
      input++;  // increment
   }  // end while

Notice how iterator input is associated with input stream cin. Notice also how input is dereferenced and incremented as a pointer variable might be in a conventional C++ program.

Add a short loop to main() to print the contents of array a to the standard output cout; print one space between each pair of values.

FOR IN-LAB CREDIT: Demonstrate this output for the lab instructor.

The STL Algorithm

An STL algorithm can be used to print the contents of the array as well; add an include for the header file algorithm to file main.cpp and add the following to main.

Code Illustration

   std::ostream_iterator <int> output (cout, " ");
   std::copy (a, a+size, output);
   cout << endl;

The STL algorithm copy will move everything from the location specified in the first parameter up to, but not including, the location specified in its second parameter to its third parameter. Since a is the name of an array, it is essentially the address of the first array element; the addition of size to a results in a location one past the last element stored in a. Notice how iterator output is associated with cout; the character-string parameter specifies what should be written between values.

The STL Container

An STL container can be used to store and manipulate data. In particular, the STL vector container can be used where an array might be used in a conventional C++ program. Add an include for the header file vector to file main.cpp and add the following to main().

Code Illustration

   std::vector <int> v;
   cout << "\n\nEnter # for max subsequence search (-999 to end): ";
   std::istream_iterator <int> input2 (cin);
   while (*input2 != -999)
   {
      v.push_back (*input2);
      cout << "Enter # for max subsequence search (-999 to end): ";
      ++input2;
   }  // end while

The STL vector object v will be filled with numbers from the keyboard via another istream_iterator object, input2. The vector member function push_back is used to add data to the end of its object.

The values stored in a vector may be manipulated using an iterator. Add the following to main().

Code Illustration

   std::vector<int>::const_iterator vIndx;
   for (vIndx = v.begin(); vIndx != v.end(); vIndx++)
      cout << *vIndx << ' ';
   cout << endl;

The vector member function begin returns a reference to the first item in the container; function end returns a reference to just past the last item in the container, hence the use of the != operator.

The same effect may be achieved with the copy algorithm; add the following to main().

Code Illustration

   std::copy (v.begin(), v.end(), output);
   cout << endl;

Note here again how copy uses references to the first item and one past the last item in the container.

FOR IN-LAB CREDIT: Demonstrate the results of copy for the lab instructor.

Example Problem: Maximal Subsequence

Consider now the problem of finding the subsequence in a series of values whose sum is maximal. A vector will be used to implement a search for this subsequence. A brute-force algorithm is developed here; a more elegant solution is to be devised in the homework.

Consider for example a sequence of five values: $a_1$, $a_2$, $a_3$, $a_4$ and $a_5$. There are five subsequences starting with $a_1$, and each of their sums must be considered: $a_1$ by itself, $a_1$ + $a_2$, $a_1$ + $a_2$ + $a_3$, $a_1$ + $a_2$ + $a_3$ + $a_4$, and $a_1$ + $a_2$ + $a_3$ + $a_4$ + $a_5$. Similarly, there are four subsequences starting with $a_2$, three with $a_3$, two with $a_4$ and just one with $a_5$ ($a_5$ by itself). In general, there will be $n$ + ($n$-1) + ($n$-2) + $\ldots$ + 1 = $n$($n$+1)/2 subsequences to consider for $n$ values. A nested loop can be written to generate these subsequences; the outer loop will keep track of the starting location while the inner loop keeps track of the ending location. Two iterators shall be used for this purpose. Add the following to function main.

Code Illustration

   std::vector <int>::const_iterator beginIndx;
   std::vector <int>::const_iterator endIndx;

   for (beginIndx = v.begin(); beginIndx != v.end(); beginIndx++)
      for (endIndx = beginIndx; endIndx != v.end(); endIndx++)
         // body;

The body of this loop must use another iterator, e. g., sumIndx, to move between beginIndx and endIndx, summing the elements between them. This sum should be compared to a running maximum sum; if it is found to be greater than the current maximum, the sum should be stored as the new maximum and the current beginning and ending indices should be saved. This being done, the results can be displayed with the following addition to function main.

Code Illustration

   cout << "maximal subsequence is ";
   std::copy (maxBeginIndx, maxEndIndx+1, output);
   cout << endl;

The iterators maxBeginIndx and maxEndIndx in the above code fragment are defined like beginIndx and endIndx in the preceding fragment. Note that maxEndIndx+1 is passed to algorithm copy here since copy always expects an ending location one past the last value to be copied.

Execute the program and verify that it is working correctly.

FOR IN-LAB CREDIT: Demonstrate the algorithm for input of the lab instructor's choosing.

	FOR IN-LAB CREDIT:	Zip up these files: Makefile main.cpp
		Name the file oop12iL.zip and upload to CSCADE.