[Python-ideas] Sorted lists

[Steven D'Aprano]

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).


-- 
Steven