SortedListTKey

SortedListTKey is a generic collection that stores elements together with a key of type TKey and maintains the entire set in sorted order according to that key. It is designed for scenarios that require both ordered iteration and fast lookups by key, combining aspects of a list and a map.

In typical implementations, each element is associated with a sortable key, and operations preserve key order. The structure may enforce unique keys or permit duplicates, depending on the design. Internally it often uses a contiguous array or list for elements and a parallel array or index to keep keys sorted, enabling efficient binary-search based access while preserving insertion order by key. Some variants store only values with keys, while others pair keys with values (similar to a map).

Common operations include:

- Add or Insert: adds a new (key, value) pair and places it at the correct position to maintain order.

- RemoveByKey and Remove: delete elements by key or by position.

- Find or GetByKey: retrieve a value or item by its key, typically via binary search.

- ContainsKey and Count: check for key existence and report the number of elements.

- Enumerate: iterate elements in sorted key order, optionally providing range queries (GetRange, GetBetween).

Performance characteristics depend on implementation. Lookups by key are usually O(log n), while inserting into a sorted array can be O(n) due to shifting elements. Memory usage includes storage for keys, values, and any auxiliary indexing structures.

Common use cases involve applications requiring ordered traversal with efficient key-based access, such as range queries, sorted reporting, or multi-step processing where determinism of iteration order is important. It is often contrasted with standard dictionaries (maps) and with simple lists that are sorted on demand.