|
Die Klassenbibliotheken der C++Compiler enthalten zwar sehr leistungsfähige Konstruktionen wie Dictionary, Bag und auch einen leistungsfähigen und flexiblen Set, aber speziell für kleine Mengen mit bis zu 256 Elementen sind diese universell angelegten Lösungen nicht besonders effizient.
| Leistungsfähigkeit, Flexibilität und Effizienz |
|
In unserer Implementierung wird pro Element der Menge ein Bit verbraucht, also gehen 8 Elemente in ein Byte. Alle Elemente der gewünschten Menge werden also in 32 Bytes gepackt untergebracht. Als Hilfsimplementierung, um unsere Menge übersichtlicher zu gestalten, greifen wir auf die Konstruktion eines BitSet zurück.
Die Hilfsklasse BitSet
| Hilfsimplementierung |
|
Die Menge BitSet hat Platz für 8 Elemente, die man sich wie die einzelnen Schalter einer DIP-Switch-Schalterleiste vorstellen kann, wenn sie von 0 bis 7 bezeichnet sind. Das Element i ist in der Schalterleiste enthalten, wenn das Bit i gesetzt ist, dieser Schalter also auf on steht.
| DIP-Switch |
BitSet (void )
Konstruktor für die „Leere Menge“, d. h. alle Bits werden auf 0 gesetzt. Es ist kein Element in der Menge vorhanden.
| Konstruktor für leere Menge |
BitSet( unsigned char )
Konstruktor für eine „einelementige Menge“. Es wird ein Element in die Menge eingetragen, das als Argument für den Konstruktor angegeben wird.
| Konstruktor für einelementige Menge |
BitSet( BitSet& )
Die Menge wird mit einer anderen Menge initialisiert. Wird vom Compiler gebraucht, wenn er Kopien der Menge anfertigen will.
| Kopier-Konstruktor |
int inset( unsigned char )
Mit der Methode Inset kann geprüft werden, ob ein Element in der Menge enthalten ist. Als Argument ist „unsigned char“ angegeben, obwohl nur Werte von 0 bis 7 sinnvoll sind. Für andere Argumente ist das Ergebnis undefiniert. Wenn das Element in der Menge ist, so wird 1 zurückgegeben, sonst 0.
Operatoren
| Methode Inset |
operator =( BitSet& )
Der Zuweisungsoperator weist eine Menge vom Typ „BitSet“ einer anderen zu. Das Ergebnis ist eine exakte Kopie der Menge, d. h. alle Werte, die in der ursprünglichen Menge vorhanden waren, sind in der Zielmenge nach der Operation auch enthalten, alle anderen nicht.
| Zuweisungs-operator |
operator =( unsigned char)
Erlaubt eine Zuweisung eines Zeichens an den BitSet. Dieser Operator könnte auch wegfallen, und trotzdem wäre die Zuweisung noch möglich, da ein Konstruktor für „unsigned char“ vorhanden ist. Allerdings würde dann das Zeichen erst in einen BitSet umgewandelt und dann zugewiesen.
| Überladener Zuweisungsoperator |
operator +( BitSet& )
Zwei BitSets werden zusammengeworfen, d. h. alle Bits die in dem einen oder anderen BitSet enthalten sind, sind danach im Ergebnis-BitSet enthalten (logisches inklusiv-oder).
| Vereinigungs-operator |
operator +=( BitSet& )
Vereinigung mit dem aktuellen BitSet („Hinzufügen“). Alle Bits, die im als Argument angegebenen anderen BitSet enthalten sind, sind danach auch im aktuellen BitSet enthalten.
| Hinzufügungs-operator |
operator *( BitSet& )
Zwei BitSets werden verglichen (logisches und), wobei nur diejenigen Bits im Ergebnis enthalten sind, die in beiden Argumenten vorkommen.
| Schnittmengen-operator |
operator *=( BitSet& )
Aus dem aktuellen BitSet werden nur diejenigen Elemente beibehalten, die auch im Argument enthalten sind. Es werden keine Elemente hinzugefügt.
| Schnittmengen-operator |
operator -( BitSet& )
Das Ergebnis wird aus denjenigen Elementen gebildet, die in der ersten Menge enthalten sind und die in der zweiten Menge nicht enthalten sind (logisches exklusiv-oder).
| XOR-Differenzmengenoperator |
operator -=( BitSet& )
Aus der aktuellen Menge werden diejenigen Elemente entfernt, die in der zweiten enthalten sind (logisches exklusiv-oder).
Die Klasse CharSet
| XOR-Differenzmengenoperator |
|
Die Klasse CharSet hat, um ihre versprochene Funktionalität zu bekommen, nun nichts anderes zu tun, als die Kapazität der BitSet auf die versprochenen 256 Elemente zu erhöhen. Wie macht Sie dies? Nun, entweder konstruieren wir nach dem Vorbild der Klasse BitSet eine völlig neue Klasse mit einem „Bitfeld“ von 256 Bit Größe, oder wir nehmen einfach 32 unserer „DIP-Schalter“ unserer Klasse BitSet und bauen sie zusammen.
| Kapazität auf 256 Elemente erhöhen |
|
Die Wiederverwendung von Code feiert ihre ersten bescheidenen Triumphe. Die lokale Datenstruktur von CharSet ist also tatsächlich auf 32 (konstante BSIZE) Schaltern aufgebaut. Die Funktionalität der Operatoren entspricht derjenigen der Klasse BitSet praktisch vollständig. Die Zeichen +, * und - sind wieder für die Vereinigung, die Schnittmenge und die Differenzmenge verwendet worden.
Die Komplementmenge ist hier wie auch beim BitSet nicht implementiert. Sie kann aber beispielsweise aus der Differenz einer Menge, in der alle Bits gesetzt sind, mit der gewünschten Menge ermittelt werden.
| Funktionalität der Operatoren |
CharSet (void )
CharSet( char )
CharSet( CharSet& )
Diese Konstruktoren arbeiten wie die entsprechenden Konstruktoren der Klasse BitSet.
| Konstruktoren |
CharSet( char* )
Anders als bei BitSet (das ja nur eine Hilfsklasse ist) kann bei CharSet eine Reihe von Werten in Form einer Zeichenkette auf einmal zum Erzeugen eines CharSet eingesetzt werden. Um keine Abhängigkeiten zu schaffen, wird ein normaler „char *“, also eine beliebige Textkonstante oder Variable als Argument verwendet. Damit ist auch ein impliziter Konstruktor geschaffen, der jede Zeichenkette in einen CharSet umwandeln kann.
| Konstruktor für mehrere Zeichen |
int inset( unsigned char )
inset arbeitet wie BitSet, jedoch mit dem Unterschied, daß alle durch „unsigned char“ adressierbaren Werte von 0 bis 255 erlaubt sind. Wenn das Element in der Menge ist, so wird 1 zurückgegeben, sonst 0.
| Methode inset |
int subset( CharSet& )
Wenn das Argument eine Untermenge der aktuellen Menge ist, so wird 1 zurückgegeben, ansonsten 0. Eine Menge ist ihre eigene Untermenge. Das Argument muß keine echte Untermenge sein.
| Methode subset |
int superset( CharSet& )
Wenn das Argument eine Obermenge der aktuellen Menge ist, so wird 1 zurückgegeben, ansonsten 0. Eine Menge ist auch ihre eigene Obermenge. Das Argument muß keine echte Obermenge sein.
Operatoren
Die Operatoren entsprechen in der Basisfunktionalität den namensgleichen Operatoren der Klasse BitSet:
operator =( CharSet& )
operator =( unsigned char)
operator +( CharSet& )
operator +=( CharSet& )
operator *( CharSet& )
operator *=( CharSet& )
operator -( CharSet& )
operator -=( CharSet& )
| Methode superset |
|
Die Operatoren +, * und - erlauben im Gegensatz zu denen von BitSet auch, daß das jeweils als erstes angegebene Element entweder ein CharSet, ein char oder ein char* sein kann. Für Zuweisungsoperatoren oder mit ihnen verbundene Operatoren ist dies nicht möglich, da das empfangende Argument immer ein CharSet sein muß.
Testprogramm
Ein Testprogramm für die Operationen und Konstruktoren der Klasse CharSet kann natürlich nicht alle denkbaren Details der Implementation austesten. Es dient uns deshalb auch mehr zur Veranschaulichung der Leistungsfähigkeit der Klasse. Wie zu sehen ist, wurde eine Eingabe- oder Ausgabefunktion für die Menge CharSet nicht implementiert, weil die Sinnhaftigkeit und die Art der Ausgabe nicht klar war. Die Ausgabe der Elemente der Menge erfolgt deshalb über die explizite Prüfung aller denkbaren Elemente (0 bis 255) auf ihre Mengeneigenschaft.
| Erweiterungen
|
