CS 39 -- Sample STL use

Below are some samples of code that use STL data structures. They are meant to give you a basic picture (particularly syntax-wise) of how to use what STL provides. Use these at your own risk: They are reliable, but also somewhat complex and hard to debug if you don't take the time to understand how they work.

If you want more documentation about STL, how to use it, and what's available, check out some STL documentation. It's not light reading, but it can be helpful once you get your brain wrapped around their descriptions.

Linked lists

Below is an example of using a linked list, provided by STL. In this example, I will specify that a list of int is to be stored. Notice that the wierd looking iterator type is actually a subclass of the list class, and is a kind of "smart pointer" to node in the list. It's smart because if you use the ++ or -- operators on it, it will move to the next or previous element in the list.

#include <iostream.h> // C++ I/O routines
#include <list.h>     // The STL list class

int
main () {

  // Create a new, empty linked list of int.
  list<int> x;

  // Insert two items at the front of this list.
  x.push_front(5);
  x.push_front(3);

  // Insert an item at the end of the list.
  x.push_back(4);

  // Show all of the items now in the list.
  list<int>::iterator i;
  for (i = x.begin(); i != x.end(); i++) {
    printf("%d - ", *i);
  }
  printf("\n");

  // Find the element with the value 5.
  bool found = false;
  i = x.begin();
  while (!found && (i != x.end())) {

    if (*i == 5) {
      found = true;
    } else {
      i++;
    }
  }

  // If the 5 was found, delete it from the list.
  if (found) {
    x.erase(i);
  }

  // Show the list again.
  for (i = x.begin(); i != x.end(); i++) {
    printf("%d - ", *i);
  }
  printf("\n");

  return 0;

}
    

Hash map

What we usually call a hash table is actually know in STL-speak as a hash map. There are other variants that use the hashing idea to allow a program to trace space for fast lookup, but this one seems most applicable to our work so far.

The example shown below was actually taken from the STL documentation listed above. It is, in some ways, an overly simple example, but it could be enough to get things rolling. The syntax isn't easy, and this container class isn't for the faint of heart, but it is something that you could try out. If you seem to have control of it, then it could later save you lots of time writing hash-table code.

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) == 0;
  }
};

int main()
{
  hash_map<const char*, int, hash<const char*>, eqstr> months;
  
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;

  printf("september -> %d\n", months["september"]);
  printf("april     -> %d\n", months["april"]);
  printf("june      -> %d\n", months["june"]);
  printf("november  -> %d\n", months["november"]);
}