CS 14 - Fall 2003

CS 14 - Lab 5

This lab will give you experience using STL, the C++ Standard Template Library.

Mid-Quarter Evaluations

But first, please fill out an anonymous review of the course. The link is available here. We would like you to answer the following questions, so that we can put on a better course for you:

Comments for/about the instructor (Wagner Truppel)
Comments for/about your TA (Titus Winters or Nelson Perez)
Comments about the in-lab exercises
Comments about the programming assignments
Comments about the quizzes
Comments about the lecture homeworks
The course overall: rank this course A through F, and explain why. What could we do better?
When did you take CS 12 / attempt CS 14 before.
If you took CS 12 at another school, tell us what programming language and development platform was used, and whether it was difficult to make the transition.

When you are done, show your TA the "Thank you page" and you'll be marked down for 1 point.

STL List

The Standard Template Library is a series of standardized, heavily optimized, industry standard (or at least exceedingly common) set of data structures and algorithms. Whether you know it or not, you already are familiar with parts of STL: the string class and the vector class.

We will here discuss some of the common STL data structures. Given the focus of this course so far (lists), we'll start with list (a doubly-linked list type) and slist (a singly-liked list type).

list

As an STL container, like vector, list is written as a templated type. To declare an instance of type list you must provide it the appropriate type. For example, to declare a list of integers:

list<int> a;

Unlike vector, you cannot simply perform random access with a list object (that is, the [] operator doesn't work). Generally, insertion is done using the push_back or push_front methods.

list<int> a;
a.push_back(1);
a.push_front(5);

So now we know how to insert data, how do we get it back? Iterators. Since the iterator for each container (vector, list, slist) is written as a special sub-class of the main container. (This just means you need to use the :: scoping operator.)

list<int> a;
a.push_back(1);
a.push_front(5);
for (list<int>::iterator i = a.begin(); i != a.end(); ++i)
{
    cout << *i << endl;
}

This is the idiomatic (canonical) "for" loop with an iterator. You WILL want to memorize this.

Now we can insert data, see what is in the list, how about removal?

list<int> a;
a.push_back(1);
a.push_front(5);
a.pop_front();
a.pop_back();

Other useful methods of list:

size() - return the count of the number of elements in the container
front() - peek at the value at the head of the list (without removing it)
back() - peek at the value at the end of the list

Other wonderful things about list:

lists compare using the standard comparison operators (==, !=)
lists pass by value unless explicitly passed by reference

There is a fantastic reference for STL available online (it's the #1 hit on Google right now, and has been for a good long while). It takes a bit of practice to understand, but it is strictly a Good Idea to figure it out. The link is http://www.sgi.com/tech/stl/table_of_contents.html

The Assignment

7 points Write a program using STL list (remember to #include<list>). Your program should read in integers from standard input (using cin) until the user presses Ctrl+D (to signify EOF). Store each value at the end of the a list. (If you don't know how to read until EOF, read this )

Next, insert two more values to the list. Insert the value 10 at the head of the list, and insert the value -1 at the end of the list.

Print the list.

Pop the 10 and the -1 off the front and the back of the list.

Print the list again.

.4 points: Write the above code using vector instead of list.

.2 points: What does the clear() method do?

.2 points: How do you sort a list?

.2 points: What does the unique() do? What must be true about the list before it works correctly?