Die Menge ganzer Zahlen: Klasse IntegerSet

1. Aufgabe

Erstellen Sie eine Klasse IntegerSet, die eine Menge ganzer Zahlen mit zentralen Operationen wie das Einfügen oder Löschen von Elementen realisiert. In der Realisierung sollte zur Ablage der Zahlen ein dynamisch allokiertes Array verwendet werden. Obwohl Arrays in ihrer Größe limitiert sind, sollte die Klasse IntegerSet prinzipiell Mengen beliebiger Größen beherrschen.

Die Konstruktoren der Klasse IntegerSet haben wir in Tabelle 1 zusammengestellt:

Schnittstelle und Beschreibung

IntegerSet ();

Der Standardkonstruktor legt eine leere Menge an.

IntegerSet (int elements[], int count);

Durch den Parameter elements wird ein Array mit ganzen Zahlen der Länge count übergeben. Vor der Aufnahme der Werte in das Mengenobjekt ist zu überprüfen, ob diese alle verschieden sind.

Tabelle 1. Konstruktoren der Klasse IntegerSet.


Die öffentlichen Methoden der Klasse IntegerSet finden Sie in Tabelle 2 vor:

Methode

Schnittstelle und Beschreibung

Contains

bool Contains (int n) const;

Prüft das Vorhandensein eines Elements n in der Menge. Der Rückgabewert true bedeutet „Element ist in der Menge vorhanden“, false das Gegenteil.

Insert

bool Insert (int n);

Fügt eine ganze Zahl n in die Menge ein. Ist die Zahl in der Menge bereits enthalten, liefert Insert den Wert false zurück, andernfalls true.

Remove

bool Remove (int n);

Entfernt ein Element n aus der Menge. Ist die ganze Zahl in der Menge nicht enthalten, liefert Remove den Wert false zurück, andernfalls true.

Size

int Size () const;

Liefert die Anzahl der in der Menge enthaltenen Elemente zurück.

IsEmpty

bool IsEmpty () const;

Liefert bei einer leeren Menge true zurück, andernfalls false.

Tabelle 2. Öffentliche Methoden der Klasse IntegerSet.


Für elementare mengentheoretische Operationen wie das Bilden einer Vereinigungs- und Schnittmenge oder das Testen der Teilmengenrelation bietet sich die Realisierung durch Operatoren an. Tabelle 3 beschreibt die gängigsten Operatoren im Umfeld der elementaren Mengenlehre (sowie den Ausgabeoperator operator<<):

Methode

Schnittstelle und Beschreibung

operator+

friend IntegerSet operator+ (const IntegerSet& is1, const IntegerSet& is2);

Das Resultatobjekt ist die Vereinigungsmenge der beiden Operanden is1 und is2.

operator-

friend IntegerSet operator- (const IntegerSet& is1, const IntegerSet& is2);

Das Resultatobjekt ist die Differenzmenge der beiden Operanden is1 und is2.

operator^

friend IntegerSet operator^ (const IntegerSet& is1, const IntegerSet& is2);

Das Resultatobjekt ist die Schnittmenge der beiden Operanden is1 und is2.

operator+=

friend const IntegerSet& operator+= (IntegerSet& is1, const IntegerSet& is2);

Fügt alle Elemente des Mengenobjekts is2 zum Mengenobjekt is1 hinzu. Das Mengenobjekt is2 wird bei dieser Operation nicht verändert.

operator-=

friend const IntegerSet& operator-= (IntegerSet& is1, const IntegerSet& is2);

Entfernt im Mengenobjekt is1 alle Elemente, die im Mengenobjekt is2 enthalten sind. Das Mengenobjekt is2 wird bei dieser Operation nicht verändert.

operator<=

friend bool operator<= (const IntegerSet& is1, const IntegerSet& is2);

Prüft, ob die Menge is1 in der Menge is2 enthalten ist (Rückgabewert true) oder nicht (Rückgabewert false).

operator==

friend bool operator== (const IntegerSet& is1, const IntegerSet& is2);

Vergleicht zwei Mengenobjekte auf Gleichheit. Zu beachten ist: Die beiden Mengen { 1, 3, 5 } und { 5, 3, 1 } sind im Sinne der Mengentheorie gleich, die Reihenfolge ihrer Elemente spielt keine Rolle.

operator!=

friend bool operator!= (const IntegerSet& is1, const IntegerSet& is2);

Vergleicht zwei Mengenobjekte auf Ungleichheit.

operator[]

int operator[] (int index) const;

Ermöglicht den indizierten Zugriff auf ein Mengenobjekt. Mit Hilfe von Size und dem []-Operator lassen sich Elemente einer Menge einzeln aufzählen. Veränderungen an einem Mengenobjekt sollen konzeptionell nur mit Hilfe der beiden Methoden Insert und Remove erfolgen, aus diesem Grund ist der Rückgabewert von operator[] elementar und kein Referenztyp.

operator<<

friend ostream& operator<< (ostream&, const IntegerSet&);

Die Menge sollte im folgenden Format auf der Konsole ausgegeben werden:

{1, 2, 3, 4, 5}

Tabelle 3. Mengentheoretische Operationen und der Ausgabeoperator der Klasse IntegerSet.


Es folgen einige Hinweise zur Realisierung. Da ein IntegerSet-Objekt eine Menge beliebiger Größe beherbergen soll, müssen die Mengenelemente in einem dynamisch allokierten Datenbereich abgelegt werden, etwa einem mit new angelegten Array. Eine gangbare Implementierung der Klasse IntegerSet kommt folglich mit zwei Instanzvariablen aus, einer Zeigervariablen m_set, die die Adresse des dynamischen Datenpuffers enthält und einer zweiten Variablen m_num vom Typ int zur Beschreibung der Pufferlänge (Abbildung 1.1).

Instanzdatenbereich eines IntegerSet-Objekts mit einem dynamisch allokierten Datenpuffer.

Abbildung 1.1. Instanzdatenbereich eines IntegerSet-Objekts mit einem dynamisch allokierten Datenpuffer.


Bei jedem Einfügen und Entfernen von Mengenelementen stehen wir vor dem Problem, dass sich der Umfang der Menge verändert. Um den nachfolgenden Lösungsvorschlag möglichst elementar zu halten, beschreiten wir zunächst einen sehr einfachen Ansatz. Der dynamisch allokierte Puffer wird hierbei bei jeder Mengenoperation in seiner Größe exakt an die Anzahl der Mengenelemente angepasst. Dies hat zwar zur Folge, dass bei jedem Einfügen oder Entfernen von Mengenelementen intern ein neuer Puffer zu allokieren ist, dessen Elemente mit Ausnahme eines einzigen Elements identisch zum alten Puffer sind. Der Nachteil der daraus resultierenden unzufriedenstellenden Performance auf Grund der vielen new und delete-Aufrufe wird jedoch durch eine vergleichsweise einfache Implementierung ausgeglichen, wie wir in den nachfolgend vorgestellten Codelistings sehen werden. Die Arbeitsweise der Insert-Methode finden Sie in Abbildung 1 exemplarisch skizziert vor.

Arbeitsweise der Insert-Methode: Aufruf mit dem Aktualparameter 2.

Abbildung 1. Arbeitsweise der Insert-Methode: Aufruf mit dem Aktualparameter 2.


Beim Einfügen eines neuen Mengenelements ist intern ein neuer – um ein Element größerer – Datenpuffer zu allokieren. Der alte Datenpuffer ist Element für Element in den neuen Puffer zu kopieren, das neu einzufügende Element kann am Ende des neuen Datenpuffers abgelegt werden. Für das Entfernen eines Mengenelements geht man ähnlich vor (siehe Abbildung 2).

Arbeitsweise der Remove-Methode: Aufruf mit dem Aktualparameter 7.

Abbildung 2. Arbeitsweise der Remove-Methode: Aufruf mit dem Aktualparameter 7.


Ein Aufruf der Remove-Methode zieht wiederum das Allokieren eines neuen Datenpuffers nach sich, der dieses Mal um ein Element kleiner ist als der alte Puffer. Mit Ausnahme des zu entfernenden Elements sind alle Elemente des alten Puffers in den neuen Puffer umzukopieren. In Abbildung 3 können Sie die Arbeitsweise der beiden Methoden Insert und Remove an Hand des Codefragements

IntegerSet is;
is.Insert(1);
is.Insert(2);
is.Insert(3);
is.Remove(1);
is.Remove(2);

studieren.

Arbeitsweise der Insert- und Remove-Methode im Zusammenspiel.

Abbildung 3. Arbeitsweise der Insert- und Remove-Methode im Zusammenspiel.

2. Lösung

In Listing 1 finden Sie das Schnittstellendesign der Klasse IntegerSet vor, in Listing 2 eine Implementierung auf Basis der diskutierten Vorgehensweise:

01: class IntegerSet
02: {
03: public:
04:     // c'tors and d'tor
05:     IntegerSet ();
06:     IntegerSet (int elems[], int count);
07:     IntegerSet (const IntegerSet&);
08:     ~IntegerSet (); 
09: 
10: public:
11:     // getter
12:     int Size () const;
13:     bool IsEmpty () const;
14: 
15:     // public methods
16:     bool Insert (int);
17:     bool Remove (int);
18:     bool Contains (int) const;
19: 
20:     // miscellaneous operators
21:     IntegerSet& operator= (const IntegerSet&);
22:     friend bool operator== (const IntegerSet&, const IntegerSet&);
23:     friend bool operator!= (const IntegerSet&, const IntegerSet&);
24:     int operator[] (int) const; // read-only subscript operator
25: 
26:     // arithmetic-assignment operators
27:     friend const IntegerSet& operator+= (IntegerSet&, const IntegerSet&);
28:     friend const IntegerSet& operator-= (IntegerSet&, const IntegerSet&);
29: 
30:     // set theory specific operators
31:     friend IntegerSet operator+ (const IntegerSet&, const IntegerSet&);
32:     friend IntegerSet operator- (const IntegerSet&, const IntegerSet&);
33:     friend IntegerSet operator^ (const IntegerSet&, const IntegerSet&);
34:     friend bool operator<= (const IntegerSet&, const IntegerSet&);
35: 
36:     // output operator
37:     friend ostream& operator<< (ostream&, const IntegerSet&);
38: 
39: private:
40:     // private member data
41:     int  m_num;  // current number of elements
42:     int* m_set;  // array of elements
43: };

Beispiel 1. Klasse IntegerSet: Schnittstelle.


001: #include <iostream>
002: using namespace std;    
003: 
004: #include "IntegerSet.h"
005: 
006: // c'tors and d'tor
007: IntegerSet::IntegerSet ()
008: {
009:     // empty buffer
010:     m_num = 0;
011:     m_set = (int*) 0;
012: }
013: 
014: IntegerSet::IntegerSet (int elems[], int count)
015: {
016:     // empty buffer
017:     m_num = 0;
018:     m_set = (int*) 0;
019: 
020:     for (int i = 0; i < count; i ++)
021:         Insert (elems[i]);
022: }
023: 
024: IntegerSet::IntegerSet (const IntegerSet& is)
025: {
026:     // allocate buffer
027:     m_num = is.m_num;
028:     m_set = new int[m_num];
029: 
030:     // copy object
031:     for (int i = 0; i < m_num; i ++)
032:         m_set[i] = is.m_set[i];
033: }
034: 
035: IntegerSet::~IntegerSet ()
036: {
037:     delete[] m_set;
038: }
039: 
040: // getter
041: int IntegerSet::Size () const
042: {
043:     return m_num;
044: }
045: 
046: bool IntegerSet::IsEmpty () const
047: {
048:     return m_num == 0;
049: }
050: 
051: // public methods
052: bool IntegerSet::Contains (int n) const
053: {
054:     // search element
055:     for (int i = 0; i < m_num; i ++)
056:         if (m_set[i] == n)
057:             return true;
058: 
059:     return false;
060: }
061: 
062: bool IntegerSet::Insert (int n)
063: {
064:     // element already exists
065:     if (Contains (n))
066:         return false;
067: 
068:     // allocate new buffer
069:     int* tmp = new int[m_num + 1];
070: 
071:     // copy old buffer into new one
072:     for (int i = 0; i < m_num; i ++)
073:         tmp[i] = m_set[i];
074: 
075:     // insert new element at end of buffer
076:     tmp[m_num] = n;
077: 
078:     // switch to new buffer
079:     delete[] m_set;
080:     m_set = tmp;
081:     m_num ++;
082: 
083:     return true;
084: }
085: 
086: bool IntegerSet::Remove (int n)
087: {
088:     // element already exists
089:     if (! Contains (n))
090:         return false;
091: 
092:     // allocate new buffer
093:     int* tmp = new int[m_num - 1];
094: 
095:     // copy old buffer into new one
096:     for (int i = 0, k = 0; i < m_num; i ++)
097:     {
098:         if (m_set[i] == n)
099:             continue;
100: 
101:         tmp[k] = m_set[i];
102:         k ++;
103:     }
104: 
105:     // switch to new buffer
106:     delete[] m_set;
107:     m_set = tmp;
108:     m_num --;
109: 
110:     return true;
111: }
112: 
113: // operators
114: IntegerSet& IntegerSet::operator= (const IntegerSet& is)
115: {
116:     // prevent self-assignment
117:     if (this == &is)
118:         return *this;
119: 
120:     // delete old buffer
121:     delete[] m_set;
122: 
123:     // allocate a new buffer
124:     m_num = is.m_num;
125:     m_set = new int[m_num];
126: 
127:     // copy buffer
128:     for (int i = 0; i < m_num; i ++)
129:         m_set[i] = is.m_set[i];
130: 
131:     return *this;
132: }
133: 
134: bool operator== (const IntegerSet& is1, const IntegerSet& is2)
135: {
136:     // compare sizes
137:     if (is1.m_num != is2.m_num)
138:         return false;
139: 
140:     // compare both sets element per element
141:     for (int i = 0; i < is1.m_num; i ++)
142:     {
143:         if (is2.Contains (is1.m_set[i]))
144:             continue;
145: 
146:         return false;
147:     }
148: 
149:     return true;
150: }
151: 
152: bool operator!= (const IntegerSet& is1, const IntegerSet& is2)
153: {
154:     return ! (is1 == is2);
155: }
156: 
157: int IntegerSet::operator[] (int n) const
158: {
159:     // check parameter
160:     if (n < 0)
161:         return -1;
162:     if (n >= m_num)
163:         return -1;
164: 
165:     // return element
166:     return m_set[n];
167: }
168: 
169: // arithmetic-assignment operators
170: const IntegerSet& operator+= (IntegerSet& is1, const IntegerSet& is2)
171: {
172:     for (int i = 0; i < is2.m_num; i ++)
173:         is1.Insert (is2.m_set[i]);
174: 
175:     return is1;
176: }
177: 
178: const IntegerSet& operator-= (IntegerSet& is1, const IntegerSet& is2)
179: {
180:     for (int i = 0; i < is2.m_num; i ++)
181:         is1.Remove (is2.m_set[i]);
182: 
183:     return is1;
184: }
185:     
186: // set theory specific operators
187: IntegerSet operator+ (const IntegerSet& is1, const IntegerSet& is2)
188: {
189:     IntegerSet is(is1);
190:     for (int i = 0; i < is2.m_num; i ++)
191:         is.Insert (is2.m_set[i]);
192: 
193:     return is;
194: }
195: 
196: IntegerSet operator- (const IntegerSet& is1, const IntegerSet& is2)
197: {
198:     IntegerSet is(is1);
199:     for (int i = 0; i < is2.m_num; i ++)
200:         is.Remove (is2.m_set[i]);
201: 
202:     return is;
203: }
204: 
205: IntegerSet operator^ (const IntegerSet& is1, const IntegerSet& is2)
206: {
207:     IntegerSet is;
208: 
209:     for (int i = 0; i < is1.m_num; i ++)
210:     {
211:         int n = is1.m_set[i];
212:         if (is2.Contains (n))
213:             is.Insert (n);
214:     }
215: 
216:     return is;
217: }
218: 
219: bool operator<= (const IntegerSet& is1, const IntegerSet& is2)
220: {
221:     // compare both sets element per element
222:     for (int i = 0; i < is1.m_num; i ++)
223:     {
224:         int n = is1.m_set[i];
225:         if (! is2.Contains (n))
226:             return false;
227:     }
228: 
229:     return true;
230: }
231: 
232: // output operator
233: ostream& operator<< (ostream& os, const IntegerSet& is)
234: {
235:     os << "{";
236:     for (int i = 0; i < is.m_num; i ++)
237:     {
238:         os << is.m_set[i];
239:         if (i < is.m_num - 1)
240:             os << ',';
241:     }
242:     os << "} [" << is.m_num << "]";
243: 
244:     return os;
245: }

Beispiel 2. Klasse IntegerSet: Implementierung.


Zum Testen der Klasse zeigen wir exemplarisch die Testmethoden für die Konstruktoren und Operatoren:

001: #include <iostream>
002: using namespace std;
003: 
004: #include "IntegerSet.h"
005: 
006: void TestingCtorsDtor ()
007: {
008:     cout << "Testing c'tors / d'tor: " << endl;
009: 
010:     IntegerSet is1;
011:     cout << "is1: " << is1 << endl;
012: 
013:     int elems1[7] = { -2, -1, 0, 1, 2, -1, -2 };
014:     IntegerSet is2(elems1, 7);
015:     cout << "is2: " << is2 << endl;
016: 
017:     int elems2[11] = { -1, 1, 2, 3, 1, 2, 3, 1, 2, 3, -1 };
018:     IntegerSet is3(elems2, 11);
019:     cout << "is3: " << is3 << endl;
020: 
021:     IntegerSet is4(is3);
022:     cout << "is4: " << is4 << endl;
023: 
024:     cout << "is1.IsEmpty: " << is1.IsEmpty () << endl;
025:     cout << "is2.IsEmpty: " << is2.IsEmpty () << endl;
026:     cout << "is3.IsEmpty: " << is3.IsEmpty () << endl;
027:     cout << "is4.IsEmpty: " << is4.IsEmpty () << endl;
028: }
029: 
030: void TestingMethods ()
031: {
032:     cout << "Testing methods: " << endl;
033: 
034:     IntegerSet is;
035:     cout << "is: " << is << endl;
036: 
037:     // testing 'Insert'
038:     is.Insert (1);
039:     is.Insert (2);
040:     is.Insert (3);
041:     is.Insert (4);
042:     is.Insert (5);
043:     is.Insert (6);
044:     cout << "is: " << is << endl;
045: 
046:     // testing 'Remove'
047:     is.Remove (3);
048:     is.Remove (4);
049:     is.Remove (5);
050:     is.Remove (6);
051:     cout << "is: " << is << endl;
052: 
053:     is.Insert (10);
054:     is.Insert (11);
055:     is.Insert (12);
056: 
057:     is.Insert (13);
058:     is.Insert (14);
059:     is.Insert (15);
060:     is.Insert (16);
061:     is.Insert (17);
062:     is.Insert (18);
063:     is.Insert (19);
064:     is.Insert (20);
065:     is.Insert (21);
066:     is.Insert (22);
067:     is.Insert (23);
068:     cout << "is: " << is << endl;
069: 
070:     is.Insert (24);
071:     cout << "is: " << is << endl;
072: 
073:     is.Remove (11);
074:     cout << "is: " << is << endl;
075: 
076:     // testing 'Contains'
077:     cout << "Contains(1): " << is.Contains(1) << endl;
078:     cout << "Contains(5): " << is.Contains(5) << endl;
079:     cout << "Contains(10): " << is.Contains(10) << endl;
080: }
081: 
082: void TestingRemove ()
083: {
084:     IntegerSet is;
085:     for (int i = 0; i < 20; i ++)
086:         is.Insert (i);
087:     cout << "is: " << is << endl;
088: 
089:     is.Remove (5);
090:     is.Remove (1);
091:     is.Remove (8);
092:     cout << "is: " << is << endl;
093: 
094:     is.Remove (11);
095:     cout << "is: " << is << endl;
096: 
097:     is.Remove (16);
098:     cout << "is: " << is << endl;
099: 
100:     is.Remove (19);
101:     cout << "is: " << is << endl;
102: }
103: 
104: void TestingInsert ()
105: {
106:     IntegerSet is;
107:     for (int i = 0; i < 16; i ++)
108:         is.Insert (i);
109: 
110:     cout << "is: " << is << endl;
111: 
112:     is.Insert (16);
113:     cout << "is: " << is << endl;
114: }
115: 
116: void TestingOperators ()
117: {
118:     // testing union set
119:     IntegerSet is1;
120:     IntegerSet is2;
121:     for (int i = 0; i < 7; i ++)
122:         is1.Insert (i);
123:     for (int i = 2; i < 9; i ++)
124:         is2.Insert (i);
125:     cout << "is1: " << is1 << endl;
126:     cout << "is2: " << is2 << endl;
127:     cout << "is1+is2: " << (is1 + is2) << endl;
128: 
129:     // testing difference set
130:     cout << "is1-is2: " << (is1 - is2) << endl;
131: 
132:     // testing intersection set
133:     cout << "is1^is2: " << (is1 ^ is2) << endl;
134: 
135:     // testing ==-operator
136:     cout << "is1 == is2: " << (is1 == is2) << endl;
137:     is2.Insert (0);
138:     is2.Insert (1);
139:     is2.Remove (7);
140:     is2.Remove (8);
141:     cout << "is2: " << is2 << endl;
142:     cout << "is1 == is2: " << (is1 == is2) << endl;
143:     cout << "is1 != is2: " << (is1 != is2) << endl;
144: 
145:     // testing subset operator
146:     cout << "is1: " << is1 << endl;
147:     cout << "is2: " << is2 << endl;
148:     cout << "is1 <= is2: " << (is1 <= is2) << endl;
149:     is1.Insert (7);
150:     cout << "is1: " << is1 << endl;
151:     cout << "is1 <= is2: " << (is1 <= is2) << endl;
152: 
153:     // testing assignment operator
154:     is1 = is2;
155:     cout << "is1: " << is1 << endl;
156:     is1 = is1;
157:     cout << "is1: " << is1 << endl;
158: }
159: 
160: void TestingArithmeticAssignmentOperators ()
161: {
162:     int elems1[3] = { 1, 2, 3 };
163:     IntegerSet is1(elems1, 3);
164:     cout << "is1: " << is1 << endl;
165: 
166: 	int elems2[3] = { 4, 5, 6 };
167:     IntegerSet is2(elems2, 3);
168:     cout << "is2: " << is2 << endl;
169: 
170: 	int elems3[3] = { 7, 8, 9 };
171:     IntegerSet is3(elems3, 3);
172:     cout << "is3: " << is3 << endl;
173:     
174:     is1 += is2 += is3;
175: 
176:     cout << "is1: " << is1 << endl;
177:     cout << "is2: " << is2 << endl;
178:     cout << "is3: " << is3 << endl;
179: }
180: 
181: void TestingSubscriptOperator ()
182: {
183:     int elems[9] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
184:     IntegerSet is(elems, 9);
185: 
186:     for (int i = 0; i < is.Size(); i ++)
187:         cout << "Element at " << i << ": " << is[i] << endl;
188: }
189: 
190: void main ()
191: {
192:     TestingCtorsDtor();
193:     TestingMethods();
194:     TestingRemove();
195:     TestingInsert();
196:     TestingOperators();
197:     TestingArithmeticAssignmentOperators();
198:     TestingSubscriptOperator();
199: }

Beispiel 3. Klasse IntegerSet: Testrahmen (in Ausschnitten).


Der Testrahmen aus Listing 3 führt bei der Ausführung zu folgenden Resultaten:

Testing c'tors / d'tor:
is1: {} [0]
is2: {-2,-1,0,1,2} [5]
is3: {-1,1,2,3} [4]
is4: {-1,1,2,3} [4]
is1.IsEmpty: 1
is2.IsEmpty: 0
is3.IsEmpty: 0
is4.IsEmpty: 0
Testing methods:
is: {} [0]
is: {1,2,3,4,5,6} [6]
is: {1,2} [2]
is: {1,2,10,11,12,13,14,15,16,17,18,19,20,21,22,23} [16]
is: {1,2,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24} [17]
is: {1,2,10,12,13,14,15,16,17,18,19,20,21,22,23,24} [16]
Contains(1): 1
Contains(5): 0
Contains(10): 1
is: {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19} [20]
is: {0,2,3,4,6,7,9,10,11,12,13,14,15,16,17,18,19} [17]
is: {0,2,3,4,6,7,9,10,12,13,14,15,16,17,18,19} [16]
is: {0,2,3,4,6,7,9,10,12,13,14,15,17,18,19} [15]
is: {0,2,3,4,6,7,9,10,12,13,14,15,17,18} [14]
is: {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} [16]
is: {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} [17]
is1: {0,1,2,3,4,5,6} [7]
is2: {2,3,4,5,6,7,8} [7]
is1+is2: {0,1,2,3,4,5,6,7,8} [9]
is1-is2: {0,1} [2]
is1^is2: {2,3,4,5,6} [5]
is1 == is2: 0
is2: {2,3,4,5,6,0,1} [7]
is1 == is2: 1
is1 != is2: 0
is1: {0,1,2,3,4,5,6} [7]
is2: {2,3,4,5,6,0,1} [7]
is1 <= is2: 1
is1: {0,1,2,3,4,5,6,7} [8]
is1 <= is2: 0
is1: {2,3,4,5,6,0,1} [7]
is1: {2,3,4,5,6,0,1} [7]
is1: {1,2,3} [3]
is2: {4,5,6} [3]
is3: {7,8,9} [3]
is1: {1,2,3,4,5,6,7,8,9} [9]
is2: {4,5,6,7,8,9} [6]
is3: {7,8,9} [3]
Element at 0: 9
Element at 1: 8
Element at 2: 7
Element at 3: 6
Element at 4: 5
Element at 5: 4
Element at 6: 3
Element at 7: 2
Element at 8: 1

Die in Listing 2 vorgestellte Realisierung ist sicherlich auf Grund der starken Beanspruchung der dynamischen Speicherverwaltung nicht optimal. Ein alternativer Realisierungsansatz besteht darin, dass man die Größe des internen Arrays an Hand eines fest vorgegebenen Werts allokiert, der bei Bedarf zu verdoppeln ist, also zum Beispiel 16, 32, 64, 128, usw. Beim Einfügen von Elementen in die Menge können so etliche neue Elemente aufgenommen werden, ohne dass eine Anforderung an die dynamische Speicherverwaltung gestellt werden muss (Abbildung 4).

IntegerSet-Mengenobjekt mit den Elementen 5, 9, 1, 7, und 3 und einem internen Datenpuffer der Länge 16.

Abbildung 4. IntegerSet-Mengenobjekt mit den Elementen 5, 9, 1, 7, und 3 und einem internen Datenpuffer der Länge 16.


Achtet man ferner darauf, dass alle Mengenelemente stets am Anfang des Arrays platziert sind, lassen sich auch bei dieser Strategie das Einfügen und Entfernen von Elementen verhältnismäßig einfach implementieren. In Abbildung 4 erkennen wir, dass wir zu diesem Zweck jetzt zwei Instanzvariablen zur Verwaltung des internen Arrays benötigen. Die Instanzvariable m_num beschreibt die aktuelle Anzahl der Elemente in der Menge, in m_cap ist die Größe des internen Puffers abgelegt (Kapazität, engl. capacity). Erst wenn m_num größer als m_cap wird, muss dynamisch ein neues Array allokiert werden.

Das Einfügen eines neuen Elements ist nun äußerst einfach. Es ist der erste unbenutzte Eintrag des internen Arrays zu verwenden, sofern noch freie Einträge vorhanden sind. Nur für den Fall, dass bereits vor der Einfügeoperation die Werte von m_num und m_cap übereinstimmen, muss ein größerer Datenpuffer allokiert werden (Abbildung 5).

Arbeitsweise der Insert-Methode: Aufruf mit dem Aktualparameter 2.

Abbildung 5. Arbeitsweise der Insert-Methode: Aufruf mit dem Aktualparameter 2.


Beim Entfernen eines Mengenelements steht man vor dem Problem, dass in dem internen Array eine Lücke entsteht (sofern nicht zufälligerweise das letzte Element zu löschen ist). Wir behelfen uns an dieser Stelle mit einem kleinen Trick: An die Position des zu löschenden Elements wird einfach das letzte Mengenelement umkopiert (Abbildung 6). Es sind so nach wie vor alle Mengenelemente dicht am Anfang des Arrays abgelegt und es entstehen keine Lücken. Nachfolgende Einfügeoperationen können auf diese Weise wieder trivial wie zuvor beschrieben ausgeführt werden.

Arbeitsweise der Remove-Methode: Aufruf mit dem Aktualparameter 7.

Abbildung 6. Arbeitsweise der Remove-Methode: Aufruf mit dem Aktualparameter 7.


Werden im Zuge der Mengenoperationen mehr Lösch- wie Einfügeoperationen durchgeführt, sollte man den internen Datenpuffer wieder verkleinern. Man verhindert so, dass der Speicherplatz eines IntegerSet-Objekts nicht ausschließlich zunimmt.

Zum Abschluss dieser Betrachtungen demonstrieren wir in Abbildung 7, wie sich sowohl beim Einfügen wie auch beim Entfernen von Elementen in ein IntegerSet-Objekt das dynamische Anlegen neuer Datenpuffer stark reduziert.

Arbeitsweise der Insert- und Remove-Methode bei geblocktem Datenpuffer.

Abbildung 7. Arbeitsweise der Insert- und Remove-Methode bei geblocktem Datenpuffer.


Bei der zweiten Realisierungsstrategie ändert sich die Schnittstelle der IntegerSet-Klasse minimal. Wir fügen einen zusätzlichen Konstruktor

IntegerSet (int capacity);

hinzu, der es gestattet, die Größe des internen Datenpuffers bei der Objekterzeugung vorab festzulegen. In der Realisierung sollte darauf geachtet werden, dass der Parameter capacity auf ein Vielfaches von 16 angepasst wird. Bei den Instanzvariablen ist es nun relevant, zwischen der Anzahl der Elemente in der Menge und der Größe des internen Puffers zu unterscheiden. Die beiden Variablen m_num und m_cap sind dazu vorgesehen:

// private member data
int  m_cap;  // capacity of set
int  m_num;  // current number of elements
int* m_set;  // array of elements

Es folgt die Implementierung des alternativen Lösungsvorschlags. In Listing 4 finden Sie nur die Teile der Klasse IntegerSet vor, deren Realisierung sich geändert hat. Selbstverständlich ist die öffentliche Schnittstelle der Klasse IntegerSet dabei unverändert geblieben:

001: // c'tors and d'tor
002: IntegerSet::IntegerSet ()
003: {
004:     // allocate buffer
005:     m_num = 0;
006:     m_cap = 16;
007:     m_elems = new int[m_cap];
008: }
009: 
010: IntegerSet::IntegerSet (int cap)
011: {
012:     // allocate buffer
013:     m_num = 0;
014:     m_cap = 16;
015:     while (m_cap < cap)
016:         m_cap *= 2;
017:     m_elems = new int[m_cap];
018: }
019: 
020: IntegerSet::IntegerSet (int elems[], int count)
021: {
022:     // allocate buffer
023:     m_num = 0;
024:     m_cap = 16;
025:     m_elems = new int[m_cap];
026: 
027:     for (int i = 0; i < count; i ++)
028:         Insert (elems[i]);
029: }
030: 
031: IntegerSet::IntegerSet (const IntegerSet& is)
032: {
033:     // allocate buffer
034:     m_num = is.m_num;
035:     m_cap = is.m_cap;
036:     m_elems = new int[m_cap];
037: 
038:     // copy object
039:     for (int i = 0; i < m_num; i ++)
040:         m_elems[i] = is.m_elems[i];
041: }
042: 
043: // public methods
044: bool IntegerSet::Insert (int n)
045: {
046:     // element already exists
047:     if (Contains (n))
048:         return false;
049: 
050:     // if current buffer is full, allocate a new one
051:     if (m_cap == m_num)
052:     {
053:         int* tmp = new int[m_cap * 2];
054: 
055:         // copy old buffer into new one
056:         for (int i = 0; i < m_num; i ++)
057:             tmp[i] = m_elems[i];
058: 
059:         // switch to new buffer
060:         delete[] m_elems;
061:         m_elems = tmp;
062:         m_cap *= 2;
063:     }
064: 
065:     // insert value at end of buffer
066:     m_elems[m_num] = n;
067:     m_num ++;
068: 
069:     return true;
070: }
071: 
072: bool IntegerSet::Remove (int n)
073: {
074:     // does element already exist
075:     if (! Contains (n))
076:         return false;
077: 
078:     for (int i = 0; i < m_num; i ++)
079:     {
080:         if (m_elems[i] == n)
081:         {
082:             // remove element - and copy last element into gap
083:             m_elems[i] = m_elems[m_num-1];
084:             m_num --;
085:         }
086:     }
087: 
088:     // reduce current buffer, if necessary
089:     if ((m_cap > 16) && (2 * m_num <= m_cap))
090:     {
091:         int* tmp = new int[m_cap / 2];
092: 
093:         // copy old buffer into new one
094:         for (int i = 0; i < m_num; i ++)
095:             tmp[i] = m_elems[i];
096: 
097:         // switch to new buffer
098:         delete[] m_elems;
099:         m_elems = tmp;
100:         m_cap /= 2;
101:     }
102: 
103:     return true;
104: }
105: 
106: // operators
107: IntegerSet& IntegerSet::operator= (const IntegerSet& is)
108: {
109:     // prevent self-assignment
110:     if (this == &is)
111:         return *this;
112: 
113:     // delete old buffer
114:     delete[] m_elems;
115: 
116:     // allocate a new buffer
117:     m_num = is.m_num;
118:     m_cap = is.m_cap;
119:     m_elems = new int[m_cap];
120: 
121:     // copy buffer
122:     for (int i = 0; i < m_num; i ++)
123:         m_elems[i] = is.m_elems[i];
124: 
125:     return *this;
126: }
127: 
128: // output operator
129: ostream& operator<< (ostream& os, const IntegerSet& is)
130: {
131:     os << "{";
132:     for (int i = 0; i < is.m_num; i ++)
133:     {
134:         os << is.m_elems[i];
135:         if (i < is.m_num - 1)
136:             os << ',';
137:     }
138:     os << "} [" << is.m_num << "," << is.m_cap << "]";
139: 
140:     return os;
141: }

Beispiel 4. Klasse IntegerSet: Alternative Implementierung.