Python has an ordered dictionary. What about an ordered set?
16 Answers
The answer is no, but as of Python 3.7 you can use the simple dict
from the Python standard library with just keys (and values as None
) for the same purpose.
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']
For older versions of Python, use the collections.OrderedDict
-
7Maybe worth mentioning that this also works (faster) with vanilla
dict.fromkeys()
. But in that case, key order is only preserved in CPython 3.6+ implementations, soOrderedDict
is a more portable solution when order matters.– jezDec 21, 2018 at 21:29 -
6
-
45@user474491 Unlike
dict
,set
in Python 3.7+ unfortunately does not preserve order.– c zJan 24, 2020 at 15:02 -
9@DavidEhrmann Keep reading a little further on the same link: "Update December 2017: dicts retaining insertion order is guaranteed for Python 3.7"– jrcSep 2, 2020 at 8:48
-
9The linked answer says
dict
retains insertion order, but it doesn't necessarily retain order after operations on its contents. It also points out several features thatOrderedDict
has, butdict
does not.dict
may be sufficient for the specific problem posed in this question, but one shouldn't takedict
's support for retaining insertion order to mean that it is a complete replacement forOrderedDict
. May 24, 2022 at 14:52
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
-
6I selected my own answer because the reference from the documentation makes this close to an official answer– CasebashDec 10, 2010 at 0:59
-
58The interface is NOT exactly the same as the normal set object, many essential methods are missing such as
update
,union
,intersection
.– xAppleDec 14, 2012 at 12:48 -
5FYI, I noticed that a slightly modified version of the recipe cited in this answer has been added to PyPi as "ordered-set" Feb 24, 2014 at 16:35
-
8I'm pretty sure you're not allowed to have two methods both called
union
in the same class. The last one will "win" and the first one will fail to exist at runtime. This is becauseOrderedSet.union
(no parens) has to refer to a single object.– KevinDec 5, 2014 at 17:38 -
4There is also "orderedset" package which is based on the same recipe but implemented in Cython -- pypi.python.org/pypi/orderedset .– mbdevplAug 31, 2016 at 11:17
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__)
-
1@Casebash: yes, one may want to define a class
OrderedSet
which subclassesOrderedDict
andabc.Set
and then define__len__
,__iter__
and__contains__
. Oct 31, 2009 at 11:12 -
5This is true, but you do have a lot of wasted space as a result, which leads to suboptimal performance. Oct 3, 2012 at 15:11
-
5An addition; collections.OrderedDict is also available in python 2.7. Sep 18, 2013 at 12:11
-
5Doing
OrderedSet([1,2,3])
raises a TypeError. How does the constructor even work? Missing usage example.– xAppleApr 28, 2017 at 13:06 -
4This answer needs to be rewritten to: (1) support initialization using a list of tuple, (2) use
dict
(since it is now ordered) via composition rather than inheritance, and (3) usecollections.abc.MutableSet
. Apr 19, 2020 at 0:58
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)
- 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
).
-
3A new contender is collections_extended.setlist. Functions like
set.union
don't work on it though, even though it inheritscollections.abc.Set
. Mar 16, 2016 at 23:20 -
5
-
There is also
SortedSet
from sortedcontainers 2.3.0 with a bunch of other sorted stuff.– ceprioApr 28, 2021 at 21:11
I can do you one better than an OrderedSet: boltons has a pure-Python, 2/3-compatible IndexedSet
type that is not only an ordered set, but also supports indexing (as with lists).
Simply pip install boltons
(or copy setutils.py
into your codebase), import the IndexedSet
and:
>>> from boltons.setutils import IndexedSet
>>> x = IndexedSet(list(range(4)) + list(range(8)))
>>> x
IndexedSet([0, 1, 2, 3, 4, 5, 6, 7])
>>> x - set(range(2))
IndexedSet([2, 3, 4, 5, 6, 7])
>>> x[-1]
7
>>> fcr = IndexedSet('freecreditreport.com')
>>> ''.join(fcr[:fcr.index('.')])
'frecditpo'
Everything is unique and retained in order. Full disclosure: I wrote the IndexedSet
, but that also means you can bug me if there are any issues.
-
Indexing does not work when negative indexes are supplied. For instance, this s[-4:-1] returns IndexedSet([]) on a very non-empty set.– darloveJan 1, 2021 at 11:31
-
1@darlove Not sure what version you're on but negative indexes are supported and your supplied case does not reproduce on the issue you opened: github.com/mahmoud/boltons/issues/274 Jan 6, 2021 at 22:45
If you're using the ordered set to maintain a sorted order, consider using a sorted set implementation from PyPI. The sortedcontainers module provides a SortedSet for just this purpose. Some benefits: pure-Python, fast-as-C implementations, 100% unit test coverage, hours of stress testing.
Installing from PyPI is easy with pip:
pip install sortedcontainers
Note that if you can't pip install
, simply pull down the sortedlist.py and sortedset.py files from the open-source repository.
Once installed you can simply:
from sortedcontainers import SortedSet
help(SortedSet)
The sortedcontainers module also maintains a performance comparison with several alternative implementations.
For the comment that asked about Python's bag data type, there's alternatively a SortedList data type which can be used to efficiently implement a bag.
-
Note that the
SortedSet
class there requires members to be comparable and hashable. Nov 24, 2014 at 19:28 -
7@gsnedders The builtins
set
andfrozenset
also require elements to be hashable. The comparable constraint is the addition forSortedSet
, but it's also an obvious constraint.– gotgenesJan 29, 2015 at 19:23 -
2As the name suggests, this does not maintain order. It is nothing but sorted(set([sequence])) which makes better?– ldmtwoNov 6, 2018 at 0:32
-
@ldmtwo I'm not sure which you're referring to but just to be clear, SortedSet as part of Sorted Containers does maintain sorted order.– GrantJNov 6, 2018 at 17:50
-
3@GrantJ - It is the difference between whether it maintains insertion order or sort order. Most of the other answers are regarding insertion order. I think you are already aware of this based on your first sentence, but it's probably what ldmtwo is saying.– JustinApr 10, 2019 at 14:00
As other answers mention, as for python 3.7+, the dict is ordered by definition. Instead of subclassing OrderedDict
we can subclass abc.collections.MutableSet
or typing.MutableSet
using the dict's keys to store our values.
import typing
T = typing.TypeVar("T")
class OrderedSet(typing.MutableSet[T]):
"""A set that preserves insertion order by internally using a dict."""
def __init__(self, iterable: typing.Iterator[T]):
self._d = dict.fromkeys(iterable)
def add(self, x: T) -> None:
self._d[x] = None
def discard(self, x: T) -> None:
self._d.pop(x, None)
def __contains__(self, x: object) -> bool:
return self._d.__contains__(x)
def __len__(self) -> int:
return self._d.__len__()
def __iter__(self) -> typing.Iterator[T]:
return self._d.__iter__()
def __str__(self):
return f"{{{', '.join(str(i) for i in self)}}}"
def __repr__(self):
return f"<OrderedSet {self}>"
Then just:
x = OrderedSet([1, 2, -1, "bar"])
x.add(0)
assert list(x) == [1, 2, -1, "bar", 0]
I added this code, with some tests, in a small library, so anyone can just pip install
it.
-
2Don't use this as-is.
discard
should never ever raise aKeyError
. Also note that this doesn't provide a sensible__repr__
Mar 22, 2021 at 22:50 -
@JasonForbes You are right —in fact we addressed your comments in the linked repo. So I just brought those fixes in this answer. Thank you for pointing it out! :-)– bustawinMar 25, 2021 at 22:10
In case you're already using pandas in your code, its Index
object behaves pretty like an ordered set, as shown in this article.
Examples from the article:
indA = pd.Index([1, 3, 5, 7, 9])
indB = pd.Index([2, 3, 5, 7, 11])
indA & indB # intersection
indA | indB # union
indA - indB # difference
indA ^ indB # symmetric difference
-
Can you include an example in this answer? Links tend to be broken after some time.– AlechanApr 11, 2020 at 16:31
-
1for the difference between sets, you actually need to use
indA.difference(indB)
, the minus sign performs standard subtraction– gg349Apr 28, 2020 at 15:22 -
3It's important to note that
pd.Index
allows for duplicate elements, which one would not expect from an actual Pythonset
. May 24, 2021 at 13:30
A little late to the game, but I've written a class setlist
as part of collections-extended
that fully implements both Sequence
and Set
>>> from collections_extended import setlist
>>> sl = setlist('abracadabra')
>>> sl
setlist(('a', 'b', 'r', 'c', 'd'))
>>> sl[3]
'c'
>>> sl[-1]
'd'
>>> 'r' in sl # testing for inclusion is fast
True
>>> sl.index('d') # so is finding the index of an element
4
>>> sl.insert(1, 'd') # inserting an element already in raises a ValueError
ValueError
>>> sl.index('d')
4
GitHub: https://github.com/mlenzen/collections-extended
Documentation: http://collections-extended.lenzm.net/en/latest/
There's no OrderedSet
in official library.
I make an exhaustive cheatsheet of all the data structure for your reference.
DataStructure = {
'Collections': {
'Map': [
('dict', 'OrderDict', 'defaultdict'),
('chainmap', 'types.MappingProxyType')
],
'Set': [('set', 'frozenset'), {'multiset': 'collection.Counter'}]
},
'Sequence': {
'Basic': ['list', 'tuple', 'iterator']
},
'Algorithm': {
'Priority': ['heapq', 'queue.PriorityQueue'],
'Queue': ['queue.Queue', 'multiprocessing.Queue'],
'Stack': ['collection.deque', 'queue.LifeQueue']
},
'text_sequence': ['str', 'byte', 'bytearray']
}
-
Some odd things in this cheatsheet: according to collections.abc, Sequences are Collections, not a sibling. And iterator does not support indexing, so shouldn't be on the same group as lists and tuples. Also, all text_sequences are also Sequence Oct 30, 2021 at 9:28
As others have said, OrderedDict
is a superset of an ordered set in terms of functionality, but if you need a set for interacting with an API and don't need it to be mutable, OrderedDict.keys()
is actually an implementation abc.collections.Set
:
import random
from collections import OrderedDict, abc
a = list(range(0, 100))
random.shuffle(a)
# True
a == list(OrderedDict((i, 0) for i in a).keys())
# True
isinstance(OrderedDict().keys(), abc.Set)
The caveats are immutability and having to build up the set like a dict, but it's simple and only uses built-ins.
The ParallelRegression package provides a setList( ) ordered set class that is more method-complete than the options based on the ActiveState recipe. It supports all methods available for lists and most if not all methods available for sets.
There is a pip library that does this:
pip install ordered-set
Then you can use it:
from ordered_set import OrderedSet
Just use pd.unique
from pandas
- does exactly what you need!
>>> import pandas as pd
>>> pd.unique([3, 1, 4, 5, 2, 2])
array([3, 1, 4, 5, 2])
This answer is for completeness sake. If the length of your set
is small, and your code is single-threaded, a list
could work just fine as it's implicitly ordered.
if not new_item in my_list:
my_list.append(new_item)
If using this approach:
- To append or remove an item, first check for presence as in the code above.
- To compare equality, use
set(my_list)
.
Checking for presence in a list of course has an O(n) complexity, but this could be acceptable for a small list, especially if high performance isn't required.
-
2The main issue with this approach is that adding runs in O(n). Meaning it gets slower with big lists. Python's built-in sets are very good at making adding elements faster. But for simple use-cases, it certainly does work!– DraconisNov 9, 2018 at 4:19
-
This answer should not be deleted because this approach works acceptably for small lists where the best performance isn't required. Jul 14 at 18:05
For many purposes simply calling sorted will suffice. For example
>>> s = set([0, 1, 2, 99, 4, 40, 3, 20, 24, 100, 60])
>>> sorted(s)
[0, 1, 2, 3, 4, 20, 24, 40, 60, 99, 100]
If you are going to use this repeatedly, there will be overhead incurred by calling the sorted function so you might want to save the resulting list, as long as you're done changing the set. If you need to maintain unique elements and sorted, I agree with the suggestion of using OrderedDict from collections with an arbitrary value such as None.
-
48The purpose for OrderedSet is to be able to get the items in the order which they where added to the set. You example could maybe called SortedSet... Feb 21, 2013 at 14:01
collections.Counter
is Python's bag.dict
is now insertion-ordered (guaranteed since Python 3.7)