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: 

// An example using STL list. 
// This program pushes 4 integer values to an STL list.
// It then prints out each of these 4 values before
// deleting them from the list
#include <iostream>
#include <list>		// list class library
using namespace std;
  
int main()  
{  
  // Now create a "list" object, specifying its content as "int".
  // The "list" class does not have the same "random access" capability
  // as the "vector" class, but it is possible to add elements at
  // the end of the list and take them off the front.
  list<int> list1;

  // Add some values at the end of the list, which is initially empty.
  // The member function "push_back" adds at item at the end of the list.
  int value1 = 10;
  int value2 = -3;
  list1.push_back (value1);
  list1.push_back (value2);
  list1.push_back (5);
  list1.push_back (1);

  // Output the list values, by repeatedly getting the item from
  // the "front" of the list, outputting it, and removing it
  // from the front of the list.
  cout << endl << "List values:" << endl;
  // Loop as long as there are still elements in the list.
  while (list1.size() > 0)
  {
    // Get the value of the "front" list item.
    int value = list1.front();
    // Output the value.
    cout << value << endl;
    // Remove the item from the front of the list ("pop_front"
    // member function).
    list1.pop_front();
  } 
 
  return(0); 
}
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()); // Remove all elements;
...
  nums_iter = find(nums.begin(), nums.end(), 3); // Search the list.
  // If we found the element, erase it from the list.
  if (nums_iter != nums.end()) nums.erase(nums_iter);
clear void clear();
Erase all elements from a list.
nums.clear(); // Remove all elements;
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: 

// Create a random integer list and sort the list
#include <iostream>
#include <list>
using namespace std;

int main()
{
	list<int> lst;
	int i;

	//create a list of random integers
	for(i = 0; i < 10; i++)
		lst.push_back(rand());
	
	cout << "Original list: " << endl;
	// create an iterator object and make it point to the
	// beginning of the list
	list<int>::iterator p = lst.begin();
	while(p != lst.end()){
		cout << *p << " ";
		p++;
	}

	cout << endl << endl;
	
	// sort the list
	lst.sort();

	cout <<"Sorted contents:\n";
	p = lst.begin();
	while(p != lst.end()){
		cout << *p << " " ;
		p++;
	}
        cout << endl << endl;
	return (0);
}

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. Comparison between Ordered List and STL List

An important part of coding is to adapt your way of thinking to handle existing code. In your class assignments you coded your own version of the instructor's description of the Sorted List ADT and its algorithm to solve various problems. In this lab exercise, we will be using STL lists to sort a list of students stored in a file.

Before we do this, let's do a comparison between key parts of the sorted list you saw in Dr. Hilderman's class and the STL list container.

Description OrdList STL List
#include Statement up to you in your implementation

#include <list>
Creating a List Object List message list<DataType> message
List Status Operations bool IsEmpty() bool empty()
bool IsFull() bad_alloc exception may be thrown if space cannot be made.
List Manipulators void InsertSorted(DataType &newDataItem)

Insert with void push_back(const DataType& x)
or void push_front(const DataType& x)
or iterator insert(iterator position, const DataType& x)

Then, to make the list sorted at some point, use void sort() (requires that operator< be defined for DataType)
void Delete() void erase(iterator position)
int Clear() void clear()
Iterator Actions void ResetP() iterator begin()
n/a iterator end()
int Iterate() p++ ( where p is list<DataType>::iterator)
DataType Read() *p (where p is list<DataType>::iterator)
DataType Write(DataType& x) *p = x (where p is list<DataType>::iterator)

4. 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.

CS Department Home Page
CS210 labs
University of Regina

Copyright: Department of Computer Science, University of Regina.