3.4. Sorted sequences (class sortseq)

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.

Figure 3.6. A sorted sequence

A sorted sequence

A sorted sequence with 6 containers. The key type is string, the value type is int. The containers are ordered (lexicographically) according to the keys, not according to the values.

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.