Sorted Sequences
The data type sortseq can be used to store objects of an arbitrary type I together with an associated key of a linearly
ordered type K (int, string,
…). Elements of sortseq are of type seq_item.
Complete Example of
Sorted Sequences ...
Strengths
- wide range of operations. Sorted Sequences can do almost everything
Linear Lists, Dictionaries,
and Priority Queues can do and many
other things (with the same asymptotic efficiency)
- finger search opens the possibility for sublogarithmic search time.
It requires that the position of the key searched for is approximately
known (finger_locate() operations).
Disadvantages
- Sorted Sequences need more space per item than the related data types.
- Constant factors in time bounds are larger than for related data
types.
Tips
- Use Sorted Sequences only if you really need the special functionality.
- Otherwise use one of the related data types.
|
See also:
Other data types with key of linearly ordered type:
Dictionaries
Dictionary Arrays.
Data type with key of type pointer, item, or int: Maps
Data type with key of hashed type: Hashing
Arrays
Two-Dimensional Dictionaries
Strings
Manual Entries:
Manual
Page Sorted Sequences
User
Defined Parameter Types
LEDA
Item Concept
Linear
Orders
Hashed
Types
|