sorteddict PEP proposal [started off as orderedict]

Paul Hankin paul.hankin at
Wed Sep 26 15:59:40 CEST 2007

On Sep 26, 2:46 pm, Duncan Booth < at invalid.invalid> wrote:
> Paul Hankin <paul.han... at> wrote:
> > More flexibly, keep a set of inserted keys that haven't yet been
> > included in the sorted list, and a set of deleted keys that haven't
> > yet been removed from the sorted list. The cache is invalid if either
> > of these sets are empty - and to make it valid you can choose what to
> > do based on the sizes of the two sets (and the sorted list). For
> > instance, if there's just been one insertion you're probably better
> > doing an insertion rather than a full resort. Of course, there's a few
> > nasty cases here but it's always possible to just throw away the
> > sorted list and reconstruct it from the dict keys when things get too
> > hairy (eg, the user deletes a key that's in the inserted-but-not-yet-
> > sorted set).
> Yes that sounds good. Did you mean 'The cache is invalid if either of
> these sets is not empty'?

Yes :)

> If you delete a key which is in the inserted set you can simply delete
> it from the inserted set.

No, in case it was already in the sorted list before the insert. You
have to remove it from the inserted set AND add it to the deleted set.

Paul Hankin

More information about the Python-list mailing list