CS210 Lab: STL Lists

Prelab Questions:

For a review of relevant topics click here.

Highlights of This Lab:

Lab Exercise:


Click the little computer above for a detailed description.
For this excercise you will be asked to implement STL lists to sort student names.

1. Introduction to STL (Standard Template Library)

In CS110 and CS115, you learned about STL and Strings. You have probably been using these strings without thinking about them. STL strings are what are available when you #include <string> and declare a string: string str1("This is a test"); In addition to strings, the STL provides other components, which may save you some time coding.

The Standard Template Library (STL) is considered to be the most important features of C++ and it has grown recent years. The STL provides general-purpose, templatized classes and functions that implement many popular and commonly used algorithms and data structures For example, it includes support for vectors, lists, queues, and stacks. It also defines various routines that access them. Because the STL is constructed from template classes, the algorithms and data structures can be applied to nearly any type of data.

At the core of the STL are four foundational items:

These items work together to offer solutions to many programming problems. The following paragraphs describe these components:

Containers are objects that hold other objects. There are several different kinds of containers. Some are general purpose, and others adapt another container to match an ADT you may have studied. The following are a few STL containers:

Each container class defines a set of functions that may be applied to the container. For example, a list container includes functions that insert, delete, and merge elements. Each container type must be included separately.

Iterators are objects that are, more or less, pointers. They give you the ability to cycle through the contents of a container in much the same way that you would use a pointer to cycle through an array. Although the iterators that we are talking about in the STL library, respond a little differently, the p iterator from your assignments and the cursor in the previous list labs acted as a type of iterator, allowing you to cycle through the list.

Algorithms act on the contents of containers. They include capabilities for initializing, sorting, searching, and transforming the contents of containers. Algorithms never change the size of a container. Some algorithms depend on external functions. Algorithms are all included with the algorithm header.

Function Objects are objects with an overloaded operator(). Such objects, or their classes, are sometimes used as arguments to STL algorithms, or to modify a container's behaviour. Next week you will use a function object to modify the hashing function of a hash table based container. Function objects used by STL are included with the funtional header.

2. STL Lists

Some points about the STL list container: Before discussing the member functions of an STL list, here is a simple example using the STL list:


Notice that in order to use the list, you must 
#include <list>

2.1 Member Functions

There are many member functions for the STL list class.  Without overwhelming you with all of them, here are the most commonly used ones:

size size_type size() const;
Returns the number of items (elements) currently stored in the list. The size_type type is an unsigned integer value.
// Loop as long as there are still elements in the list.
 while (list1.size() > 0)
 {
   ...
 }
empty bool empty() const;
Returns a true value if the number of elements is zero, false otherwise. 
if (list1.empty())
{
  ...
}
push_back
push_front		 void push_back(const T& x);
void push_front(const T& x);
Adds the element x at the end (or beginning) of the list. (T is the data type of the list's elements.)
list<int> nums;
nums.push_back (3);
nums.push_back (7);
nums.push_front (10); // 10 3 7
front
back		 T& front();
const T& front() const;
T& back();
const T& back() const;
Obtain a reference to the first or last element in the list (valid only if the list is not empty). This reference may be used to access the first or last element in the list.
list<int> nums;
nums.push_back(33);
nums.push_back(44);
cout << nums.front() << endl; // 33
cout << nums.back() << endl; // 44
begin iterator begin();
Returns an iterator that references the beginning of the list.
end iterator end();
Returns an iterator that references a position just past the last element in the list.
insert iterator insert(iterator position, const T& x);
Insert the element x (type T is the type of a list element) into the list at the position specified by the iterator (before the element, if any, that was previously at the iterator's position). The return value is an iterator that specifies the position of the inserted element.
  nums_iter = find (nums.begin(), nums.end(), 15);
  if (nums_iter != nums.end())
  {
    nums_iter = nums.insert (nums_iter, -22);
    cout << "Inserted element " << (*nums_iter) << endl;
  }
erase iterator erase(iterator position);
iterator erase(iterator first, iterator last);
Erase (remove) one element or a range of elements from a list. In the case of a range, this operation deletes elements from the first iterator position up to, but not including, the second iterator position. The returned iterator points to the element after the last one erased. For an alternate way to erase all elements, see the description of clear() below. 
  nums.erase (nums.begin(), nums.end());
clear void clear();
Erase all elements from a list.
nums.clear();
pop_front
pop_back		 void pop_front();
void pop_back();
Erases the first (or last) element from a list. These operations are illegal if the list is empty.
  while (list1.size() > 0)
  {
    ...
    list1.pop_front();
  }
remove void remove (const T& value);
Erases all list elements that are equal to value. The equality operator (==) must be defined for T, the type of element stored in the list.
  nums.remove(15);
sort void sort();
Sorts the list elements in ascending order. The comparison operator < ("less than") must be defined for the list element type. Note that the STL sort algorithm does NOT work for lists; that's why a sort member function is supplied.
  nums.sort();
reverse void reverse();
Reverses the order of elements in the list.
  nums.reverse();

2.2 Another Example

In the following example, we demonstrate the use of some of the STL list member functions discussed above.  This program creates a list of random integers and then puts the list into sorted order:

Here is a sample output of the above program: 

Original list:
41 18467 6334 26500 19169 15724 11478 29358 26962 24464 

Sorted contents:
41 6334 11478 15724 18467 19169 24464 26500 26962 29358

3. Lab Exercise


Test Plan for the Student Name Processing Program
Test Case Checked
Students in the file input.txt  
   
   

If you would like to, make your own student files and test them with this program.

When you are finished your program should

  1. Have both the '<<' and '<' operators overloaded
  2. Read the list of names from the text file and print them out unsorted
  3. Sort the names and print them out sorted

A sample output could look like this :

Example output that shows a list of students printed unsorted, then the same list of students printed sorted by last name

5. Postlab Exercises

For postlab exercices, click here.

CS Dept Home Page
Back to 210 Lab Outline

© Copyright: Department of Computer Science, University of Regina.