Zeichenketten in C++: Die Klasse String

1. Aufgabe

In einer objektorientierten Sprache wie C++ gehört eine Klasse String für den komfortablen Umgang mit Zeichenketten zum Pflichtbestandteil der Klassenbibliothek eines jeden C++-Compilers. Da in C++ auch standardisierte Klassenbibliotheken existieren, finden wir die gesuchte Klasse – unter dem Namen string – tatsächlich auch in der STL („Standard Template Library“) vor. Um Übung in der Anwendung der Programmiersprache C++ zu erlangen, beschäftigen wir uns im folgenden mit der Realisierung unserer eigenen Klasse String, siehe dazu die Beschreibung der öffentlichen Schnittstelle dieser String-Klasse in Tabelle 1.

Bei der Implementierung der Klasse String ist der Speicherbereich für die einzelnen Zeichen der Zeichenkette dynamisch zu allokieren. Der Einfachheit halber legen wir zusätzlich zu Grunde, dass der Umfang dieses Speicherbereichs exakt an die Länge der Zeichenkette angepasst wird, siehe Abbildung 1. Den Overhead im Arbeitsaufwand der einzelnen Methoden nehmen wir in billigend Kauf, da wir mit dieser Vorschrift eine einfachere Realisierung verbuchen können.

Instanzdatenbereich eines String-Objekts mit dynamisch allokiertem Datenpuffer.

Abbildung 1. Instanzdatenbereich eines String-Objekts mit dynamisch allokiertem Datenpuffer.


Element

Schnittstelle und Beschreibung

Konstruktor

String ();

Standard-Konstruktor zum Anlegen einer leeren Zeichenkette.

Konstruktor

String (char* s);

Benutzerdefinierter Konstruktor. Als Argument wird eine Folge von char-Elementen erwartet, die mit '\0' abgeschlossen ist, sprich eine klassische „C-Zeichenkette“.

Methode Length

int Length () const;

Liefert die Länge der Zeichenkette zurück.

Methode Insert

bool Insert (const String& s, int ofs);

Fügt die Zeichenkette s in die aktuelle Zeichenketten-Instanz an der Position ofs ein.

Methode Append

void Append (const String& s);

Hängt die Zeichenkette s am Ende des aktuellen Zeichenkettenobjekts an.

Methode Remove

bool Remove (int ofs, int num)

Entfernt num Zeichen an der Position ofs des aktuellen Zeichenkettenobjekts.

Methode SubString

String SubString (int ofs, int num)

Extrahiert eine Teilzeichenkette (beginnend an der Position ofs mit num Zeichen) aus dem aktuellen Zeichenkettenobjekt. Das Ergebnis wird in Gestalt eines String-Objekts zurückgeliefert.

Methode Find

int Find (const String& s);

Sucht nach der Zeichenkette s im aktuellen Zeichenkettenobjekt. Wird die Zeichenkette gefunden, wird der Index (ihres ersten Vorkommens) innerhalb des aktuellen Zeichenkettenobjekts zurückgeliefert, andernfalls der Wert -1.

Methoden ToUpper und ToLower

void ToUpper ();
void ToLower ();

Wandelt alle Kleinbuchstaben im aktuellen Zeichenkettenobjekt in Groß- bzw. Kleinbuchstaben um.

Methoden Left und Right

String Left (int num);
String Right (int num);

Liefert die ersten bzw. letzten num Zeichen des aktuellen Zeichenkettenobjekts in Gestalt eines eigenständigen Zeichenkettenobjekts zurück.

Operator []

char operator[] (int n) const;

Indexoperator, liefert das n.-te Zeichen aus der Zeichenkette zurück.

Operatoren + und +=

friend String operator+ (const String& s1, const String& s2);
friend const String& operator+= (String& s1, const String& s2);

Verknüpfung von zwei Zeichenketten in Operatorenschreibweise als Alternative zur Append-Methode. Der +-Operator liefert als Resultatobjekt die Verkettung der zwei Zeichenketten s1 und s2 zurück, d.h. ihre Hintereinanderschreibung. Die Objekte s1 und s2 bleiben bei dieser Operation unverändert. Der +=-Operator hängt die Zeichenkette s2 an s1 an, das Ergebnis der Verkettung kommt folglich in Objekt s1 zum Tragen.

Operatoren == und !=

friend bool operator== (const String& s1, const String& s2);
friend bool operator!= (const String& s1, const String& s2);

Der ==-Operator vergleicht zwei Zeichenkettenobjekte auf inhaltliche Gleichheit, der !=-Operator auf ihre Ungleichheit.

Ein- und Ausgabe

friend ostream& operator<< (ostream& os, const String& s);
friend istream& operator>> (istream& is, String& s);

Ein- und Ausgabe einer Zeichenkette in der Konsole. Bei der Eingabe darf man in der Implementierung eine maximale Anzahl für die einzulesenden Zeichen voraussetzen. Die Ausgabe der Zeichenkette "ABC" sollte wiederum im Format "ABC"[3] erfolgen, die Länge der Zeichenkette ist in eckigen Klammern aufzuführen.

Tabelle 1. Öffentliche Elemente der Klasse String.


Hinweis: Klassenelemente wie der Kopierkonstruktor oder der Destruktor fehlen in Tabelle 1, da sie in einer korrekten Realisierung ohnehin vorhanden sein müssen.

Die in der Lösung vorgestellte Implementierung der Klasse String verzichtet auf jegliche Unterstützung aus der C Runtime Library (CRT). Dies erfolgt zu Lehrzwecken, um die Realisierung einer Klasse ohne jegliche Unterstützung durch eine externe Bibliothek zu betrachten. In der Praxis würde man zur Realisierung die CRT mit einbeziehen, um das Rad für eine Reihe elementarer Operationen wie Zeichenkette kopieren, vergleichen, usw. nicht zweimal erfinden zu müssen.

Zum Testen Ihrer Implementierung schreiben Sie für jede Methode oder zusammengehörige Gruppe von Klassenelementen eine separate Testfunktion. Die Regel „weniger ist mehr“ gilt an dieser Stelle nicht, ganz im Gegenteil: Um Änderungen in Ihrer Implementierung auch im Nachhinein seriös praktizieren zu können, benötigen Sie einen robusten Testrahmen. Eine sehr ausführliche Anregung dazu finden Sie hier:

#include <iostream>
using namespace std;

#include "String.h"

void TestingCtorsDtor ()
{
    // testing c'tors
    String s1;
    cout << "s1: " << s1 << endl;
    String s2 ("12345");
    cout << "s2: " << s2 << endl;
    String s3 (s2);
    cout << "s3: " << s3 << endl;
}

void TestingInsert ()
{
    String s1 ("12678");
    s1.Insert ("345", 2);
    cout << "s1: " << s1 << endl;

    String s2 ("ABCD");
    s2.Insert (s1, 2);
    cout << "s2: " << s2 << endl;

    s2.Insert ("!", 13);
    cout << "s2: " << s2 << endl;

    s2.Insert (".", 12);
    cout << "s2: " << s2 << endl;

    s2.Insert (".", 0);
    cout << "s2: " << s2 << endl;
}

void TestingAppend ()
{
    String s1;
    s1.Append ("123");
    cout << "s1: " << s1 << endl;

    String s2 ("ABC");
    s2.Append ("DEF");
    cout << "s2: " << s2 << endl;
}

void TestingRemove ()
{
    String s1 ("12345");
    s1.Remove (1, 3);
    cout << "s1: " << s1 << endl;

    String s2 ("ABC");
    s2.Remove (0, 3);
    cout << "s2: " << s2 << endl;
}

void TestingSubString ()
{
    String s2 ("ABCDE");
    String s;
    s = s2.SubString (1, 3);
    cout << "s: " << s << endl;
    s = s2.SubString (0, 5);
    cout << "s: " << s << endl;
    s = s2.SubString (0, 6);
    cout << "s: " << s << endl;
    s = s2.SubString (0, 0);
    cout << "s: " << s << endl;
}

void TestingOperators ()
{
    // testing '=' operator
    String s1;
    String s2 ("12345");
    s1 = s2;
    cout << "s1: " << s1 << endl;

    // testing '==' operator
    cout << "s1 == s2: " << (s1 == s2) << endl;
    s1.Remove (0, 1);
    cout << "s1 == s2: " << (s1 == s2) << endl;
    cout << "s1 != s2: " << (s1 != s2) << endl;
}

void TestingInput ()
{
    String s;
    cout << "Enter string: ";
    cin >> s;
    cout << "String: " << s << '.' << endl;
}

void TestingLeftRight ()
{
    String s("12345");
    String s1;
    String s2;

    s1 = s.Left (3);
    cout << "Left(3):  " << s1 << '.' << endl;
    s2 = s.Right(2);
    cout << "Right(2): " << s2 << '.' << endl;

    s1 = s.Left (5);
    cout << "Left(5):  " << s1 << '.' << endl;
    s2 = s.Right(5);
    cout << "Right(5): " << s2 << '.' << endl;

    s1 = s.Left (6);
    cout << "Left(6):  " << s1 << '.' << endl;
    s2 = s.Right(6);
    cout << "Right(6): " << s2 << '.' << endl;
}

void TestingToUpperToLower ()
{
    String s("aBcDeFgHiJkLmNoPqRsTuVwXyZ");
    cout << "s:" << s << '.' << endl;
    s.ToUpper ();
    cout << "s:" << s << '.' << endl;
    s.ToLower ();
    cout << "s:" << s << '.' << endl;
}

void TestingFind ()
{
    String s("ABCDEFGHIJKLMN");
    int i = s.Find ("IJK");
    cout << "i: " << i << endl;

    i = s.Find ("ABCDEFGHIJKLMN");
    cout << "i: " << i << endl;

    i = s.Find ("IJKZ");
    cout << "i: " << i << endl;

    i = s.Find ("N");
    cout << "i: " << i << endl;

    i = s.Find ("Z");
    cout << "i: " << i << endl;

    i = s.Find ("");
    cout << "i: " << i << endl;
}

void TestingSubsriptOperator ()
{
    String s("ABCDE");
    cout << "s[0]: " << s[0] << endl;
    cout << "s[4]: " << s[4] << endl;

    s[0] = '<';
    s[4] = '>';
    cout << "s: " << s << endl;

    try
    {
        s[5] = '!';
    }
    catch (out_of_range& e)
    {
        cout << e.what () << endl;
    }
}

void TestingStringConcatenation ()
{
    String s1("123");
    String s2("ABC");
    String s3;

    s3 = s1 + s2;
    cout << "s1:" << s1 << endl;
    cout << "s2:" << s2 << endl;
    cout << "s3:" << s3 << endl;

    s1 += s2 += "789";
    cout << "s1:" << s1 << endl;
    cout << "s2:" << s2 << endl;
}

void main ()
{
    TestingCtorsDtor ();
    TestingInsert ();
    TestingAppend ();
    TestingRemove ();
    TestingSubString ();
    TestingOperators ();
    TestingInput ();
    TestingLeftRight ();
    TestingToUpperToLower ();
    TestingFind ();
    TestingSubsriptOperator ();
    TestingStringConcatenation ();
}

Ausgabe:

s1: ""[0]
s2: "12345"[5]
s3: "12345"[5]
s1: "12345678"[8]
s2: "AB12345678CD"[12]
s2: "AB12345678CD"[12]
s2: "AB12345678CD."[13]
s2: ".AB12345678CD."[14]
s1: "123"[3]
s2: "ABCDEF"[6]
s1: "15"[2]
s2: ""[0]
s: "BCD"[3]
s: "ABCDE"[5]
s: ""[0]
s: ""[0]
s1: "12345"[5]
s1 == s2: 1
s1 == s2: 0
s1 != s2: 1
Enter string: 12345
String: "12345"[5].
Left(3):  "123"[3].
Right(2): "45"[2].
Left(5):  "12345"[5].
Right(5): "12345"[5].
Left(6):  ""[0].
Right(6): ""[0].
s:"aBcDeFgHiJkLmNoPqRsTuVwXyZ"[26].
s:"ABCDEFGHIJKLMNOPQRSTUVWXYZ"[26].
s:"abcdefghijklmnopqrstuvwxyz"[26].
i: 8
i: 0
i: -1
i: 13
i: -1
i: 0
s[0]: A
s[4]: E
s: "<BCD>"[5]
Wrong index
s1:"123"[3]
s2:"ABC"[3]
s3:"123ABC"[6]
s1:"123ABC789"[9]
s2:"ABC789"[6]

2. Lösung

Quellcode: Siehe auch https://github.com/peterloos/Cpp_Strings

01: class String
02: {
03: private:
04:     char* m_ptr; // buffer
05:     int m_len;   // buffer length
06: 
07: public:
08:     // c'tors and d'tor
09:     String ();
10:     String (char*);
11:     String (const String&);
12:     ~String ();
13: 
14:     // public methods
15:     int Length () const;
16:     bool Insert (const String&, int);
17:     bool Remove (int, int);
18:     void Append (const String&);
19:     String SubString (int, int) const;
20:     int Find (const String&) const;
21:     void ToUpper ();
22:     void ToLower ();
23:     String Left (int) const;
24:     String Right (int) const;
25: 
26:     // assignment operator
27:     String& operator= (const String&);
28: 
29:     // subscript operator
30:     char& operator[] (int index);
31: 
32:     // string concatenation
33:     friend String operator+ (const String&, const String&);
34:     friend const String& operator+= (String&, const String&);
35: 
36:     // comparison operators
37:     friend bool operator== (const String&, const String&);
38:     friend bool operator!= (const String&, const String&);
39: 
40:     // input/output
41:     friend ostream& operator<< (ostream&, const String&);
42:     friend istream& operator>> (istream&, String&);
43: };

Beispiel 1. Klasse String: Schnittstelle.


001: #include <iostream>
002: using namespace std;
003: 
004: #include "String.h"
005: 
006: // c'tors and d'tor
007: String::String ()
008: {
009:     // empty string
010:     m_len = 0;
011:     m_ptr = (char*) 0;
012: }
013: 
014: String::String (const String& s)
015: {
016:     // allocate buffer
017:     m_len = s.m_len;
018:     m_ptr = new char[m_len];
019: 
020:     // copy object
021:     for (int i = 0; i < m_len; i ++)
022:         m_ptr[i] = s.m_ptr[i];
023: }
024: 
025: String::String (char* s)
026: {
027:     // length of string
028:     m_len = 0;
029:     while (s[m_len] != '\0')
030:         m_len ++;
031: 
032:     // allocate buffer
033:     m_ptr = new char[m_len];
034: 
035:     // copy string
036:     for (int i = 0; i < m_len; i ++)
037:         m_ptr[i] = s[i];
038: }
039: 
040: String::~String ()
041: {
042:     delete[] m_ptr;
043: }
044: 
045: // getter
046: int String::Length () const
047: {
048:     return m_len;
049: }
050: 
051: char& String::operator[] (int index)
052: {
053:     // check parameter
054:     if (index < 0 || index >= m_len)
055:         throw out_of_range ("Wrong index");
056: 
057:     return m_ptr[index];
058: }
059: 
060: // public methods
061: bool String::Insert (const String& s, int ofs)
062: {
063:     if (ofs > m_len)
064:         return false;
065: 
066:     // allocate new buffer
067:     char* tmp = new char[m_len + s.m_len];
068: 
069:     for (int i = 0; i < ofs; i ++)      // copy first part
070:         tmp[i] = m_ptr[i];
071:     for (int i = 0; i < s.m_len; i ++)  // copy string to insert
072:         tmp[ofs + i] = s.m_ptr[i];
073:     for (int i = ofs; i < m_len; i ++)  // copy second part
074:         tmp[s.m_len + i] = m_ptr[i];
075: 
076:     delete[] m_ptr;   // release old buffer
077:     m_ptr = tmp;      // switch buffer
078:     m_len += s.m_len; // adjust buffer length
079: 
080:     return true;
081: }
082: 
083: void String::Append (const String& s)
084: {
085:     Insert (s, m_len);
086: }
087: 
088: bool String::Remove (int ofs, int num)
089: {
090:     if (ofs + num > m_len)
091:         return false;
092: 
093:     // allocate new buffer
094:     char* tmp = new char[m_len - num];
095: 
096:     // copy remaining parts
097:     for (int i = 0; i < ofs; i ++)            // first part
098:         tmp[i] = m_ptr[i];
099:     for (int i = ofs + num; i < m_len; i ++)  // second part
100:         tmp[i - num] = m_ptr[i];
101: 
102:     delete[] m_ptr; // release old buffer
103:     m_ptr = tmp;    // switch buffer
104:     m_len -= num;   // adjust buffer length
105: 
106:     return true;
107: }
108: 
109: String String::SubString (int ofs, int num) const
110: {
111:     String empty;
112:     if (ofs < 0)
113:         return empty;
114:     if (ofs > m_len)
115:         return empty;
116:     if (ofs + num > m_len)
117:         return empty;
118: 
119:     // allocate temporary buffer
120:     char* tmp = new char[num + 1];
121: 
122:     // copy partial string
123:     for (int i = 0; i < num; i ++)
124:         tmp[i] = m_ptr[ofs + i];
125:     tmp[num] = '\0'; // terminate buffer
126: 
127:     // create result object
128:     String s(tmp);
129:     delete[] tmp; // release temporary buffer
130:     return s;
131: }
132: 
133: int String::Find (const String& s) const
134: {
135:     for (int i = 0; i < m_len - s.m_len + 1; i ++)
136:     {
137:         int k = 0;
138:         while (k < s.m_len)
139:         {
140:             if (m_ptr[i + k] != s.m_ptr[k])
141:                 break;
142: 
143:              k ++;
144:         }
145:         if (k == s.m_len)
146:             return i;
147:     }
148: 
149:     return -1;
150: }
151: 
152: void String::ToUpper ()
153: {
154:     for (int i = 0; i < m_len; i ++)
155:         if (m_ptr[i] >= 'a' && m_ptr[i] <= 'z')
156:             m_ptr[i] -= ('a' - 'A');
157: }
158: 
159: void String::ToLower ()
160: {
161:     for (int i = 0; i < m_len; i ++)
162:         if (m_ptr[i] >= 'A' && m_ptr[i] <= 'Z')
163:             m_ptr[i] += ('a' - 'A');
164: }
165: 
166: String String::Left (int num) const
167: {
168:     return SubString (0, num);
169: }
170: 
171: String String::Right (int num) const
172: {
173:     return SubString (Length() - num, num);
174: }
175: 
176: // assignment operator
177: String& String::operator= (const String& s)
178: {
179:     if (this != &s)
180:     {
181:         // delete old string
182:         delete[] m_ptr;
183: 
184:         // allocate new buffer
185:         m_len = s.m_len;
186:         m_ptr = new char[m_len];
187: 
188:         // deep copy
189:         for (int i = 0; i < m_len; i ++)
190:             m_ptr[i] = s.m_ptr[i];
191:     }
192: 
193:     return *this;
194: }
195: 
196: // string concatenation
197: String operator+ (const String& s1, const String& s2)
198: {
199:     String s(s1);
200:     s.Append (s2);
201:     return s;
202: }
203: 
204: const String& operator+= (String& s1, const String& s2)
205: {
206:     s1.Append (s2);
207:     return s1;
208: }
209: 
210: // comparison operators
211: bool operator== (const String& s1, const String& s2)
212: {
213:     if (s1.m_len != s2.m_len)
214:         return false;
215: 
216:     for (int i = 0; i < s1.m_len; i++)
217:         if (s1.m_ptr[i] != s2.m_ptr[i])
218:             return false;
219: 
220:     return true;
221: }
222: 
223: bool operator!= (const String& s1, const String& s2)
224: {
225:     return ! (s1 == s2);
226: }
227: 
228: // output operator
229: ostream& operator<< (ostream& os, const String& s)
230: {
231:     os << '"';
232:     for (int i = 0; i < s.m_len; i++)
233:         os << s.m_ptr[i];
234:     os << "\"[" << s.m_len << ']';
235: 
236:     return os;
237: }
238: 
239: // input operator
240: istream& operator>> (istream& is, String& s)
241: {
242:     char line[256];
243:     is.getline(line, 256);
244: 
245:     // calculate length of string
246:     int len = 0;
247:     while (line[len] != '\0')
248:         len ++;
249: 
250:      // release old buffer, if any
251:     delete[] s.m_ptr;
252: 
253:     // allocate new buffer and copy string
254:     s.m_ptr = new char[len];
255:     for (int i = 0; i < len; i ++)
256:         s.m_ptr[i] = line[i];
257: 
258:     // adjust buffer length
259:     s.m_len = len; 
260: 
261:     return is;
262: }

Beispiel 2. Klasse String: Implementierung.