The objective of this lab is to familiarize you with issues involved in programming using the vector and list generic containers in the C++ standard library.

Recall that two of the central components in the Standard Template Library (STL, now part of the C++ standard library) are containers and iterators. Containers are objects that can hold a collection of other objects, and iterators are objects that are used to refer to individuals in a container and to step through its contents. Many types of data structures can serve as container/iterator pairs; for example, a normal C-style array can be treated as a container for which a C-style pointer acts as an iterator. Containers and iterators can also be more complex objects, and the standard library provides a number of these (vectors, lists, maps, etc.)

A third component of the standard library is its collection of generic algorithms. These are commonly used algorithms that have been programmed (using templates) in a generic way; they are designed to work in as many situations as possible. For example, there are standard algorithms to sort, reverse, and randomly shuffle ("mix up") a collection of objects. There are also algorithms to search for a specific object, either using linear search or binary search. Most of these generic algorithms can be used with any of the standard containers; learning to use pre-programmed (and pre-debugged!) components like these is the key to effective programming in C++.

Work your way through the following steps, in order:

1. Copy the lab files. You will need to modify the files in the lab, so first make your own copies. Copy all the files, but don't (yet) add them all to your project. Initially, your project should contain only main.cpp.
• complex.h
• complex.cpp
• main.cpp
• main2.cpp
  
  
2. Examine the main program. The main program creates a vector of integers and prints it out. Pay special attention to the function operator<<, and note how it is generic; it is written (using templates) so that it will work with any type of vector.

The class std::vector can be thought of as an array that will automatically resize itself as necessary. It is one of the most useful classes in the standard library; if you are not familiar with it, refer to a C++ reference.

Build and run the main program. Does it work as expected?


3. Modify the program. Add the file complex.h to your project. (Note: do not yet add complex.cpp.) This defines a simple class for complex numbers. Change the main program so that it includes complex.h, and change the type of the vector from int to complex.

Attempt to build the program; what went wrong?


4. Add an overloaded operator to the class. The first error message says that the compiler does not know how to print out a complex number (where do we ask it to do this?), and to fix it we must tell the compiler how to do so. Make sure you understand this error message.


The function to do this defined in complex.cpp; add this file to your project now. Note the similarity between the prototype of this function and the one in the main program. Overloading the "output" operator in this way is common and a very convenient method to add to your own classes.

Add an appropriate prototype to the complex class for the new "output" function. (Hint: Is this function a member function? How can it access the private members of the class?)



5. Getting the program to build. Build the executable. What is going wrong? Look at the first error message. Although it is horribly cryptic, with some explanation we can figure out what the compiler is complaining about.


Look at the end of the error message; it mentions the class complex. This tells us that the problem is in using our new class. The begining of the message tells us that the problem in particular is with the function operator<. The problem is that the compiler does not have enough information about how to implement this comparison operation.

Why does the compiler need this information? Did we ask it to compare complex numbers in our program? We did not, and this error is the result of a bug in Microsoft's implementation of the standard library.

This is instructive for two reasons. First, since we are using the Microsoft tools, as a practical matter we need to work around such bugs. Second, even though in this case we got the error message due to a Microsoft bug, it is very easy to get the same error message because of problems in our own code. It is therefore important to understand what the error means and how to fix it.

To fix the error, we need to give the compiler some more information about our complex class. Add the following to complex.h

          bool operator<(const complex & a) const;

This declares a member function that compares two complex numbers. (We don't need to implement this function since we never make use of it; the declaration alone is sufficient to take care of the error.)

Try building the program now. Are there any other member function declarations you need to add? Run the program to test it after you get it to build.



6. Expand the main program. Go back to the main program and add the following code at the end:

          std::sort(a.begin(), a.end());
          std::cout << "a sorted = " << a << std::endl;

We are using a standard library function to sort the vector. Rather than specifying the vector to sort, we pass as arguments two iterators that refer to the first and the last item in the range we want to sort. This makes the sorting function more general, for example allowing us to sort only a portion of the vector. However, in this case we are not doing anything fancy and we just want to sort the whole thing. We therefore want to pass in iterators to the first and last elements in the vector; we can obtain these iterators by using the member functions begin and end, which every standard container provides.

Rebuild the program; what is wrong now? This time we get errors from the linker, not the compiler. This error is equally cryptic, but looking at it we can guess that the problem is that there is no "less than" operator defined for the complex class.



7. Implementing the operator. Above we declared the less than operator for the complex class, and this is sufficient to satisfy the compiler. However, the linker will complain if we use this operator and it is not defined anywhere. (Where did we implicitly use this operator?)


Implement this function (add the code to complex.cpp. [Recall that we compare complex numbers by their magnitude: the sum of the squares of the real and imaginary parts.] Add some "real" complex numbers (with an imaginary part) to the vector, and then build and run your program to test it.



8. Yet another overloaded operator. Add the following implementation of the addition operator to complex.cpp, and an appropriate prototype to complex.h:

          complex operator+(complex & a, complex & b)
          { 
            return complex(a.real + b.real, a.imag + b.imag);
          }

This is a friend function, rather than a member function, so that the compiler can use complex constructors and automatic type conversions on both sides of the operator, not just the right.

Also add the following code to the end of the main program:

          std::cout << "sum of a is " 
                    << std::accumulate(a.begin(), a.end(), complex(0))
                    << std::endl;

What we are doing here is using a standard function, accumulate, to sum up the numbers in the vector. You can think of this function as performing the following:

                    sum = initial_value
                    for i = first_element to last_element
                      sum = sum + item[i]
                    return sum

We provide the iterators for the first element and last element, and the initial value as the first, second, and third arguments, respectively. (Note that we use the constructor to provide the initial value. This is not strictly necessary, since due to the way the constructor is coded, the compiler can figure it out from just a single integer or floating point argument. Try it and see.) As with sort, we accumulate over the entire container by providing iterators to the first and last elements using begin and end.

Build and run the program, and check that its output is correct. As another example of a useful standard function, write some code to use the find function:

          // Prototype for standard library function 'find'.
          template &ltclass Iterator, class T>
          Iterator find(Iterator first, Iterator last, T value);

The find function, like accumulate, takes as arguments two iterators and a value; it searches the container (starting at the element referred to by the 'first' iterator, and continuing up to but not including the element referred to by the 'last' iterator) for the value. It returns an iterator that refers to the element in the container that is equal to the desired value if it exists; if it does not, it returns the iterator 'last'.

Add some code to the main program to search for the square root of -1 (negative one) in the vector, and print out a message indicating whether or not it was found. Build and test the ouput of the program.



9. Const correctness. Add the following code to the end of the main program:

          const std::vector<complex> b = a;
          std::cout << "sum of b is " 
                    << std::accumulate(b.begin(), b.end(), complex(0))
                    << std::endl;

Note that b is declared as const, meaning that we can't change it; this is appropriate since all we want to do is print out its sum. Try to build the program; what went wrong?

The compiler is complaining about the plus operator for the complex class. Didn't we just implement this? We did, but look closely at the error message: it needs a version of the plus operator that works with a const complex value (i.e., the plus operator must promise not to change the numbers it is adding). Our implementation does not in fact change either of its arguments, but we have not promised this to the compiler; our function prototype is inaccurate.

To fix this, change the types of the arguments to be const. Test your fix by building and running the program.



10. Const correctness continued. Add a simple member function to provide us with the real part of the complex number (add the following code to complex.h):

          double real_part() { return real; }

Add the following code to the end of the main program:

          const complex c(12,34);
          std::cout << "c is " << c << " with real part " << c.real_part()
             << std::endl;

Build the program. What went wrong?

This error is again due to const correctness. Although the real_part member function does not change the complex number, we did not specify this to the compiler. To do so, we put the keyword const between the closing parentheses of the argument list and the opening curly bracket of the body of the function. Make this fix, build, and run the program.



11. Working with iterators. The vector output function in the main program uses integer indexing to step through the elements of the vector. While this works for vectors (which are based on an array data structure), it will not work for all containers. Change this function so that it is more generic by modifying the code to use iterators rather than integer indexing.
    
    
12. Working with lists. Another useful type of standard library container is the list. This is a doubly-linked list, as opposed to an array based data structure. Each data structure has advantages and disadvantages in different situations; the standard library makes it easy to choose whichever is appropriate because they are pretty much interchangeable.


Delete main.cpp from your project and add main2.cpp. Build the program, fixing any errors you need to, and run it.

Note that the only two differences in the use of vector vs. list are in the generic "print out" function and in the use of a member function sort rather than std::sort. Why is this? Try changing a.sort() to code using std::sort (as in the vector example). Can you decipher the compiler error?

At the conclusion of this lab, take a moment to review the following:

You should understand how to use the standard containers and their iterators, in particular the classes vector and list.

You should have gained an appreciation of the usefulness of the standard library functions and how they can make programming easier; you should be motivated to become familiar with the other functions in the standard library.

You should understand what "const correctness" means and how bugs can be caused when programs do not use const correctly.

You should be familiar with the types of pitfalls that can occur when you combine your own classes with the standard containers and standard algorithms, how to diagnose the resulting error messages, and how to fix them.