Im letzten Programm werden die Strings s und t mit Initialisierung durch Kopieren definiert. Eine syntaktisch äquivalente Form für die Initialisierung von t ist die Definition

string t = "LEDA";

Diese Möglichkeit der Definition durch Kopieren gibt es für jeden LEDA-Typ. Das ist eine feste Regel, die immer gültig ist, nämlich die LEDA-Regel bzgl. Definition mit Initialisierung durch Kopieren.

Diese Regel entstammt einem Regelwerk, das beim Programmieren mit LEDA eingehalten werden muss, um syntaktisch und semantisch korrekte und effiziente LEDA-Programme zu schreiben. Die Regel, dass Definition mit Initialisierung durch Kopieren für jeden LEDA-Typ möglich ist, ist eine davon. Wir werden diese Regeln nach und nach kennen lernen. Wer mag, kann sich in Anhang B, Die goldenen LEDA-Regeln schon einmal einen Überblick verschaffen.

Was aber ist eine Kopie eines Strings? Was machen Anweisungen wie

t = s;

oder

string t(s);

genau? In Programmen, die mit vielen Stringvariablen arbeiten, tragen erfahrungsgemäß viele dieser Variablen denselben Wert, d. h. sie beziehen sich auf die gleiche Zeichenkette. Es wäre eine große Speicherplatzverschwendung, wenn jede Variable ein eigenes Objekt bezeichnen würde, d. h. einen separaten Bereich im Speicher. LEDA ist immer bemüht, eine möglichst kluge, d. h. speicher- und/oder platzsparende Implementierung eines Datentyps anzubieten, und arbeitet deshalb hier mit einem Handle-Schema und mit Referenzzählung (reference counting): Wenn die Stringvariable s der Variablen t durch die Anweisung t = s zugewiesen oder t mit einer Kopie von s initialisiert wird, so werden nicht etwa die einzelnen Zeichen vom physikalischen Speicherort von s an den Speicherort von t kopiert, sondern vielmehr „zeigen“ nun t und s auf denselben physikalischen Speicherbereich. In diesem Sinne sind sie „Griffe“ (engl. „Handles“), über die auf den tatsächlichen Bereich zugegriffen wird. Den tatsächlichen String, d. h. die Folge der Zeichen, gibt es nur einmal im Speicher, und LEDA zählt mit, wie viele Handles sich darauf beziehen.

Erst wenn ein String z. B. durch einen Zugriff über [] verändert wird, werden die beiden Handles tatsächlich „entkoppelt“, d. h. es wird neuer Speicherplatz angefordert und eine Kopie angelegt. In diesem Sinne sind Strings von ihrer Implementierung her Zeigern sehr ähnlich, nur geschieht dank LEDA alles von selbst im Hintergrund; der Benutzer muss sich über die üblichen, bei der Verwendung von Zeigern und dynamischer Speicherallokation auftretenden Schwierigkeiten keine Sorgen machen.

Einige Typen von LEDA folgen diesem Handle-Schema mit Referenz-Zählung, so etwa der Typ point für Punkte in der Ebene oder der Typ integer für beliebig große ganze Zahlen. Diese Typen werden demnach als Handle-Typen bezeichnet.

Der Typ string ist aus verschiedenen implemetierungstechnischen Günden, auf die wir hier nicht eingehen wollen, kein echter Handle-Typ. Demgemäß wird die Klasse string auch nur als handle-ähnlicher Typ bezeichnet.

Alle Datentypen von LEDA lassen sich hinsichtlich der Art und Weise, wie ein Objekt eines solchen Typs kopiert wird, und hinsichtlich der Frage, wie ein solches Objekt aus Teilobjekten aufgebaut ist oder in einem umfassendem Objekt vorkommen muss, in ein System einordnen, das in Anhang A, Klassifizierung der LEDA-Datentypen dargestellt ist. Diese Klassifizierung werden wir nach und nach kennen lernen. In ihr ist der Typ string als handle-ähnlicher Typ unter die Item-Typen eingeordnet, die eine Unterkategorie der primitiven Typen darstellen.

Im Gegensatz zum Zuweisungsoperator legt der Operator +=, den wir im Palindromtest benutzt haben, um einen String umzudrehen, immer eine Kopie eines Strings an, ohne dass wir es merken. Dadurch wird beim Umdrehen eines Strings, wie wir es bisher implementiert haben, trotz des Handle-Schemas beim Anhängen jedes Zeichens des ursprünglichen Strings eine Kopie eines Strings angelegt. Eine unnötige Speicherverschwendung! Wie also können wir einen (langen) String speicherplatzeffizient umdrehen? Das folgende Programm beinhaltet zwei Tricks. Einen, um beliebig lange Satzpalindrome zu bilden; er ist der englischen Sprache zuzuschreiben. Und einen Programmiertrick, der die Kopierwut von += umgeht.

#include <LEDA/string.h>
#include <iostream>

using leda::string;
using std::cout;

string reverse_efficient(const string& s) {
  string result = s;

  int i = 0;
  int j = result.length() - 1;

  while(i < j) {
    char tmp = result[i];
    result[i] = result[j];
    result[j] = tmp;
    i++; j--;
  }
  
  return result;
}


int main() {
  string s;
  
  cin >> s;

  string s_quoted = "'" + s + "'";
  
  string r = reverse_efficient(s_quoted);

  string outstring = s_quoted + " sides reversed is " + r;

  cout << outstring << "\n";
  cout << reverse_efficient(outstring) << "\n";
}

Die Ausgabe des Programms bei der Eingabe Joachim ist

'Joachim' sides reversed is 'mihcaoJ'
'Joachim' si desrever sedis 'mihcaoJ'

und damit dürfte der erste Trick offenkundig sein.

Die Effizienz der Funktion reverse_efficient() liegt darin begründet, dass insgesamt nur eine Kopie angelegt wird, und zwar in dem Moment, in dem zum ersten Mal schreibend auf result[0] zugegriffen wird. Das Vertauschen der Zeichen geschieht innerhalb dieser Kopie durch zwei Indizes i und j. Dabei läuft i von vorne nach hinten und j von hinten nach vorne, bis sie sich in der Mitte treffen. Es werden jeweils die Zeichen an der Stelle i und j vertauscht.

Strings sind durch Zeichenarrays von C++ implementiert.

Wenn der String s aus n Zeichen besteht und der String t aus m Zeichen, so gilt: Alle Operationen, die ein Suche nach dem Teilstring t im String s beinhalten, benötigen Zeit O(n·m). (Die Bedeutung der O-Notation werden wir in Abschnitt 2.2.3 kennen lernen.) Ein Zugriff auf ein einzelnes Zeichen durch [] benötigt konstante Zeit. Alle anderen Operationen benötigen Zeit O(n).

Die Klasse string besitzt noch einige weitere Methoden. Auch können die oben vorgestellten Methoden teilweise mit anderen oder zusätzlichen Argumenten aufgerufen werden. Diese Möglichkeiten wollen wir hier nicht alle vorstellen. Stattdessen verweisen wir auf die entsprechende Manualseite der Klasse string