*Learning objectives*

Sorted sequences |

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
* sortseq*, which
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.^{[34]}
One, however, should not use the class `sortseq`

unhesitatingly:
The price for its variousness are an increased space overhead for storing the structure
and larger constants in the asymptotic running times of the
individual operations.

^{[34] }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 `sortseq`

by
what I really need.”