| 3.4. Sorted sequences (class sortseq) | ||
|---|---|---|
 | Chapter 3. Associative container types |  |
| 3.4. Sorted sequences (class sortseq) | ||
|---|---|---|
| | Chapter 3. Associative container types | |
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 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.”
| |  | |
| 3.3.3. Maps (class map) |  | 3.4.1. Basic functionality |