A Bag example

The tutorial ``Associative Arrays in C++ - Map(C++)'' develops a short program that uses a Map(C++) to count how many times each distinct word occurs in its input:

       #include <String.h>
       #include <Map.h>
       #include <iostream.h>
       main() {
           Map<String,int> count;
           String word;

           while (cin >> word)
                   count[word]++;
           cout << "COUNT\ tWORD\ n\ n";
           Mapiter<String,int> p(count);
           while (++p)
               cout << p.value() << "\ t"
                    << p.key() << endl;
       }

If lexicographic ordering of the output is not important (for example, if we are concerned only with knowing how many times each word occurs), then a Bag<String> offers just the functionality needed:

       #include <String.h>
       #include <Set.h>
       #include <iostream.h>
       main(){
           Bag<String> count;
           String word;

           while(cin >> word){
               count.insert(word);
           }
           Bagiter<String> bi(count);
           const Bag_pair<String>* p;
           cout << "COUNT\ tWORD\ n\ n";

           while(p = bi.next()){
               cout << p->count << "\ t"
                    << p->value << "\ n";
           }
       }
       Set_or_Bag_hashval Bag<String>::hash(const String& s){
           return ((Set_or_Bag_hashval)s.hashval());
       }

First note that the header file Set.h contains the definitions needed to declare and implement Bags as well as Sets and pointer sets. Like the Set<>, the Bag<String> needs a hash function, which we implement using String's own hash function. (The String(C++) hash function is not perfect, but it is fast and does quite a good job.) Bag iterators return pointers, not to elements, but to pairs consisting of an element and its multiplicity. Running this program on an input stream consisting of this sentence alone gives:

            COUNT   WORD
           1       an
           1       stream
           1       of
           1       gives:
           2       this
           1       Running
           1       consisting
           1       sentence
           1       on
           1       alone
           1       input
           1       program

Compare this with the output of the Map version:

           COUNT   WORD
           1       Running
           1       alone
           1       an
           1       consisting
           1       gives:
           1       input
           1       of
           1       on
           1       program
           1       sentence
           1       stream
           2       this

As expected, the only difference is that the Map version produces sorted output. We will look at the performance of these two programs in the section, ``Space-time tradeoffs''.