UMBC CMSC 202 Computer Science II

Lab13: Standard Template Library

Objective

In this lab you will practice using iterators with the vector and list classes from the Standard Template Library. You will use iterators to sort, insert elements, remove elements in vectors using Standard Template Library.

Understanding Iterators

To do this lab, you will need to have a basic understanding of iterators. Here are two sources:

O'Reilly Network: What is an Iterator in C++? Iterators: An iterator in C++ is a concept that refines the iterator design pattern into a specific set of behaviors that work well with the C++ standard library. The standard library uses iterators to expose elements in a range, in a consistent, familiar way. Anything that implements this set of behaviors is called an iterator. This paves the way for generic algorithms and makes it easy to implement your own iterators and have them integrate smoothly with the standard library. [More...]
MSDN (Microsoft): Iterators are a generalization of pointers, abstracting from their requirements in a way that allows a C++ program to work with different data structures in a uniform manner. Iterators act as intermediaries between containers and generic algorithms. Instead of operating on specific data types, algorithms are defined to operate on a range specified by a type of iterator. Any data structure that satisfies the requirements of the iterator may then be operated on by the algorithm. [More...]

In this lab, we will use iterators to work with vectors and lists from the Standard Template Library (STL). Iterators do many things, we will only look at the simple uses. For example, if we had a vector V of 10 int items, we can step through the vector using a for loop: for (i = 0 ; i < V.size() ; i++) { cout << V[i] << " " ; } Using iterators we would, write: for ( it = V.begin() ; it != V.end() ; it++ { cout << *it << " " ; } The reason we might want to abandon our familiar for loop index using an int variable is that the syntax for looping through other STL data structures (e.g., a list) is exactly the same when you use an iterator.

To understand the syntax of the second for loop above, note that:

The type of it is vector<int>::iterator
V.begin() returns an iterator that represents the "position" of the first element of the vector.
V.end() returns an iterator that represents the "position" past the last element of the vector.
The ++ operator is defined for most iterators, as are ==, != and --
The dereference operator * returns the data at the "position" represented by the iterator.

Step 0: Get the file

You will only need one file: lab13.cpp.

This C++ program has defined:

vector<int> V ; list<int> L ; vector<int>::iterator it1 ; list<int>::iterator it2 ; Some numbers have been added to V and L for you.

Step 1: Warm up

A for loop that prints out the vector V has been written. Add a for loop that prints out the linked list L using iterators.

Expected output: 60 20 40 30 70 90 60 80 10

Step 2: use the insert() function

Add code to insert the number 50 to the vector V the insert() method in vector. We want 50 to appear just before 70 in the vector. The syntax for calling insert is: V.insert(it1,50) ; but you have to set it1 to the right position.

Hint: use a while loop to loop through V until you find the 70.

Expected output: 60 20 40 30 50 70 90 60 80 10

The code for inserting into a linked list would be identical. So, we won't insert in the linked list. However, note that insert is actually more efficient in a linked list, since you don't have to shift the contents of a linked list for insertion.

Step 3: use the erase() function

Add code to remove the number 90 from the linked list L. The syntax for calling erase is: L.erase(it2) ;.

Expected output: 60 20 40 30 70 60 80 10

Step 4: use the for_each function

The for_each function applies a given function to items in the range of iterators given. The syntax is: for_each(first, last, func) ;

Here first and last are iterators. The parameter func is a function with no return value and takes exactly one parameter of the correct type by reference.

A function add5() has been written for you. Use the for_each() function to add 5 to each element of the vector V and each element of the linked list L. (You should make two class to for_each.)

Expected output:
65 25 45 35 55 75 95 65 85 15
65 25 45 35 75 65 85 15

Step 5: vector has random access iterators

Not all iterators are created equal. The iterator for the vector class is a "random access" iterator and has the + operator defined. Use the for_each() function and the + operator for vector iterators to apply add5 to the first 5 items in vector V.

Expected output: 70 30 50 40 60 75 95 65 85 15

Note: this would not work for the linked list L since operator+ is not defined.

Step 6: sorting

STL has a sort() function. The syntax for calling sort is: sort(first, last). Here first and last are iterators.

Expected output: 15 30 40 50 60 65 70 75 85 95

Step 7: cannot sort linked lists

Try using the same sort() function on a linked list.

Expected output: lots of compile-time errors.