alwayssortedlist (was Re: On PEP 322 (ireverse))

[Bengt Richter]

On Wed, 29 Oct 2003 20:12:23 GMT, Alex Martelli <aleax at aleax.it> wrote:

>Roy Smith wrote:
>
>> "Terry Reedy" <tjreedy at udel.edu> wrote:
>>> As I suggested elsewhere, make iter() the type object for iterator.
>>> Then iter.reversed is closely parallel to list.sorted.
>> 
>> I've got a question about list.sorted.  I assume it's just a list that's
>> initialized to have its elements sorted when it's created?  We're not
>> talking about some new magic container type which keeps its elements
>> sorted all the time?
>> 
>> In other words, I'm assuming that
>> 
>> l = list.sorted ((1, 2, 5, 3))
>> l.append (4)
>> print l
>> 
>> will print [1, 2, 3, 5, 4], right?
>
>Perfectly right.  If you DO want a listoid container that keeps its
>elements sorted, that's not hard to make for yourself.  There are
>basically two obvious implementation strategies:
>  -- ensure the underlying list is re-sorted at each insertion,
>     append &c, and/or
>  -- let the underlying list grow as it will on insertion &c, but
>     make sure it's sorted at any method that accesses it (you can
>     use a flag -- 'have there being any append/insert/... since
>     the last sort?' -- to re-sort only when needed).
>
>I'll choose the first for general use because:
>  -- accesses are much more frequent than modifications,
>  -- list.sort is VERY fast when a list is "nearly sorted"
>  -- the second approach would require sorting also on many
>     kind of changes (e.g. __setitem__ -- to ensure the items
>     being replaced ARE those the user expects...)
>&c.
>
[...]

No comments on the heapq module?

Regards,
Bengt Richter