Die Klasse sortseq bietet zusätzlich Operationen an, um eine geordnete Folge (an einem bestimmten Container) in zwei geordnete Folgen aufzuspalten, um zwei geordnete Folgen aneinanderzuhängen und um zwei geordnete Folgen zusammenzumischen.

Ein Aufruf von

S.split(it, T1, T2);

spaltet die geordnete Folge S in zwei Teilfolgen T1 und T2 auf. it muss dabei ein Item sein, das auf einen Container von S verweist. S wird dann hinter diesem Container aufgespalten, d. h., der Container, auf den it verweist, wird zum letzten Container von T1. Dies entspricht dem zusätzlichen, vierten Default-Argument LEDA::after von split():

S.split(it, T1, T2, LEDA::after);

Um die Spaltung vor diesem Container auszuführen, kann als viertes Argument LEDA::before angegeben werden. T1 und T2 müssen verschiedene Objekte sein; eines von beiden darf wieder S sein. Ist S keines von beiden, dann ist S nach dem Aufspalten auf jeden Fall leer.

Die Anweisung

S.conc(T);

hängt T hinten an S an. T wird dabei geleert. Vorbedingung ist, dass der kleinste Schlüssel von T größer als der größte Schlüssel von S ist. Auch hier kann durch ein viertes Argument LEDA::before spezifiziert werden, dass T vor dem ersten Container von S angehängt werden soll (die Vorbedingung muss dann entsprechend umgedreht gelten). In jedem Fall wird T geleert.

Mit der Anweisung

S.merge(T);

werden die beiden geordneten Folgen S und T zu einer Folge zusammengemischt. Vorbedingung ist natürlich, dass alle Schlüssel in beiden Folgen verschieden sind. T wird dabei geleert, und S enthält nach dem Mischen alle Schlüssel-Wert-Paare.

Das folgende Programm gibt Beispiele für die Anwendung dieser Operationen:

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

using leda::sortseq;
using leda::seq_item;
using leda::string;
using std::cout;
using std::endl;


// print all key-value-pairs of a sortseq 
// together with its name and a newline at the end
inline void sortseq_print(const string& name, 
                          const sortseq<int, int>& S) {
  cout << name << ": ";
  if(S.empty()) {
    cout << "(Empty sequence)" << endl;
    return;
  }

  seq_item it = S.min_item();
  seq_item last_it = S.max_item();
  while(true) { 
    cout << "(" << S.key(it) << "," << S.inf(it) << ") ";
    if(it == last_it) break;
    it = S.succ(it);
  }
  cout << endl;
}


int main()
{
  sortseq<int,int> Even;
  sortseq<int,int> Odd;

  for(int i = 0; i < 10; i++) {
    Even.insert(i * 2, 0);
    Odd.insert(i * 2 + 1, 0);
  }

  cout << "Before splitting Even:" << endl;
  sortseq_print("Even", Even);
  sortseq_print("Odd", Odd);

  seq_item it = Even.locate(5);

  sortseq<int,int> T1, T2;

  Even.split(it, T1, T2, LEDA::before);
  cout << "After Even.split(it, T1, T2, LEDA::before):" << endl;
  sortseq_print("Even", Even);
  sortseq_print("T1", T1);
  sortseq_print("T2", T2);

  T2.conc(T1,LEDA::before); // LEDA::after results in an error here!
  cout << "After T2.conc(T1,LEDA::before):" << endl;
  sortseq_print("T1", T1);
  sortseq_print("T2", T2);

  T2.merge(Odd);
  cout << "After T2.merge(Odd):" << endl;
  sortseq_print("Odd", Odd);
  sortseq_print("T2", T2);
}

Das Programm gibt Folgendes aus:

Before splitting Even:
Even: (0,0) (2,0) (4,0) (6,0) (8,0) (10,0) (12,0) (14,0) (16,0) (18,0)
Odd: (1,0) (3,0) (5,0) (7,0) (9,0) (11,0) (13,0) (15,0) (17,0) (19,0)
After Even.split(it, T1, T2, LEDA::before):
Even: (Empty sequence)
T1: (0,0) (2,0) (4,0)
T2: (6,0) (8,0) (10,0) (12,0) (14,0) (16,0) (18,0)
After T2.conc(T1,LEDA::before):
T1: (Empty sequence)
T2: (0,0) (2,0) (4,0) (6,0) (8,0) (10,0) (12,0) (14,0) (16,0) (18,0)
After T2.merge(Odd):
Odd: (Empty sequence)
T2: (0,0) (1,0) (2,0) (3,0) (4,0) (5,0) (6,0) (7,0) (8,0) (9,0) (10,0) 
(11,0) (12,0) (13,0) (14,0) (15,0) (16,0) (17,0) (18,0) (19,0)

Die Hilfsfunktion print_sortseq zeigt, wie mittels min_item(), max_item() und succ() über alle Schlüssel-Wert-Paare einer sortseq iteriert werden kann.

	Anmerkung
	Obwohl es im LEDA-Manual (noch) nicht erwähnt ist, existieren auch bei sortseq die forall-Makros. Mit forall_defined(k,S) kann über alle Schlüssel, mit forall(v,S) über alle Werte iteriert werden.

Das Programm legt zunächst zwei geordnete Folgen Even und Odd an, deren Schlüssel gerade bzw. ungerade ganze Zahlen sind. (Da eine sortseq immer auch einen Typparameter für die assoziierten Werte benötigt, wählen wir hier einfach ebenfalls den Typ int, setzen die zugehörigen Werte aber immer auf 0.) Danach spaltet es die Folge Even am Schlüssel 5 in zwei Teilfolgen auf und hängt diese wieder geeignet zusammen. Zum Schluss mischt es noch die Folge der ungeraden Schlüssel in die Folge der geraden Schlüssel ein.