Axel Rogat

Objektorientiertes Programmieren mit C++ und JAVA

15.1: Strings

Kapitel 15

16: Generizität

15.2 Teilmengen von int

Mengen (von Objekten beliebigen Typs) sind als Container-Klassen ähnlich wie Stacks und Arrays darstellbar. Wenn der zugrundeliegende Typ völlig allgemein gehalten ist (wenn es insbesondere keine Ordnungsrelation gibt), bleibt nichts weiter übrig, als die Objekte einer Menge (oder Zeiger bzw. Referenzen darauf) listenähnlich zu speichern. Will man feststellen, ob ein bestimmtes Element in der Menge enthalten ist, müssen ggf. alle Objekte angeschaut werden. Da ja auch kein Element doppelt vorkommen soll, muß auch beim Einfügen die Liste komplett nach Doppelgängern durchsucht werden.

Wir wollen eine wesentlich einfachere Klasse implementieren, nämlich iset für Teilmengen von int. Als Darstellung verwenden wir eine Art (selbstverwaltetes) Bitfeld. Für jedes mögliche Element einer Menge brauchen wir nämlich nur 1 Bit abzuspeichern, das genau dann gesetzt ist, wenn die Zahl in der Menge enthalten ist. Da int linear geordnet ist, sollten wir die Bits natürlich entsprechend anordnen, so daß die Speicheradresse des relevanten Bits direkt aus der Zahl berechenbar ist.

Der Zugriff auf die Enthaltenseins-Information etc. ist so sehr schnell. Außerdem lassen sich andere sinnvolle Operationen sehr schnell erledigen. Zur Bildung der Vereinigung etwa brauchen die beiden Bitdarstellungen nur mit logischem Oder verknüpft zu werden, beim Schnitt mit Und, etc.

Wenn wir allerdings alle möglichen int-Zahlen zulassen, benötigen wir bei 32-Bit-ints also 2³² Bits = 512 MByte für die Darstellung eines Objekts!

Dieser Zahlenbereich ist aber für die meisten Anwendungen weit übertrieben. Wir geben daher bei der Konstruktion einer Menge den maximal zulässigen Zahlenbereich an. Nach der Definition iset is(100); soll is Zahlen von 0 bis 99 aufnehmen können. Dazu brauchen wir nur 16 Bytes (aufgerundet von 12.5 bei 32-Bit-Speicherorganisation).

Abgesehen von Konstruktoren, Destruktor und Zuweisungsoperator sind die gewünschten Operationen:

Wir verwenden zur internen Darstellung ein dynamisches Array von unsigned long (statt z.B. char oder int), da die Verknüpfungen wie Vereinigung und Schnitt so möglichst schnell ablaufen können. In der statischen Variable longbits merken wir uns, wieviel Bits wir auf der jeweiligen Maschine tatsächlich in so einem Wort unterbringen können.

Den Komma-Operator überladen wir, um Mengen in der folgenden Art mit += Elemente hinzufügen zu können (analog entfernen mit -=):

iset m(32); m+=4,8,9,10; cout << m << endl; // Ausgabe: {4,8,9,10}

#ifndef ISET_H #define ISET_H

#include <iostream.h> class iset { private: int Range; unsigned long *data; int numlong; bool mode; static const int longbits; unsigned long &locate(int,unsigned long &) const; void allocate(unsigned long *); public: iset(int r) : Range(r), mode(true) { allocate(0); } iset(int,int *); iset(const iset& s) : Range(s.Range), mode(true) { allocate(s.data); } iset(const iset&, int, int); ~iset() { if (Range!=0) delete[] data; } int range() const { return Range; } bool operator [] (int i) const { unsigned long mask; return (locate(i,mask)&mask)!=0; } void empty(); int card() const; iset renumber(int,int *) const; iset& operator += (int i) { unsigned long mask; locate(i,mask)|=mask; mode=true; return *this; } iset& operator -= (int i) { unsigned long mask; locate(i,mask)&=~mask; mode=false; return *this; } iset& operator , (int i) { return mode?operator+=(i):operator-=(i); } bool operator == (const iset &) const; bool operator != (const iset &s2) const { return !(*this==s2); } iset& operator = (const iset &); iset& operator += (const iset &); iset& operator -= (const iset &); iset& operator *= (const iset &); iset operator ! () const; bool operator <= (const iset &) const; bool operator >= (const iset &) const; }; inline iset operator + (const iset &s1, const iset &s2) { iset temp(s1); return temp+=s2; } inline iset operator - (const iset &s1, const iset &s2) { iset temp(s1); return temp-=s2; } inline iset operator * (const iset &s1, const iset &s2) { iset temp(s1); return temp*=s2; } ostream& operator << (ostream &, const iset &); #endif

Wir bieten außerdem (im Hinblick auf spätere Anwendungen) einen Copy-Konstruktor an, bei dem eine neue Größe für den Wertebereich angegeben werden kann, sowie eine Verschiebedistanz. So kann beispielsweise die Menge {1,3,6} in {1,...,10} um 4 verschoben in {1,...,20} eingebettet werden mit dem Resultat {5,7,10} in {1,...,,20}.

Mit renumber können die Elemente in den Mengen umnumeriert werden, die neuen Nummern werden als Index-Vektor angegeben. Die Menge {1,2,3} in {1,...,5} wird mit dem Vektor (5,4,3,2,1) umnumeriert in {5,4,3}={3,4,5} in {1,...,5}

Es folgt die Implementationsdatei iset.cpp:

#include <iostream.h> #include <stdlib.h> #include <limits.h> #include "iset.h" const int iset::longbits=sizeof(unsigned long)*CHAR_BIT; static void error(char *str) { cout << "iset: " << str << endl; exit(0); } void iset::allocate(unsigned long *p) { if (Range<0) error("illegal range"); numlong=(Range+longbits-1)/longbits; if (Range!=0) { data=new unsigned long[numlong]; if (p==0) for (int i=0;i<numlong;++i) data[i]=0; else for (int i=0;i<numlong;++i) data[i]=p[i]; } } iset::iset(int r, int *p) : Range(r), mode(true) { int e; allocate(0); while ((e=*p++)>=0) *this+=(e); } iset::iset(const iset &s1, int newrange, int offset) : Range(newrange), mode(true) { if (newrange<s1.Range || s1.Range+offset>newrange) error("illegal shift copy constructor"); allocate(0); for (int i=0;i<s1.Range;++i) if (s1[i]) *this+=(i+offset); } iset& iset::operator = (const iset &s2) { if (Range!=s2.Range) { delete[] data; Range=s2.Range; allocate(s2.data); } else for (int i=0;i<numlong;++i) data[i]=s2.data[i]; return *this; } unsigned long & iset::locate(int i, unsigned long &mask) const { if (i<0 || i>=Range) error("illegal index"); mask=(1L<<(i%longbits)); return data[i/longbits]; } void iset::empty() { for (int i=0;i<numlong;++i) data[i]=0; } iset iset::renumber(int new_range, int *indices) const { iset n(new_range); for (int i=0;i<Range;++i) if ((*this)[i]) n+=indices[i]; return n; } int iset::card() const { int count=0; for (int i=0;i<numlong;++i) { unsigned long l=data[i]; for (int j=longbits;j>0;--j,l>>=1) if (l&1) ++count; } return count; } iset& iset::operator += (const iset& s2) { if (Range!=s2.Range) error("union with different ranges"); for (int i=0;i<numlong;++i) data[i]|=s2.data[i]; return *this; } iset& iset::operator -= (const iset& s2) { if (Range!=s2.Range) error("setminus with different ranges"); for (int i=0;i<numlong;++i) data[i]&=~s2.data[i]; return *this; } iset& iset::operator *= (const iset& s2) { if (Range!=s2.Range) error("section with different ranges"); for (int i=0;i<numlong;++i) data[i]&=s2.data[i]; return *this; } iset iset::operator ! () const { iset temp(Range); for (int i=0;i<numlong;++i) temp.data[i]=~data[i]; return temp; } bool iset::operator == (const iset &s2) const { if (Range!=s2.Range) return false; for (int i=0;i<numlong;++i) if (data[i]!=s2.data[i]) return false; return true; } bool iset::operator <= (const iset &s2) const { if (Range!=s2.Range) error("<= with different ranges"); for (int i=0;i<numlong;++i) if (data[i]&~s2.data[i]) return false; return true; } bool iset::operator >= (const iset &s2) const { if (Range!=s2.Range) error(">= with different ranges"); for (int i=0;i<numlong;++i) if (s2.data[i]&~data[i]) return false; return true; } ostream& operator << (ostream &o, const iset &s) { bool comma=false; o << '{'; for (int i=0;i<s.range();++i) if (s[i]) { if (comma) o << ','; o << i; comma=true; } return o << '}'; }

15.1: Strings

Startseite

16: Generizität