2.11.1. Paare, Tripel und Quadrupel (Klassen two_tuple, three_tuple, four_tuple)

Lernziele

Die Klasse two_tuple
Die Klasse three_tuple
Die Klasse four_tuple

Sehr oft müssen aus schon bestehenden Datentypen Verbundtypen gebaut werden. Besonders häufig kommt dies in kombinatorischen Algorithmen vor, wo die meisten dieser Verbundtypen aus zwei, drei bzw. vier Komponenten bestehen. Solche geordneten Paare werden je nach Anzahl der Komponenten als Paare, Tripel bzw. Quadrupel bezeichnet. Allgemein wird eine geordnete Ansammlung von n Objekten als n-Tupel bezeichnet.

Um dem Programmierer die immer gleiche Schreibarbeit zu ersparen, bietet LEDA hier ein wenig „syntaktischen Zucker“ an: die Klassen two_tuple, three_tuple und four_tuple. So ist eine Variable vom Typ two_tuple<A,B> ein geordnetes Paar (a,b) von Variablen a und b, wobei a vom Typ A und b vom Typ B ist. Die beiden anderen Klassen erweitern dieses Konzept auf drei bzw. vier Komponenten.

Diese Tupel werden oft als Typparameter eines Containertyps verwendet, der eine lineare Ordnung auf den Elementen voraussetzt. Daher muss jeder einzelne der Komponententypen die Funktion compare() implementieren, die wir in Abschnitt 2.8.3 kennen gelernt haben. Dadurch erweitert sich die Default-Ordnung der Typparameter auf eine Default-Ordnung von Paaren dieser Typen durch komponentenweisen Vergleich: Zuerst wird nach der ersten Komponente geordnet, dann nach der zweiten usw.

Das folgende Programm erzeugt einige Paare von ganzen Zahlen, speichert sie in einer Liste ab, sortiert die Liste und gibt die Paare in sortierter Reihenfolge wieder aus.

Filename: TupleSort.C
#include <LEDA/tuple.h>
#include <LEDA/list.h>
#include <iostream>

using leda::two_tuple;
using leda::list;

int main()
{
  two_tuple<int,int> A(1,2);
  two_tuple<int,int> B(-2,1);
  two_tuple<int,int> C(3,5);
  two_tuple<int,int> D(3,4);

  std::cout << "A is: " << A.first() << " " << A.second() << "\n";

  list<two_tuple<int,int> > L;

  L.push(A);
  L.push(B);
  L.push(C);
  L.push(D);

  L.sort();

  L.print("All tuples are: ",'\n'); 
}

Die Ausgabe ist:

A is: 1 2
All tuples are:
-2 1
1 2
3 4
3 5

Hier wird der Typ two_tuple zweimal mit dem Typ int parametrisiert, was einen Typ ergibt, der Paare von ganzen Zahlen umfasst.

Die Werte der Komponenten eines Paares können im Konstruktor angegeben werden. Auf sie kann durch die Methoden

P.first();
P.second();

zugegriffen werden, die eine Referenz auf die jeweilige Komponente liefern. (Bei Tripeln und Quadrupeln gibt es entsprechend die Methoden third() und fourth()).

Wie wir an der Ausgabe der sortierten Liste sehen, wird bei der Default-Ordnung von Tupeln komponentenweise geordnet: zuerst nach der ersten Komponenten, dann nach der zweiten usw.

Weitere Informationen

Mehr Informationen zu den Tupeln von LEDA finden sich auf der Manualseite von two_tuple, der Manualseite von three_tuple und der Manualseite von four_tuple.