Lektion 68:

Eine Comparator-Klasse

Die Sortierung der Namen ergibt die Liste "Anna", "Fritz", "Hans", "Klaus", "ich". Ich bin aber der Meinung, daß "ich" zwischen "Hans" und "Klaus" einsortiert werden sollte.

 Die falsche Sortierung liegt an der Klasse string. Sie vergleicht die Zeichen anhand der entsprechenden ASCII-Werte. Die ASCII-Werte der Großbuchstaben liegen im Bereich 65 (für 'A') bis 90 (für 'Z'). Die ASCII-Werte der Kleinbuchstaben liegen im Bereich 97 (für 'a') bis 122 (für 'z').

Um eine korrekte Sortierung zu erreichen müssen mindestens zwei eigene Funktionen erstellt werden, die unabhängig von der Groß- oder Kleinschreibung strings vergleicht:

  • ein operator< und
  • ein operator==.

Die anderen Vergleichsoperatoren lassen sich dann ohne großen Aufwand aus diesen erzeugen:

normale Darstellung      Ersatzdarstellung
  a<b                      ist gegeben
  a<=b                     !(b<a)
  a==b                     ist gegeben
  a!=b                     !(a==b)
  a>=b                     !(a<b)
  a>b                        b<a

Es würde sogar gehen, auf den Operator== zu verzichten

normale Darstellung      Ersatzdarstellung
  a!=b                       a>b¦¦a<b
  a==b                     !(a>b¦¦a<b)

aber dazu müßten zwei Vergleichs-Operatoren aufgerufen werden. Weil dies unter Umständen viel Rechenzeit beanspruchen könnten, ist es besser, nicht so weit zu gehen.

Die beiden Vergleichsfunktionen sollen lessThan und isEqual heißen und werden in eine entsprechende Klasse gepackt. Die einfachste Implementierung ist wohl, alle Zeichen in den beiden zu vergleichenden strings in Kleinbuchstaben zu verwandeln und dann einen ganz normalen string-Vergleich durchzuführen.

string tolower(const string &str)
{
   string result=str;
   for(int i=0;i<result.size();++i)
      result[i]=tolower(result[i]);
   return result;
};
class IgnoreCaseStringComparator
{
public:
   bool lessThan(const string &a,const string &b)
   {
      return tolower(a)<tolower(b);
   };
   bool isEqual(const string &a,const string &b)
   {
      return tolower(a)==tolower(b);
   };
};

Falls Sie die Funktion

char tolower(char ch)

 nicht mehr haben, dann inkludieren Sie einfach die Datei <ctype.h>. Dort stehen solche Funktionen bereit.

Diese neue Klasse kann man jetzt als Parameter der Containerklasse SortedArray übergeben. Nachdem die Klasse SortedArray entsprechend angepaßt ist, daß sie nur noch die Vergleichsfunktionen der übergebenen Klasse verwendet, wird sie auch wunschgemäß sortieren.

Die notwendigen Änderungen sind:

  • Einführen eines zweiten Template-Parameters,
  • Einführen eines Attributes dieses Typs,
  • Ersetzen der Vergleichsoperatoren.

Die ersten beiden Punkte sind schnell abgehandelt.

template<class T,class C>
class SortedArray
{
private:
   C m_comp;
   int m_size;
   usw.

Entsprechend ändert sich die main-Funktion.

void main()
{
   SortedArray<string,IgnoreCaseStringComparator> s;
   usw.

Das Ersetzen der Vergleichsoperatoren ist ein wenig mehr Mühe. Sie müssen nämlich immer unterscheiden, ob die Operatoren in Ihrer Klasse sich gerade auf die strings beziehen oder nur auf Ihre Feld-Indizes.

 Für solche Aufgaben empfehle ich, sich Unterstützung beim Compiler zu holen. Eigentlich ist diese Verwendung des Compilers eher ein Mißbrauch, und die reine Lehre sagt, daß man gefälligst selber nachdenken soll. Ich bin nicht dieser Meinung.

Diese Klasse hat keine Vergleichsoperatoren.

class Test
{
};

Sie kann aber mit diesem Comparator verglichen werden.

class TestComparator
{
public:
   bool lessThan(const Test &a,const Test &b)
   {
      return false;
   };
   bool isEqual(const Test &a,const Test &b)
   {
      return false;
   };
};

Und diese Funktion kann nicht compiliert werden, weil der Comparator noch nicht benutzt wird.

void test()
{
   SortedArray<Test,TestComparator> test;
};

Sie bekommen jetzt überall dort, wo Sie Ersetzungen machen müssen eine Fehlermeldung. Die alle zu beheben, dürfte nicht schwierig sein. Es muß nur jeder Aufruf der normalen Vergleichsoperatoren in einen Aufruf einer der beiden Vergleichsfunktionen übersetzt werden.

Nachdem Sie alle Fehler beseitigt haben, löschen Sie wieder die Test-Klassen und die test-Funktion und das Programm ist fertig.



Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern.
[aktuelle Version] [inhalt] [index]      [Fehlerkorrektur, Verbesserungsvorschlag]

© Volkard Henkel <volkard@normannia.de>, last update: 08/25/00