CSCI.1200 - Computer Science II
Summer, 2002
Worksheet 20
More on the Standard Template Library

The STL list Class

While the class vector is probably the most widely used, there are a number of other container classes defined in STL. The class list is an ordered sequence of elements. Unlike a vector, it is not random access. The term random access means that any element can be reached in constant time. Since a vector is like an array, the time that it takes to retrieve element 1000 is the same as the time to retrieve element 0. The STL list class is implemented as a doubly linked list (you don't need to know that to use it), so retrieving the element at position n is $O(n)$. (Why?). On the other hand, the insert operation, inserting a new element in the middle, is $O(n)$ for a vector because it is necessary to move every element above the insertion point to the right by one, but constant time ($O(1)$) for a list.

A list class should be used any time that you would use a linked list. All storage management and all of the standard list operations are defined for you, so if you didn't like working with linked lists, you will never have to code one up again.

Here is the class declaration:

using namespace std;
#include <list>
template <class T>
class list;

The operators $==$ and $<$ must be defined on the type T.

As with a vector, the type
list<T>::iterator
is defined and is used to point to a particular element. The operators $++$ and $--$ (both prefix and postfix) are defined on a list, and behave in the obvious fashion. The $*$ (dereferencing) operator is also defined on a list iterator. However, if i is a list iterator, you cannot increment it by an arbitrary amount as you can with a vector iterator.

Here are some of the member functions.

list() the default constructor

iterator begin() returns an iterator which references the first element in the list.

iterator end() returns an iterator which references a node one passed the end of the list.

int size() returns the number of elements in the list

bool empty() returns true if the list is empty, and false otherwise.

void push_front(const T& elt) adds the element elt at the beginning of the list.

void push_back(const T& elt) adds the element elt at the end of the list.

iterator insert(iterator pos, const T& elt) inserts the element elt at the position pointed to by pos. The return value references to position that contains the inserted element. Note that this will not be the same as pos because a new element has been inserted.

void pop_front() erases the first element in the list

void pop_back() erases the last element in the list

void erase(iterator pos) erases the element of the list pointed to by pos

void remove(const T& value) removes all elements in the list that are equal to value.

void sort() sorts the list according to the operator < of type T. Note that the generic sort function cannot be used on a linked list because it only works on contiguous memory.

Alert: The STL code for list and other classes generates a number of incomprehensible warning messages when you compile your code using our compiler. You can eliminate these by putting this line at the top of your code.
#pragma warning (disable : 4786)

Exercise 1: Create a list of lists of integers. Insert three lists of integers into this list, each of which has three integers (use your favorite integers for this). Then iterate through the list, printing the contents of each of the three lists. Note that you will need two iterators, one for the list of lists and one for the lists.

Stacks, Queues, and PriorityQueues in STL

STL also supports other data structures. The code for a stack is in the include file stack. There is a minor difference between the implementation of the STL stack and the more traditional stack. The pop() member function is of type void; it removes the top item but does not return it. There is another function T top() which returns the top element but does not remove it from the stack. Thus, to implement the traditional pop function, you need to call both top and pop. The stack class also has a push(T item) member function which works in the standard way, and a size() member function which returns the number of elements in the stack. Here is a short example.

#include <stack>
#include <iostream>
using namespace std;

int main()
{
    int thedata[] = {45, 34, 56, 27, 71, 50, 62};
    stack <int> s;
        int i;
    for (i=0;i<5;i++)
        s.push(thedata[i]);
    cout << "The stacksize is " << s.size() << endl;
    for (i=0;i<3;i++) {
        cout << s.top() << endl;
        s.pop();
    }
    for(i=5;i<7;i++)
        s.push(thedata[i]);
    for (i=0;i<4;i++) {
        cout << s.top() << endl;
        s.pop();
    } 
    return 0;
}

The queue class has the following member functions:

void push(T item)

adds an item to the end (tail) of the queue.

T front()

returns the item at the front (head) of the queue.

void pop()

removes the item at the fron (head) of the queue.

int size()

returns the number of items in the queue.

Here is a short program which demonstrates the queue class.

#include <queue>
#include <iostream>
using namespace std;

int main()
{
    int thedata[] = {45, 34, 56, 27, 71, 50, 62};
    queue<int> q;
        int i;
    for (i=0;i<5;i++)
        q.push(thedata[i]);
    cout << "The queuesize is " << q.size() << endl;
    for (i=0;i<3;i++) {
        cout << q.front() << endl;
        q.pop();
    }
    for(i=5;i<7;i++)
        q.push(thedata[i]);
    for (i=0;i<4;i++) {
        cout << q.front() << endl;
        q.pop();
    } 
    return 0;
}

There is also a class priority_queue which stores its items in sorted order. The basci member functions are the same as for stack (push, pop, top, size). You must include two header files, queue and functional. Here is a short sample.

#include <iostream>
#include <queue>
#include <functional>
using namespace std;

int main()
{
     priority_queue<int> pq;

     pq.push(23);
     pq.push(17);
     pq.push(34);
     pq.push(21);
     pq.push(30);
     cout << pq.top() << endl;  // prints 34
     pq.pop();
     cout << pq.top() << endl;  // prints 30
     pq.pop();
     return 0;
}

The STL set Class

There is no STL class called a tree. This makes sense because a tree is an implementation of the ADT set. There are several different set container classes in STL, the simplest of which is set. Here is the prototype:

#include <set.h>
template <class Key, class Compare>
class set;

A set is implemented as a tree (actually a much more sophisticated tree that the binary search tree that you have seen), but this allows rapid retrieval. The operations $==$ and $<$ must be defined on the class Key. The class Compare can be either less or greater. These are template functions and so the type must be enclosed in $< .. >$ operators.

An iterator for a set iterates through the set of values in sorted order (ascending if the second argument is less, descending if the second argument is greater). The operators $++$ and $--$ are defined on an iterator as is the defererening operator $*$. However, like list iterators, you cannot add an arbitrary amount to a set iterator. If i is a set iterator, the operation *(i+3) is not allowed.

Here are some of the member functions in set.

int size();
iterator end();
iterator begin();
void insert(const T& x);
void erase(iterator i);
iterator find(const T& x);

Note that there is no push_back() or push_front member functions because items are inserted in their proper place in the set.

Here is a short example. It defines a class String and overloads the $<$ and $==$ operators for it. In main, a set of type String called Dwarfs is declared. Seven strings are added to the set, and then an iterator goes through the set and each member is printed. Even though the strings are inserted into the set in random order, they are retrieved in sorted order because the iterator on a set iterates through the tree in InOrder.

#pragma warning (disable : 4786)
#include <set>
#include <string.h> // for strcpy, strcmp
#include <iostream>
using namespace std;
class String {
  private:
     char *s;
   public:
     String(){s=NULL;}
     String(char *ss) {
         s = new char[strlen(ss)+1];
         strcpy(s,ss);
     }
     ~String() {
         if (s != NULL) {
             delete [] s;
         }
     }
     String(const String& oldstring) {
          s = new char[strlen(oldstring.s)+1];
          strcpy(s,oldstring.s);
     }
     String operator = (const String &oldstring) {
         if (s != NULL) delete [] s;
         s = new char[strlen(oldstring.s)+1];
         strcpy(s, oldstring.s);
         return *this;
     }
     char *GetString() {return s;}
     bool operator==(const String &s1) {
          if (strcmp(s1.s,s)==0) return true;
          else return false;
      }
      bool operator>(const String &s1) {
          if (strcmp(s1.s,s) > 0) return true;
          else return false;
      }
      friend bool operator<(const String&, const String&);
      friend bool operator==(const String&, const String&);
 };

bool operator<(const String& s1, const String& s2) {
      if (strcmp(s1.s,s2.s) < 0) return true;
      else return false;
  }

bool operator==(const String& s1, const String& s2) {
      if (strcmp(s1.s,s2.s) ==  0) return true;
      else return false;
  }

int main()
{
   set<String,less<String> > Dwarfs;
   char *values[]={"Grumpy","Happy","Doc","Sleepy",
                   "Bashful","Dopey","Sneezy"};
   for (int i=0;i<7;++i) {
       String temp(values[i]);
       Dwarfs.insert(temp);
   }
   set<String, less<String>  >:: iterator it;
   String temp2;
   for(it = Dwarfs.begin();it != Dwarfs.end();it++) {
      temp2= *it;
      cout << temp2.GetString() << endl;
  }
   return 0;
}

The output of this program is

Bashful
Doc
Dopey
Grumpy
Happy
Sleepy
Sneezy

A set assumes that all keys are unique. There is also a class multiset which can store multiple copies of the same key.

The STL map class

A map is an associative container that supports unique keys of a given type Key and provides for fast retrieval of another type T based on the stored keys. The ordering relation Compare is used to order the elements of the map.

Here is the prototype

#include <map>
template <class Key, class T, class Compare>
class map

Note that this is a template with three classes. Elements are stored in pairs in sorted order by Key according to the comparison function Compare. It is possible to iterate through a map in order by key value using an iterator, just as for a set.

The dereferencing operator on a map iterator references a class of type pair. This is an STL class which has two fields, first and second. The first field contains the key value, and the second field contains the value associated with the key.

The map class has the $[ ]$ operator defined on it. Unlike an array or vector, in which the only type allowed between the square brackets is an integer, in the case of a map, the data type enclosed is the type of the key. For example, here is a declaration of a map to store phone numbers based on names.

map<string, long, less<string> > phone_numbers;

The class string is simply a character string with the $<$ and $==$ operators overloaded for it.

The following statement will insert a new phone number into the map

phone_numbers["Mickey Mouse"] = 7639001;

Here is how you would get Mickey's phone number.

long n = phone_numbers["Mickey Mouse"];

If you iterate through a map from beginning to end, the order will be entries sorted by key value (ascending order if the Compare function is less, descending order if the Compare function is greater). Here is the code to iterate through a map. Note the use of first and second to get the two values.

   map<string, int, less<string> >:: iterator i;
   for(i = phone_numbers.begin();i != phone_numbers.end();i++)
       cout << "The phone number of " << (*i).first << " is "
            << (*i).second << endl;

The complete program is in /dept/cs/cs2/wksht21/map.cpp. Here is the code.

#pragma warning (disable : 4786)
#include <map>
#include <iostream>
#include <string.h>
using namespace std;
class String {
   private:
     char *s;
 public:
   String(){s=NULL;}
   String(char *ss) {
       s=new char[strlen(ss)+1];
       strcpy(s,ss);
   }
   String(const String &oldString) {
       s = new char[strlen(oldString.s)+1];
       strcpy(s, oldString.s);
   }
   ~String() {if (s != NULL) delete [] s;}
   String operator=(const String& oldString) {
       s = new char[strlen(oldString.s)+1];
       strcpy(s, oldString.s);
       return *this;
   }
   friend bool operator<(const String&, const String&);
   friend bool operator==(const String&, const String&);
   friend ostream& operator <<(ostream &, const String&);
  };

bool operator<(const String& s1, const String& s2) {
       if (strcmp(s1.s,s2.s) < 0) return true;
       else return false;
   }
bool operator==(const String& s1, const String& s2) {
       if (strcmp(s1.s,s2.s) == 0) return true;
       else return false;
   }
ostream& operator<<(ostream &os, const String &s1) {
    os << s1.s;
    return os;
}

int main()
{
   map<String, int, less<String> > phone_numbers;

   phone_numbers["Mickey Mouse"] = 7639001;
   phone_numbers["Donald Duck"] = 3429871;
   phone_numbers["Homer Simpson"] = 2348900;

   cout << "Donald Duck's phone number is " << phone_numbers["Donald Duck"]
        << endl;

   map<String, int, less<String> >:: iterator i;
   for(i = phone_numbers.begin();i != phone_numbers.end();i++)
       cout << "The phone number of " << (*i).first << " is "
            << (*i).second << endl;

   i = phone_numbers.find("Mickey Mouse");
   phone_numbers.erase(i);
   return 0;
}

Most of the other standard member functions are also defined for a map. The insert function takes a pair as an argument, but it is seldom used because the $[ ]$ syntax is so much easier and does the same thing. There is a find function that takes a key value as an argument and returns an iterator which points to entry with that key value. There is an erase function which takes an iterator as an argument and removes that entry from the map.

Maps must have all keys unique. There is also a class multimap which allows duplicate keys.