A sorted sequence (in the sense of LEDA) is a sequence of containers in which every container consists of a key of a linearly ordered key type and a value of an arbitrary value type. The containers are ordered in ascending order of their keys. Figure 3.6 shows a sorted sequence.
Sorted sequences are provided in LEDA by the class
offers a broad pallet of operations. This covers almost all
operations of which linear
lists, dictionaries, and priority queues are capable
and still much more. A
sortseq does this even with the same time
costs, asymptotically speaking.
Sorted sequences are therefore the “egg putting wool
milk sow” container type of LEDA.
One, however, should not use the class
The price for its variousness are an increased space overhead for storing the structure
and larger constants in the asymptotic running times of the
 A LEDA
adept known to the author responded to the question about his
main use cases of sorted sequences with the words “If I do
not know which specialized container type I finally need, or if I am too lazy to think this over, I first start with a
sortseq, and if everything is working at
the end, and I still feel like it, then I replace the
what I really need.”