Python有有序集吗？

答案是否定的，但您可以将 Python 标准库中的 collections.OrderedDict 与键（和值作为 None）一起用于相同的目的。

更新：从 Python 3.7（和 CPython 3.6）开始，标准 dict 是 guaranteed to preserve order，并且比 OrderedDict 性能更高。 （但是，为了向后兼容，尤其是可读性，您可能希望继续使用 OrderedDict。）

下面是一个示例，说明如何将 dict 用作有序集以在保留顺序的同时过滤掉重复项，从而模拟有序集。使用 dict 类方法 fromkeys() 创建一个 dict，然后简单地要求 keys() 返回。

>>> keywords = ['foo', 'bar', 'bar', 'foo', 'baz', 'foo']

>>> list(dict.fromkeys(keywords))
['foo', 'bar', 'baz']

---

对此有一个 ordered set（可能是 new link）配方，从 Python 2 Documentation 中引用。这可以在 Py2.6 或更高版本以及 3.0 或更高版本上运行，无需任何修改。该接口几乎与普通集合完全相同，只是应该使用列表进行初始化。

OrderedSet([1, 2, 3])

这是一个 MutableSet，因此 .union 的签名与 set 的签名不匹配，但由于它包含 __or__，因此可以轻松添加类似的内容：

@staticmethod
def union(*sets):
    union = OrderedSet()
    union.union(*sets)
    return union

def union(self, *sets):
    for set in sets:
        self |= set

---

更新：此答案自 Python 3.7 起已过时。有关更好的解决方案，请参见上面的 jrc's answer。仅出于历史原因将在此处保留此答案。

有序集在功能上是有序字典的特例。

字典的键是唯一的。因此，如果忽略有序字典中的值（例如，通过分配它们None），则本质上具有有序集。

从 Python 3.1 和 2.7 开始，有 collections.OrderedDict。以下是 OrderedSet 的示例实现。 （请注意，只有少数方法需要定义或覆盖：collections.OrderedDict 和 collections.MutableSet 完成繁重的工作。）

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__)

---

PyPI 上的实现

虽然其他人指出 Python 中没有内置的插入顺序保留集实现（目前），但我觉得这个问题缺少一个答案，说明在 PyPI 上可以找到什么。

有以下包：

有序集（基于 Python）

有序集（基于 Cython）

集合扩展

boltons（在 iterutils.IndexedSet 下，基于 Python）

oset（最后更新于 2012 年）

其中一些实现基于此处的其他答案中也提到的 recipe posted by Raymond Hettinger to ActiveState。

一些差异

有序集（1.1 版）

优点：O(1) 用于按索引查找（例如 my_set[5]）

oset（版本 0.1.3）

优点：O(1) for remove(item)

缺点：显然 O(n) 用于按索引查找

对于 add(item) 和 __contains__(item) (item in my_set)，两种实现都有 O(1)。

---

我可以比 OrderedSet 做得更好：boltons 的 a pure-Python, 2/3-compatible IndexedSet type 不仅是一个有序集，而且还支持索引（与列表一样）。

只需 pip install boltons（或将 setutils.py 复制到您的代码库中），导入 IndexedSet 并：

>>> 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'

一切都是独一无二的，并按顺序保留。完全披露：我写了 IndexedSet，但这也意味着 you can bug me if there are any issues。 :)

---

如果您使用有序集来维护排序顺序，请考虑使用 PyPI 中的排序集实现。 sortedcontainers 模块为此提供了一个 SortedSet。一些好处：纯 Python、快速的 C 实现、100% 的单元测试覆盖率、数小时的压力测试。

使用 pip 从 PyPI 安装很容易：

pip install sortedcontainers

请注意，如果您不能 pip install，只需从 open-source repository 中拉下 sortedlist.py 和 sortedset.py 文件。

安装后，您可以简单地：

from sortedcontainers import SortedSet
help(SortedSet)

sortedcontainers 模块还维护一个 performance comparison 以及几个替代实现。

对于询问 Python 的包数据类型的评论，还有一个 SortedList 数据类型可用于有效地实现包。

---

正如其他答案所提到的，对于 python 3.7+，dict 是按定义排序的。除了继承 OrderedDict，我们还可以使用 dict 的键来继承 abc.collections.MutableSet 或 typing.MutableSet 来存储我们的值。

import itertools
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}>"

然后只是：

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，所以任何人都可以pip install它。

---

如果您已经在代码中使用了 pandas，那么它的 Index 对象的行为就像一个有序集，如 this 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

---

游戏有点晚了，但我编写了一个类 setlist 作为 collections-extended 的一部分，它完全实现了 Sequence 和 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

文档：http://collections-extended.lenzm.net/en/latest/

派皮：https://pypi.python.org/pypi/collections-extended

---

官方图书馆没有OrderedSet。我制作了所有数据结构的详尽备忘单供您参考。

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']
}

---

正如其他人所说，就功能而言，OrderedDict 是有序集合的超集，但如果您需要一个集合来与 API 交互并且不需要它是可变的，{2 } 实际上是一个实现 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)   

需要注意的是不可变性并且必须像字典一样构建集合，但它很简单并且只使用内置函数。

---

ParallelRegression 包提供了一个 setList( ) 有序集类，它比基于 ActiveState 配方的选项更完整。它支持所有可用于列表的方法，以及大多数（如果不是全部）可用于集合的方法。

---

注意：jrc 答案的扩展，因为如何使用 OrderDict 不包含在该答案中。

一个很好的解释，在 Create OrderedSet in Python 3.7 and Before 解释了适当的例子

我们有两种方法 - (1) collections.OrderedDict 和 (2) dict

First 用于 3.7 之前的 python，而 later 用于 python 3.7 及更高版本。

在 python 3.7 及更高版本中创建有序集，如下所示 -

keywords = ['hello', 'aurav', 'hello', 'narendra', 'foo', 'foo']
sampleList = list(dict.fromkeys(keywords))

print(type(sampleList))

for item in sampleList:
    print(item)

运行上述程序时，输出为 -

<class 'list'>
hello
aurav
narendra
foo

查看如何create OrderedSet using OrderDict from collections

---

有一个 pip library 可以做到这一点：

pip install ordered-set

然后你可以使用它：

from ordered_set import OrderedSet

---

对于许多目的，只需调用 sorted 就足够了。例如

>>> 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]

如果您要重复使用它，调用 sorted 函数会产生开销，因此您可能希望保存结果列表，只要您完成更改集合。如果您需要维护唯一的元素并进行排序，我同意从具有任意值（例如 None）的集合中使用 OrderedDict 的建议。

---

所以我也有一个小清单，我显然有可能引入非唯一值。

我搜索了某种唯一列表的存在，但后来意识到在添加元素之前测试元素的存在就可以了。

if(not new_element in my_list):
    my_list.append(new_element)

我不知道这种简单方法是否有警告，但它解决了我的问题。

---