The member functions of the Collection Class Library call other functions to manipulate elements and keys. These functions are called element functions and key-type functions, respectively.
Member functions of the Collection Class Library may, for example, use the element's assignment or copy constructors for adding an element, or they may use the element's equality operator for locating an element in the collection. In addition, Collection Class functions use memory management functions for the allocation and deallocation of dynamically created internal objects (such as nodes in a tree or a linked list).
The element functions that may be required by a given collection are:
This list is the superset of all element functions and key-type functions that a Collection Class can ever require. For example, a collection without keys does not require any key-type functions, and a collection without element equality does not require an equality test.
The key-type functions that may be required by a given collection are:
Where possible, these functions are already defined by the Collection Class Library. Default memory management functions are provided for usage with any element and key type. For the standard C++ data types int and char*, defaults are offered for all element and key-type functions. For all other element and key types, you must provide these functions.
Note: For implementation variants where both equality test and ordering relation are required element functions (or where both are required key-type functions), the library does not define which of the two is used to determine element or key equality.
You can define these functions in three ways:
Note: Some collections may require allocation and deallocation functions. The second and third methods can also be used to replace the default memory management functions for some of the collections.
The easiest way to provide the required element or key-type functions is to use member functions. For assignment, equality, and ordering relation, operator=, operator==, and operator< are used, respectively. Certain element functions and key-type functions must be defined as member functions. Others cannot be defined as member functions, but must be defined as separate functions.
You must define these functions using member functions:
Except for assignment, you must define member functions of a class as const. You will get a compile-time error if you do not include const in these definitions.
The following example shows how member functions must be defined as const:
class Element {
public:
Element& operator= (Element const&);
IBoolean operator== (Element const&) const;
IBoolean operator< (Element const&) const;
};
The Collection Class Library does not check or use the return type of operator=(). The return type of equality and ordering relation must be compatible with type IBoolean.
You can use global functions to provide the required element and key functions. A global function is a function that is not a member of any class. Use global functions when, in instantiating the Collection Class, you have no control over the element class and the element class does not define the appropriate functions.
The following functions must be defined as global functions that are not members of any class:
The following shows what the declarations for these global functions must look like:
void assign (Element&, Element const&); IBoolean equal (Element const&, Element const&); long compare (Element const&, Element const&); Key const& key (Element const&); unsigned long hash (Element const&, unsigned long); IBoolean equal (Key const&, Key const&); long compare (Key const&, Key const&); unsigned long hash (Key const&, unsigned long);
You can also use global functions for the standard memory management functions, as defined by the C++ language:
void* operator new (size_t); void operator delete (void*);
The compare function must return a value that is less than, equal to, or greater than zero, depending on whether the first argument is less than, equal to, or greater than the second argument.
The hash function must return a value that is less than the second argument; this value may be achieved, for example, by computing the remainder (operator%) with the second argument. The hash function should evenly distribute over the range between zero and the second argument. For equal elements or keys, the hash element must yield equal results.
Note: An efficient hash function is very important to the performance of your program.
For assign, equal, and compare, template functions are defined that will be instantiated unless otherwise specified. The default for assign uses the assignment operator, the default for equal uses the equality operator, and the default for compare uses two comparisons with operator<. It is therefore advisable to define your own compare function if the given element type has a more efficient implementation available. Such definitions are already provided for integer types using operator- and for char* using strcmp. By default, the standard memory management functions are used. (Using operator- works for integer types because the result of a-b can be used to determine whether a<b evaluates to true.)
The following examples demonstrate the use of a global function for the definition of the key access. The element class is Person, its data member PersonName is the key, and its member function GetPersonName is used to access the key.
The example below is the header file:
//person.h - header file containing class Person
#include <iostream.h>
#include <istring.hpp>
class Person {
IString PersonName; //This will be used as the key
IString TNumber;
public:
//constructor
Person() : PersonName(""), TNumber("") {}
//copy constructor
Person(IString Name, IString Number)
: PersonName(Name), TNumber(Number)
{
}
IString const& GetPersonName() const { return PersonName; }
IString const& GetTNumber() const { return TNumber; }
IBoolean operator== (Person const& A) const
{
return (PersonName == A.GetPersonName()) &&
(TNumber == A.GetTNumber());
}
IBoolean operator<(Person const& A) const
{
return (PersonName < A.GetPersonName());
}
};
ostream& operator<<(ostream& os,Person A);
// Use separate function Key const& key (Element const&);
inline IString const& key (Person const& A) //Key access
{
return A.GetPersonName();
}
The example below is the main file.
//main.cpp - main file
#include "person.h" //person.h from the previous example
#include <ikeyset.h>
typedef IKeySet <Person,IString> AddressList;
ostream& operator<<(ostream& os,Person A)
{
return (os << endl << A.GetPersonName() << " " <<
A.GetTNumber());
}
void main()
{
AddressList Business;
AddressList::Cursor myCursor(Business);
Person A("Peter Black","714-50706");
Person B("Carl Render","714-540321");
Person C("Sandra Summers","x");
Person D("Mike Summers","x");
Business.add(A);
Business.add(B);
Business.add(C);
Business.add(D);
Business.removeElementWithKey("Carl Render");
forICursor(myCursor) {
cout<<Business.elementAt(myCursor);
}
}
You can use element operation classes in cases where you want to place elements of one type into more than one collection, and where the element or key-type functions are different for each collection. For example, suppose you require an element type that is used to instantiate employee records that can be sorted either by name or by salary. You can declare an element class Person, and then place references to each Person instance into each of two collections. In one collection, the key is the name; in the other, the key is the salary. In your program, you need to define different element and key-type functions for hashing, comparison, and so on. Because these functions are not identical for both collections, you cannot define them within the class Person.
You can provide different sets of element and key-type functions for a given element type and multiple collections, by using the IG... class template for the collection you want to use. This class template lets you define element functions separately from the element class. In the case of the employee program, you can declare two classes as follows:
IGKeySortedSet <PersonPtr, int, SalaryOps> SalaryKSet; IGKeySortedSet <PersonPtr, IString, NameOps> NameKSet;
You then need to define two other classes, SalaryOps and NameOps, which must contain appropriate element and key-type functions.
When you do not provide element or key operations by using an IG... collection, the standard class template (I... as opposed to IG...) defines default operations. These default operations are declared in istdops.h.
The following excerpt shows the definition of the class templates for ISequenceAsList and IGSequenceAsList:
template < class Element, class ElementOps >
class IGSequenceAsList { /* ... */ };
template < class Element >
class ISequenceAsList
: public IGSequenceAsList<Element, IStdOps<Element>>
{
/* ... */
};
The advantage of passing the arguments using an extra class instead of passing them as function pointers is that the class solution allows inlining.
The following is a skeleton for operation classes. The keyOps member must only be present for key collections. Note that all element and key operations must be defined as const.
template <class Element, class Key>
class ...Ops {
public:
void* allocate (size_t) const;
void deallocate (void*) const;
void assign (Element&, Element const&) const;
IBoolean equal (Element const&, Element const&) const;
long compare (Element const&, Element const&) const;
Key const& key (Element const&) const;
unsigned long hash (Element const&, unsigned long) const;
class KeyOps
{
IBoolean equal (Key const&, Key const&) const;
long compare (Key const&, Key const&) const;
unsigned long hash (Key const&, unsigned long) const;
} keyOps;
};
You can inherit from the following class templates when you define your own operation classes. Templates with argument type T can be used for both the element and the key type.
class IStdMemOps {
public:
void* allocate (size_t) const;
void deallocate (void*) const;
};
template < class T >
class IStdAsOps
{
void assign (T&, T const&) const;
};
template < class T >
class IStdEqOps
{
IBoolean equal (T const&, T const&) const;
};
template < class T >
class IStdCmpOps
{
long compare (T const&, T const&) const;
};
template < class Element, class Key >
class IStdKeyOps
{
Key const& key (Element const&) const;
};
template < class T >
class IStdHshOps
{
unsigned long hash (T const&, unsigned long) const;
};
The file istdops.h defines the above templates. It also defines other templates that combine the properties of one or more of the templates.
One of the C++ language rules states that function template instantiations are considered before conversions. Because the Collection Classes define default templates for element functions, functions such as equal or compare, defined for a class, will not be considered for that class's derived classes; the default template functions will be instantiated instead. In the following example, the compiler would attempt to instantiate the template compare function for class B, instead of inheriting the compare function of class A and converting B to A:
class A {
// ...
};
long compare(A const&, A const&);
class B : public A {
// ...
};
ISortedSet<B> BSet;
The instantiated default compare function for class B uses the operator< of B. If no operator< for B can be found, a compilation error occurs. You must define standard functions such as equal or compare for the actual element type B to prevent the template instantiation of those functions, in case you want to provide a class-specific equal or compare function for B.
Introduction
to the Collection Classes
Collection
Class Hierarchy
Overall
Implementation Structure
Element
Functions and Key-Type Functions
Collection
Class Polymorphism
Ordering
of Collection Elements
Access
by Key
Equality
Relation
Uniqueness of Entries
Smart
Pointers
Using Element Pointers
Possible
Implementation Paths
Choosing One of the
Provided Implementation Variants
Instantiating the
Collection Classes
