In "__init__", iterable is checked to be "not None" before calling "update", which seems redundant because "update" does the same check before doing anything.

Although this recipe is far superior in that it actually is a set, my older recipe doesn't require the cyclic GC to be collected.http://code.activestate.com/recipes/528878/ It'd be fairly easy to combine the two.

Adam, this recipe doesn't use or rely on GC. Individual links get deleted immediately whendiscard() is called. Likewise, when the whole set is no longer needed, the__del__ method neatly deletes clears all of the links without waiting for GC.

Also, FWIW, there is an alternate version of this recipe using weakrefs. Seerecipe 576696. Neither version needs GC.

Hello Raymond,

I'm planing to use this module in LDTPv2 -http://ldtp.freedesktop.org under LGPLv2 license. If you have any objections, please write me to nagappan (at) gmail (dot) com. I have just mentioned your name in the file. I could not find your email id to specify in orderedset.py (http://cgit.freedesktop.org/ldtp/ldtp2/tree/ldtpd/orderedset.py). You can email me that as well, if you are interested with my proposal :)

You have done a wonderful job.

ThanksNagappan

The __eq__ operator for comparison with a non-OrderedSet returns

not self.isdisjoint(other)

but this returns False when comparing empty sets. I think the following should return True, not False:

OrderedSet([]) == set([])

I used this OrderedSet in a chain of functions processing lists. I soon found it was bogging down the calculations. I studied the code and find it is overloaded with Python features. For my purpose, the following simpler function runs 4 times faster.

def OrderedSet(alist):

    """ Creates an ordered set from a list of tuples or other hashable items """    mmap = {} # implements hashed lookup    oset = [] # storage for set    for item in alist:            #Save unique items in input order            if item not in mmap:                    mmap[item] = 1                    oset.append(item)    return oset

I've create a python package for this recipe and upload to Pypi as 'oset'. Code onhttp://gitorious.org/sleipnir/python-oset. It also works on python 2.5.

@Raymond: If you are interested in maintain this, it's all yours :)

Hello Raymond,

I created an MIT Licensed project that is using your OrderedSet recipe.I've added the required MIT License comment at the beginning:http://pypsifas.hg.sourceforge.net/hgweb/pypsifas/pypsifas/file/7bfaf2ed308c/psifas/datatypes/ordered_set.py

If you have any problem with that, please let me know.

Oren Zomeroren.zomer@gmail.com

I experienced memory problems (objects were not garbage-collected) when using this recipe, but the one based on weakref worked better.

The __del__ method is not guaranteed to be called when the set is not needed, it will only be called during the garbage collection phase, if the set is ever garbage-collected. Moreover, reference cycles can actually be made worse by the addition of a __del__ method:http://docs.python.org/2/library/gc.html#gc.garbage

For the record, removing the __del__ method actually got rid of the memory leak I was experiencing, at least on Python 2.7.

You may also want to check out theSortedContainers package. It's a pure-Python and fast implementation of SortedList, SortedDict, andSortedSet data types. "Sorted" isn't the same as "ordered" but it's sometimes what you actually want. There's also extensiveperformance benchmarks with comparisons.