Example

It is often said that the only way to learn a programming language is to write programs in it, but it helps to have some examples.

Here is the promised customized List output function. First we declare a structure which will contain a String and the number of times it appears in the input:

   struct Pair {
      int    count;
      String name;
             Pair() {}
             Pair(String s) : name(s), count(1) {}
             Pair(const Pair& pp) : name(pp.name),
                 count(pp.count) {}
            ~Pair() {}
      Pair&  operator=(const Pair& pp) {
          name = pp.name;
          count = pp.count;
          return *this;
      }
      int operator==(const Pair& pp) {
          if(name == pp.name && count == pp.count)
               return 1;
          else return 0;
      }
   };
   ostream&
   operator<<(ostream& oo, const Pair& p) {
      oo << "Name: " << p.name << " count: " << p.count;
      return oo;
   }

The comparison operator is necessary in order for List<Pair> programs to compile. Here is the main program:

   main() {
      String s;
      List<Pair> myList;
      while (cin >> s)
          myList.put(Pair(s));
      cout << sort(myList) << "\0;
   }

This program uses the String operator>> function to separate the input stream into space-separated token Strings. It assumes a sort() function, which we show next.

   List<Pair>
   sort( List<Pair> aList ) {       // straight insertion
      Listiter<Pair>  unsorted(aList);
      if ( unsorted.step_next() ) {
          Pair p;
          while( unsorted.remove_next(p) ) {
              Listiter<Pair> sorted = unsorted;
              Pair *q;  // pointer into sorted part
              while( sorted.prev(q) && q->name > p.name )                ;
              if ( q->name < p.name )
                  sorted.step_next();   // back up
              else if ( q->name == p.name ) {
                  q->count++;
                  continue;
              }
              sorted.insert_next(p);
          }
      }
      return aList;
   }

This is a straight insertion sort The sort() routine uses a second pointer into the List to separate the sorted and unsorted parts. The routine works by removing each unsorted element and inserting it into its proper position in the sorted part of the List, unless it is found to equal one of the sorted elements. In case of equal, the count of that element is incremented instead. This is a good example of when List iterators can come in handy.