Very often compound types must be built from already existing data types. This occurs particularly often in combinatorial algorithms, where most of these compound type consist of two, three or four components. Such ordered pairs are denoted as pairs, triples, and quadruples, respectively, depending on the number of components. In general, an ordered collection of n objects is called an n-tuple.

To free the programmer from always the same paperwork, LEDA offers a little “syntactic sugar” here: the classes two_tuple, three_tuple, and four_tuple. So a variable of the type two_tuple<A,B> is an ordered pair (a,b) of variables a and b in which a is of type A and b of type B. The two other classes extend this concept on three and four components, respectively.

These tuples are often used as a type parameter of a container type that presupposes a linear order on the elements. Therefore, every single component type must implement the function compare() that we got to know in Section 2.8.3. Thereby, the default order of the type parameters extends itself on a default order for pairs of these types by component-wise comparison: First it is ordered according to the first component, then to the second one etc.

The following program creates some pairs of integer numbers, stores them in a list, sorts the list, and outputs the pairs in sorted order again.

#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'); 
}

The output is:

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

Here the type two_tuple is parametrized twice with the type int, which produces a type comprising pairs of integer numbers.

The values of the components of a pair can be specified in the constructor. They can be accessed by the methods

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

These methods return a reference to the respective component. (For triples and quadruples there are the corresponding methods third() and fourth().)

As we see from the output of the sorted list, ordering is carried out component-wise with the default order of tuples: first according to the first component, then to the second one etc.