Does Python have an ordered set?
Update: This answer is obsolete as of Python 3.7. See jrc's answer above for a better solution. Will keep this answer here only for historical reasons.
An ordered set is functionally a special case of an ordered dictionary.
The keys of a dictionary are unique. Thus, if one disregards the values in an ordered dictionary (e.g. by assigning them None
), then one has essentially an ordered set.
As of Python 3.1 and 2.7 there is collections.OrderedDict
. The following is an example implementation of an OrderedSet. (Note that only few methods need to be defined or overridden: collections.OrderedDict
and collections.MutableSet
do the heavy lifting.)
import collections
class OrderedSet(collections.OrderedDict, collections.MutableSet):
def update(self, *args, **kwargs):
if kwargs:
raise TypeError("update() takes no keyword arguments")
for s in args:
for e in s:
self.add(e)
def add(self, elem):
self[elem] = None
def discard(self, elem):
self.pop(elem, None)
def __le__(self, other):
return all(e in other for e in self)
def __lt__(self, other):
return self <= other and self != other
def __ge__(self, other):
return all(e in self for e in other)
def __gt__(self, other):
return self >= other and self != other
def __repr__(self):
return 'OrderedSet([%s])' % (', '.join(map(repr, self.keys())))
def __str__(self):
return '{%s}' % (', '.join(map(repr, self.keys())))
difference = property(lambda self: self.__sub__)
difference_update = property(lambda self: self.__isub__)
intersection = property(lambda self: self.__and__)
intersection_update = property(lambda self: self.__iand__)
issubset = property(lambda self: self.__le__)
issuperset = property(lambda self: self.__ge__)
symmetric_difference = property(lambda self: self.__xor__)
symmetric_difference_update = property(lambda self: self.__ixor__)
union = property(lambda self: self.__or__)
There is an ordered set (possible new link) recipe for this which is referred to from the Python 2 Documentation. This runs on Py2.6 or later and 3.0 or later without any modifications. The interface is almost exactly the same as a normal set, except that initialisation should be done with a list.
OrderedSet([1, 2, 3])
This is a MutableSet, so the signature for .union
doesn't match that of set, but since it includes __or__
something similar can easily be added:
@staticmethod
def union(*sets):
union = OrderedSet()
union.union(*sets)
return union
def union(self, *sets):
for set in sets:
self |= set
Implementations on PyPI
While others have pointed out that there is no built-in implementation of an insertion-order preserving set in Python (yet), I am feeling that this question is missing an answer which states what there is to be found on PyPI.
There are the packages:
- ordered-set (Python based)
- orderedset (Cython based)
- collections-extended
- boltons (under iterutils.IndexedSet, Python-based)
- oset (last updated in 2012)
Some of these implementations are based on the recipe posted by Raymond Hettinger to ActiveState which is also mentioned in other answers here.
Some differences
- ordered-set (version 1.1)
- advantage: O(1) for lookups by index (e.g.
my_set[5]
) - oset (version 0.1.3)
- advantage: O(1) for
remove(item)
- disadvantage: apparently O(n) for lookups by index
Both implementations have O(1) for add(item)
and __contains__(item)
(item in my_set
).
The answer is no, but you can use collections.OrderedDict
from the Python standard library with just keys (and values as None
) for the same purpose.
Update: As of Python 3.7 (and CPython 3.6), standard dict
is guaranteed to preserve order and is more performant than OrderedDict
. (For backward compatibility and especially readability, however, you may wish to continue using OrderedDict
.)
Here's an example of how to use dict
as an ordered set to filter out duplicate items while preserving order, thereby emulating an ordered set. Use the dict
class method fromkeys()
to create a dict, then simply ask for the keys()
back.
>>> keywords = ['foo', 'bar', 'bar', 'foo', 'baz', 'foo']
>>> list(dict.fromkeys(keywords))
['foo', 'bar', 'baz']