Ordered Sets

[Scott David Daniels]

pataphor wrote:
> Raymond Hettinger wrote:
> 
>> Right.  Here's a link to a weakref version (though I think the
>> previous __del__ version also does the trick):
>>
>>     http://code.activestate.com/recipes/576696/
> 
> Interesting. But how about this one? Does it also have the reference 
> problem? By the way collections.MutableSet needs python >= 2.6
...

> class OrderedSet(collections.MutableSet):
>     'Set that remembers the order elements were added'
>     # Big-O running times for all methods are the same as for regular sets.
> 
>     def __init__(self, iterable=None):
>         self.__map = {}                     # key --> [prev,key,next]
>         if iterable is not None:
>             self |= iterable
...
>     def add(self, key):
>         if not self.__map:
>             self.start = key
>             self.__map = {key: [key,key,key]}
...
Two responses:
(1) No, it doesn't have the reference problem, but it does replace
     a reference with map lookup (at a performance cost).
and
(2) Why, oh why, do people feel so comforted adding double_underscores
     to data structures?  If I want to inherit from your mapping in order
     to log the attempts to discard a key not actually in the set, I
     have to either us the nasty name mangling to get at self.__map, or
     name my subclass OrderedSet and take advantage of a not-guaranteed
     name mangling.  What on earth makes you unwilling to go with "_map"
     and credit your code's consumers with a bit of common sense?

Sorry, this latter rant has been building up for a while (spurred on by
a sojourn into the unittest code where they have the private disease in
spades.

--Scott David Daniels
Scott.Daniels at Acm.Org