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 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 new feature added to C++ in 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 three 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. The following are a few STL containers:

In addition to the basic 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.

Algorithms act on the contents of containers. They include capabilities for initializing, sorting, searching, and transforming the contents of containers.

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 cursor in the previous list labs acted as a type of iterator, allowing you to cycle through the list.

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 an 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 void erase(iterator position);
void 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. 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 Previous Lab and STL Lists

An important part of coding is to adapt your way of thinking to handle existing code. In the Sorted Lists lab exercise, we used a pre-existing set of data members and member functions to input packets into an ordered list and then output them to the screen.

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 general comparison between the OrdList class that we previously used and the STL List.

Description OrdList STL List
#include Statement #include "ordlist.h" #include <list>
Creating a List Object OrdList message list <DataType> message
List Status Operations bool IsEmpty() bool empty()
bool isFull() N/A
List Manipulators void insert(DataType &newDataItem) void push_back(const T& x)
or void push_front(const T& x)
or iterator insert(iterator position, const T& x)
void remove() void erase(iterator position)
void clear() void clear()
Iterator Movement void gotoBeginning() iterator begin()
void gotoEnd() iterator end()
bool gotoNext() p++ ( where p is list<DataType>::iterator)
DataType getCursor() *p (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.

5. Postlab Exercises

For postlab exercices, click here.

CS Dept Home Page
CS Dept Class Files
CS210 Class Files


Copyright: Department of Computer Science, University of Regina.