问Python有有序集吗？

EN

有一个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

我可以做一个比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的bag数据类型的注释，也可以使用SortedList数据类型，该数据类型可用于高效地实现bag。