[Python-ideas] Sorted lists
alex at alexchamberlain.co.uk
Mon Apr 8 17:16:31 EDT 2019
On Mon, 8 Apr 2019 at 22:07, Barry Scott <barry at barrys-emacs.org> wrote:
> > On 8 Apr 2019, at 19:37, Terry Reedy <tjreedy at udel.edu> wrote:
> > On 4/8/2019 5:40 AM, Steven D'Aprano wrote:
> >> 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;
> > Item assignment could be allowed if it checked the new value against neighbors and raised ValueError if it would 'unsort' the list.
> >> - 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).
> How do you handle a list of objects that after insertion and being sorted change their sort key and thus make the list unsorted.
> From the point of view of the list nothing changed, but its not sorted now.
> Think if a list of file stat info objects that are sorted by size.
> As the files are written to the size changes.
> I can loop over the objects and tell them to update the stats.
> Now the __is_sorted__ property is wrong.
> > --
> > Terry Jan Reedy
> > _______________________________________________
> > Python-ideas mailing list
> > Python-ideas at python.org
> > https://mail.python.org/mailman/listinfo/python-ideas
> > Code of Conduct: http://python.org/psf/codeofconduct/
> Python-ideas mailing list
> Python-ideas at python.org
> Code of Conduct: http://python.org/psf/codeofconduct/
I think you're right to recognise that as a risk, but I consider it
similar to the risk of someone defining `__hash__` on a mutable
object, putting it in a `set` then mutating it. We'd have to make the
contract of `SortedList` clear, but I think it would be very difficult
to stop the determined user from breaking the contract if they so
To be clear, that contract would be that although storing mutable
objects is supported, once in the SortedList, a mutable object must
not be changed in such a way as to change its key.
More information about the Python-ideas