README.md
1[](https://travis-ci.org/LuminosoInsight/ordered-set)
2[](https://codecov.io/github/LuminosoInsight/ordered-set?branch=master)
3[](https://pypi.python.org/pypi/ordered-set)
4
5An OrderedSet is a mutable data structure that is a hybrid of a list and a set.
6It remembers the order of its entries, and every entry has an index number that
7can be looked up.
8
9
10## Usage examples
11
12An OrderedSet is created and used like a set:
13
14 >>> from ordered_set import OrderedSet
15
16 >>> letters = OrderedSet('abracadabra')
17
18 >>> letters
19 OrderedSet(['a', 'b', 'r', 'c', 'd'])
20
21 >>> 'r' in letters
22 True
23
24It is efficient to find the index of an entry in an OrderedSet, or find an
25entry by its index. To help with this use case, the `.add()` method returns
26the index of the added item, whether it was already in the set or not.
27
28 >>> letters.index('r')
29 2
30
31 >>> letters[2]
32 'r'
33
34 >>> letters.add('r')
35 2
36
37 >>> letters.add('x')
38 5
39
40OrderedSets implement the union (`|`), intersection (`&`), and difference (`-`)
41operators like sets do.
42
43 >>> letters |= OrderedSet('shazam')
44
45 >>> letters
46 OrderedSet(['a', 'b', 'r', 'c', 'd', 'x', 's', 'h', 'z', 'm'])
47
48 >>> letters & set('aeiou')
49 OrderedSet(['a'])
50
51 >>> letters -= 'abcd'
52
53 >>> letters
54 OrderedSet(['r', 'x', 's', 'h', 'z', 'm'])
55
56The `__getitem__()` and `index()` methods have been extended to accept any
57iterable except a string, returning a list, to perform NumPy-like "fancy
58indexing".
59
60 >>> letters = OrderedSet('abracadabra')
61
62 >>> letters[[0, 2, 3]]
63 ['a', 'r', 'c']
64
65 >>> letters.index(['a', 'r', 'c'])
66 [0, 2, 3]
67
68OrderedSet implements `__getstate__` and `__setstate__` so it can be pickled,
69and implements the abstract base classes `collections.MutableSet` and
70`collections.Sequence`.
71
72
73## Interoperability with NumPy and Pandas
74
75An OrderedSet can be used as a bi-directional mapping between a sparse
76vocabulary and dense index numbers. As of version 3.1, it accepts NumPy arrays
77of index numbers as well as lists.
78
79This combination of features makes OrderedSet a simple implementation of many
80of the things that `pandas.Index` is used for, and many of its operations are
81faster than the equivalent pandas operations.
82
83For further compatibility with pandas.Index, `get_loc` (the pandas method for
84looking up a single index) and `get_indexer` (the pandas method for fancy
85indexing in reverse) are both aliases for `index` (which handles both cases
86in OrderedSet).
87
88
89## Type hinting
90To use type hinting features install `ordered-set-stubs` package from
91[PyPI](https://pypi.org/project/ordered-set-stubs/):
92
93 $ pip install ordered-set-stubs
94
95
96## Authors
97
98OrderedSet was implemented by Robyn Speer. Jon Crall contributed changes and
99tests to make it fit the Python set API.
100
101
102## Comparisons
103
104The original implementation of OrderedSet was a [recipe posted to ActiveState
105Recipes][recipe] by Raymond Hettiger, released under the MIT license.
106
107[recipe]: https://code.activestate.com/recipes/576694-orderedset/
108
109Hettiger's implementation kept its content in a doubly-linked list referenced by a
110dict. As a result, looking up an item by its index was an O(N) operation, while
111deletion was O(1).
112
113This version makes different trade-offs for the sake of efficient lookups. Its
114content is a standard Python list instead of a doubly-linked list. This
115provides O(1) lookups by index at the expense of O(N) deletion, as well as
116slightly faster iteration.
117
118In Python 3.6 and later, the built-in `dict` type is inherently ordered. If you
119ignore the dictionary values, that also gives you a simple ordered set, with
120fast O(1) insertion, deletion, iteration and membership testing. However, `dict`
121does not provide the list-like random access features of OrderedSet. You
122would have to convert it to a list in O(N) to look up the index of an entry or
123look up an entry by its index.
124
125
126## Compatibility
127
128OrderedSet is automatically tested on Python 2.7, 3.4, 3.5, 3.6, and 3.7.
129We've checked more informally that it works on PyPy and PyPy3.
130
){kind=link}
){kind=link}
){kind=link}