[Python-ideas] Sorted lists
steve at pearwood.info
Mon Apr 8 05:40:55 EDT 2019
On Mon, Apr 08, 2019 at 07:44:41AM +0100, Alex Chamberlain wrote:
> I think a better abstraction for a sorted list is a new class, which
> implements the Sequence protocol (and hence can be used in a lot of
> existing list contexts), but only exposed mutation methods that can
> guarantee that sorted order can be maintained
Perhaps that's a better idea.
> (and hence is _not_ a MutableSequence).
Right, but it can still be mutable, so long as the mutation methods can
maintain the invariant. That means:
- the SortedList needs to know the sort direction;
- and the key used for sorting;
- no slice or item assignment;
- insertions are okay, since the SortedList can put them in
the correct place;
- but not append;
- deletions are okay, since they won't change the sort invariant
(at least not for items with a total order).
More information about the Python-ideas