|
|
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.