You'll notice that the collection class template RWTValDlist in the example follows a unique format. In Tools.h++, all templates have class names starting with RWT , for Rogue Wave Template, followed by a three-letter code:

Hence, RWTValOrderedVector<T> is a value-based template for an ordered vector of type-name T. RWTPtrMultiMap<Key,T,C> is a pointer-based template based on the Standard C++ Library multimap class. Special characteristics may also modify the name, as in RWTValSortedDlist<T,C>, a value-based doubly-linked template list that automatically maintains its elements in sorted order.

Tools.h++ collection class templates can be either value-based or pointer-based. Value-based collections use value semantics, maintaining copies of inserted objects and returning copies of retrieved objects. In contrast, pointer-based collections use reference semantics, dealing with pointers to objects as opposed to the objects themselves. See Chapter 10 for other examples of value and reference semantics.

Templates offer you a choice between value and reference semantics. In fact, in most cases, you must choose between a value-based or a pointer-based class; for example, either RWOrderedVectorVal, or RWOrderedVectorPtr.

Your choice depends on the requirements of your application. Pointer-based templates are a good choice for maximizing efficiency for large objects, or if you need to have the same group of objects referred to in several ways, requiring that each collection class point to the target objects, rather than wholly contain them.

// value-based list of RWDate pointers:
RWTValDlist<RWDate*> myBirthdayV;

RWDate* d1 = new RWDate(29,12,55);  // December 29, 1955
myBirthdayV.insert(d1);
RWDate* d2 = new RWDate(29,12,55);  // Different object, same date
cout << myBirthdayV.occurrencesOf(d2);   // Prints 0

RWTPtrDlist<RWDate> myBirthdayP;  // pointer-based list of RWDates
RWDate* d1 = new RWDate(29,12,55); // December 29,1955
myBirthdayP.insert(d1);
RWDate* d2 = new RWDate(29,12,55); // Different object, same date
cout << myBirthdayP.occurrencesOf(d2);   // Prints 1

For a collection class of type-name T, intrusive lists are lists where type T inherits directly from the link type itself^[13] . The results are optimal in space and time, but require you to honor the inheritance hierarchy. The disadvantage is that the inheritance hierarchy is inflexible, making it slightly more difficult to use with an existing class. For each intrusive list class, Tools.h++ offers templatized value lists as alternative non-intrusive linked lists.

Note that when you insert an item into an intrusive list, the actual item , not a copy, is inserted. Because each item carries only one link field, the same item cannot be inserted into more than one list, nor can it be inserted into the same list more than once.

A unique feature of this version of Tools.h++ is that many of its template collections do not actually require the presence of the Standard C++ Library. Consider RWTValDlist<T> If you are using Tools.h++ on a platform that supports the Standard C++ Library, RWTValDlist<T> will be built around the Standard C++ Library list container. But if your platform does not support the Standard C++ Library, you may still use the class. Tools.h++ accomplishes this feat transparently through an alternate implementation, not based on the Standard C++ Library. The appropriate implementation is selected at compile time based on the settings in the configuration header file, rw/compiler.h. In fact, the alternate implementations are exactly those that were employed in the previous version of Tools.h++.

When using one of these template collections without the Standard C++ Library, you will be restricted to a subset of the full interface. For example, the std() member function mentioned above is not available, nor are the begin() and end() functions, which return Standard C++ Library iterators. The Tools.h++ Class Reference contains entries for both the full and the subset interfaces for all of the templates that can be used either with or without the Standard C++ Library.

There are two reasons you may want to use the restricted subset interface for a collection class template:

There are seven Standard C++ Library containers: deque, list, vector, set, multiset, map, and multimap. Tools.h++ extends these with five additional containers which are compliant with the Standard C++ Library: rw_slist, rw_hashset, rw_hashmultiset, rw_hashmap, and rw_hashmultimap. Each of these has value-based and pointer-based Rogue Wave wrapper templates. Tools.h++ also offers always-sorted versions, both value-based and pointer-based, of the doubly-linked list and vector collections. The total: 28 new or re-engineered collection class templates, all based on the Standard C++ Library!

To keep things simple and allow you to program with more flexibility, we have implemented common interfaces within the various divisions of standard-library based collection class templates. For example, the RWTPtrSet and RWTPtrMultiSet templates have interfaces identical to their value-based cousins; so do the map-based collection classes. All of the Sequence-based collections have nearly identical interfaces within the value and pointer-based subgroups. (An exception here is the set of deque-based classes, which contain push and pop member functions designed to enhance their abstraction of the queue data structure.)

There are pluses and minuses to this approach. The downside is that it puts slightly more of the burden on you, the developer, to choose the appropriate collection class. Had we chosen not to provide the insertAt(size_type index) member function for class RWOrderedVectorVal<Type>, we could have enforced the idea that vector-based templates are not a good choice for inserting into the middle of a collection class. Instead, it is up to you to be aware of your choices and use such member functions judiciously.

On the plus side, the common interface lowers the learning curve, allows flexibility in experimenting with different collections, and provides the capability of dealing with the Rogue Wave templates polymorphically via genericity.^[14]

Real-life programming is seldom as neat as the exercises in a data structures textbook. You may find yourself in a situation where it is difficult to balance the trade-offs and determine just which collection class to use. With the common interface, you can easily benchmark code that uses an RWTValDeque and later benchmark it again, substituting an RWTValOrderedVector or RWTValDlist. You can also write class and function templates that are parameterized on the collection class type. For example:

template <class RWSeqBased>
void tossHiLo(RWSeqBased& coll) {
    // throw out the high and low values:
   assert(coll.entries() >= 2);  // precondition
   coll.sort();
   coll.removeFirst();
   coll.removeLast();
}

Thanks to the common interface, the above function template will work when instantiated with any of the Rogue Wave Sequence-based templates.

As noted above, the comparator must induce a total ordering on the type of the items in the collection class. This means that the function-call operator of the comparator must satisfy the following two conditions^[15] , assuming that comp is the comparison object and x, y, and z are potential elements of the collection class, not necessarily distinct:

I.  Exactly one of the following statements is true:
    a) comp(x,y) is true  and comp(y,x) is false
    b) comp(x,y) is false and comp(y,x) is true
    c) comp(x,y) is false and comp(y,x) is false 
      (or, in other words: not both comp(x,y) and comp(y,x) 
       are true)
II. If comp(x,y) and comp(y,z) are true, then so is 
    comp(x,z) (transitivity).

The truth of I.a implies that x must precede y within the collection class, while I.b says that y must precede x. More interesting is I.c. If this statement is true, we say that x and y are equivalent, and it doesn't matter in what order they occur within the collection class. This is the notion of equality that prevails for the templates that take a comparator as a parameter. For example, when the member function contains(T item) of an associative container-based template tests to see if the collection class contains an element equivalent to item, it is really looking for an element x in the collection class such that comp(x,item) and comp(item,x) are both false. It is important to realize that the == operator is not used. Don't worry if at first it seems counter-intuitive that so much negativity can give rise to equivalence—you are not alone! You'll soon be comfortable with this flexible way of ensuring that everything has its proper place within the collection class.

Comparators are generally quite simple in their implementation. Take for example:

class IncreasingLength {
public:
    bool operator()(const RWCString& x, const RWCString& y) 
    { return x.length() < y.length(); }
};
RWTValSet<RWCString,IncreasingLength> mySet;

Here mySet maintains a collection of strings, ordered from shortest to longest by the length of those strings. You can verify that an instance of the comparator satisfies the given requirements for total ordering. In the next example, mySet2 maintains a collection class of integers in decreasing order:

class DecreasingInt {
public:
    bool operator()(int x, int y) 
    { return x > y; }
};
RWTValSet<int, DecreasingInt> mySet2;

Although the sense of the comparison may seem backwards when you first look at it, the comparator says that x should precede y within the collection class if x is greater than y; hence, you have a decreasing sequence. Finally, let's look at a bad comparator:

// DON'T DO THIS:
class BadCompare {
public:
    bool operator()(int x, int y) 
   { return x <= y; }    // OH-OH! Not a total ordering relation
};
RWSetVal<int, BadCompare> mySet3;  // ILLEGAL COMPARATOR!

To determine why it's bad, consider an instance badcomp of BadCompare. Note that when using the value 7 for both x and y, none of the three statements I.a, I.b, or I.c is true, which violates the first rule of a total ordering relation.^[16]

All Tools.h++ standard library-based collection class templates provide standard iterators. These iterators are fully compliant with the Standard C++ Library requirements for iterators, making them a powerful tool for using the classes in conjunction with the Standard C++ Library—especially the algorithms. Although full treatment of iterators is beyond the scope of this guide, your Standard C++ Library reference and tutorials will provide ample information.

The standard library-based collection class templates provide three types of iterators: forward, bi-directional, and random-access. Forward iterators allow unidirectional traversal from beginning to end. As suggested by the name, bidirectional iterators allow traversal in both directions—front to back, and back to front. Random-access iterators are bidirectional as well, and further distinguished by their ability to advance over an arbitrary number of elements in constant time. All of these iterators allow access to the item at the current position via the dereference operator *.

Given iterator iter and an integral value n, the following basic operations are just some of those supported:

Again, your standard library documentation will describe all the operators and functions available for each type of iterator.

In addition to the iterators just described, the standard library-based collection class templates also provide two typedefs used to iterate over the items in a collection class: iterator, and const_iterator. You can use the iterator typedef to traverse a collection class and modify the elements within. You can use instances of const_iterator to traverse, but not modify, the collection class and access elements. For the associative container-based and sorted sequence-based collections, which do not allow modification of elements once they are in the collection class, the iterator and const_iterator types are the same.

Finally, the templates also provide two member functions that return actual iterators you can use for traversing their respective collection classes. These member functions are begin() and end(). Each of these member functions is overloaded by a const receiver so that the non-const version returns an instance of type iterator, and the const version returns an instance of type const_iterator.

Member function begin() always returns an iterator already positioned at the first item in the collection class. Member function end() returns an iterator which has a past-the-end value, the way a pointer to the NULL character of a null-terminated character string has a value that points "past the end." An iterator of past-the-end value can be used to compare with another iterator to see if you've finished visiting all the elements in the collection class. It can also be used as a starting point for moving backwards through collection classes that provide either bidirectional or random-access iterators. The one thing you cannot do with an end() iterator is dereference it. The one thing you cannot do with an end() iterator is deference it. Here's an example using iterators to move through a list and search for a match:

RWTValDlist<int> intCollection; // a list of integers
 
// ... < put stuff in the list >
 
// position iter at start: 
RWTValDlist<int>::iterator iter = intCollection.begin();
 
// set another iterator past the end:
RWTValDlist<int>::iterator theEnd = intCollection.end();
 
// iterate through, looking for a 7:
while (iter != theEnd) {       // test for end of collection
  if (*iter == 7)              // use `*' to access current element
    return true;               // found a 7
  ++iter;                      // not a 7, try next element
}
return false;                  // never found a 7

In the case of a map-based collection class, like RWMapVal<K,T,Compare>, iterators refer to instances of the Standard C++ Library structure pair<const K, T>. As you iterate over a map-based collection, you have access to both the key and its associated data at each step along the traversal. The pair structure provides members first and second, which allow you to individually access the key and its data, respectively. For example:

typedef RWTValMap<RWCString, RWDate, less<RWCString> > Datebook;
 
Datebook birthdays;
// ... < populate birthdays collection >
 
Datebook::iterator iter = birthdays.begin();
 
while (iter != birthdays.end()) {
  cout << (*iter).first              // the key
       << " was born on "
       << (*iter).second             // the data for that key
       << endl;
 
  ++iter;
};

Note that given a non-const reference to such a pair, you can still modify only the second element—the data associated with the key. This is because the first element is declared to be of type const K. Because the placement of objects within the collection class is maintained internally, based on the value of the key, declaring it as const protects the integrity of the collection class. In order to change a key within a map, you will have to remove the key and its data entirely, and replace them with a new entry.

It may not be obvious at first, but you can think of an iterator as a generalized pointer. Imagine a pointer to an array of ints. The array itself is a collection class, and a pointer to an element of that array is a random-access iterator. To advance to the next element, you simply use the unary operator ++. To move back to a previous element, you use --. To access the element at the current position of the iterator, you use the unary operator *. Finally, it is important to know when you have visited all the elements. C++ guarantees that you can always point to the first address past the end of an allocated array. For example:

int intCollection[10];                // an array of integers
 
// ... < put stuff in the array >
 
// position iter at start: 
int* iter = intCollection;
 
// set another iterator past the end:
int* theEnd = intCollection + 10;
 
// iterate through, looking for a 7:
while (iter != theEnd) {       // test for end of array
  if (*iter == 7)              // use `*' to access current element
    return true;               // found a 7
  ++iter;                      // not a 7, try next element
}
return false;                  // never found a 7

If you compare this code fragment to the one using standard iterators in Section 11.7.1XX, you can see the similarities. If you need a bit of help imagining how the standard iterators work, you can always picture them as generalized pointers.

The restricted subset interfaces are almost fully upward compatible with their corresponding standard library-based interfaces. The major difference you will find is that some collections take a different number of template parameters, depending on which underlying implementation they are using. For example, when RWTPtrHashSet is used with the Standard C++ Library, it takes three template arguments as described in "Hash Functors and Equalitors" above. However, when that same class is used without the Standard C++ Library, the restricted interface calls for only one template parameter, namely the type of item being contained. To help you write portable code that works with or without the Standard C++ Library, Tools.h++ provides two macros:

Let's start with a simple example that uses RWTValVector<T>, one of the classes that is not based on the Standard C++ Library.

#include <rw/tvvector.h>             // 1
 
main() {
    RWTValVector<double> vec(20, 0.0);                     // 2
 
    int i;
    for (i=0; i<10; i++)     vec[i] = 1.0;                 // 3
    for (i=11; i<20; i++)    vec(i) = 2.0;                 // 4
 
    vec.reshape(30);                                       // 5
    for (i=21; i<30; i++)    vec[i] = 3.0;                 // 6
    return 0;
    }

Each program line is detailed below.

The second example involves a hashing dictionary. By using the macro RWDefHArgs(T) when you declare the hashing dictionary, you insure that your code is portable with or without access to the Standard C++ Library.

#include <rw/cstring.h>
#include <rw/rstream.h>
#include <iomanip.h>
 
class Count {                                                  // 1
  int  N;
public:                                                        // 2
  int  operator++()  { return ++N; }                           // 3
  operator    int()  { return N; }                             // 4
};
 
unsigned hashString ( const RWCString& str )                   // 5
  { return str.hash(); }
 
main() {
 
  RWTValHashDictionary<RWCString,
                       Count  /* Note: no comma here! */
                       RWDefHArgs(RWCString)> hmap(hashString); //6
 
 
  RWCString token;
  while ( cin >> token )                                       // 7
    ++hmap[token];                                             // 8
 
  RWTValHashDictionaryIterator<RWCString,Count> next(hmap);    // 9
 
  cout.setf(ios::left, ios::adjustfield);                     // 10
  while ( ++next )                                            // 11
    cout << setw(20) << next.key()
         << " " << setw(10) << next.value() << endl;          // 12
 
  return 0;
}

Program Input:

How much wood could a woodchuck chuck if a woodchuck could chuck wood ?

Program Output:

much                 1
wood                 2
a                    2
if                   1
woodchuck            2
could                2
chuck                2
How                  1
?                    1

In the code above, the problem is to read an input file, break it up into tokens separated by white space, count the number of occurrences of each token, and then print the results. The general approach is to use a dictionary to map each token to its respective count. Here's a line-by-line description: