Python有有序集合吗？

Question

Python有一个有序字典。那么有没有有序集合呢？

- Casebash

---

相反的情况又如何呢，一袋子东西呢？（无序且不唯一） - wim

@wim collections.Counter 是 Python 中的一个“袋子”。 - flornquake

如果某个东西被添加了两次怎么办？应该采取什么立场？ - McKay

如果按照collections.OrderDict的行为来进行，那么它仍然会保持初始添加时的位置。 - wojtow

警告：这里有些答案已经过时了。例如，dict现在是按插入顺序排序的（自Python 3.7起保证）。 - Walter Tross

Answer 1

答案是否定的，但是从Python 3.7开始，你可以使用Python标准库中的简单dict，只使用键（值为None）来达到相同的目的。

下面是一个使用dict作为有序集合来过滤重复项并保持顺序的示例，从而模拟有序集合。使用dict类方法fromkeys()创建一个字典，然后简单地要求返回keys()即可。

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

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

---

对于较旧版本的Python，请使用collections.OrderedDict。

- jrc

---

也许值得一提的是，使用普通的 dict.fromkeys() 也可以（更快地）实现相同的功能。但在这种情况下，只有在使用CPython 3.6+实现时才能保留键的顺序，因此在需要保持顺序时，使用OrderedDict是一个更便携的解决方案。 - jez

Python 3.7及以上版本的Set是否也保留顺序？ - Pierre Carbonnelle

与 Python 中的 dict 不同，Python 3.7+ 中的 set 不幸地不保留顺序。 - c z

请继续阅读同样的链接： "2017年12月更新：对于Python 3.7，保留插入顺序的字典是得到保证的。" - jrc

这个链接中的答案说dict保留插入顺序，但在对其内容进行操作后不一定会保留顺序。 它还指出了OrderedDict拥有但dict没有的几个特性。 dict可能足以解决这个问题，但不能因为dict支持保留插入顺序就认为它完全替代了OrderedDict。 - Mr. Lance E Sloan

Answer 2

有一个有序集合（可能新链接）的方案可供使用，文档来源于Python 2文档。这个方案可以在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

- Casebash

---

我选择了自己的答案，因为文档中的参考使得这个答案接近于官方答案。 - Casebash

接口与普通集合对象并不完全相同，许多重要的方法都不存在，比如update、union和intersection。 - xApple

我注意到这个答案中引用的配方的稍作修改的版本已经以“ordered-set”的名称添加到了PyPI上。请查看链接。 - Geoffrey Hing

在同一个类中不允许有两个被称为 union 的方法，最后一个会覆盖前面的方法并在运行时失效。这是因为 OrderedSet.union(没有括号)必须引用单个对象。 - Kevin

还有一个名为"orderedset"的包，它基于相同的配方但是用Cython实现。-- https://pypi.python.org/pypi/orderedset 。 - mbdevpl

请参考以下答案：https://dev59.com/DnI-5IYBdhLWcg3w0cOG#53657523。在Python 3.7+中，字典会保留顺序。否则，请使用OrderedDict。 - mattyb

Answer 3

更新：截至Python 3.7，此回答已过时。请参见上面jrc的答案以获取更好的解决方案。只为历史原因保留此答案。

---

一个有序集合从功能上来说是有序字典的一种特殊情况。

字典的键是唯一的。因此，如果忽略有序字典中的值（例如将它们赋值为None），那么基本上就得到了一个有序的集合。

自Python 3.1和2.7版本以来，有collections.OrderedDict。以下是一个有序集合的示例实现。（注意，只需要定义或重写少量方法：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__)

- Stephan202

---

这是正确的，但是由此产生了很多浪费空间，导致了次优的性能。 - Daniel Kats

补充说明：在Python 2.7中也可以使用collections.OrderedDict。 - Nurbldoff

调用 OrderedSet([1,2,3]) 会引发 TypeError 错误。构造函数是如何工作的？缺少使用示例。 - xApple

这个答案需要重新编写以支持使用元组列表进行初始化，通过组合而不是继承使用dict（因为它现在是有序的），并且使用collections.abc.MutableSet。 - Asclepius

@Stephan202 它仍然可以工作，只是自Py2以来有一些变化。但这是可以预料的，因为这是一个有点小众和非常规的开发 :) 只是留下了一个评论，指引人们朝着正确的方向前进，甚至都不记得我是如何修复它的呵呵。 - Torxed

Answer 4

在PyPI上的实现

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

以下是一些包:

• ordered-set (基于Python)
• collections-extended
• boltons (位于iterutils.IndexedSet下，基于Python)
• oset (最后更新于2012年)

一些这些实现是基于Raymond Hettinger在ActiveState上发布的配方，这也在其他答案中提到过。

一些区别：

- 有序集合（版本1.1） - 优点：按索引查找（例如my_set[5]）的时间复杂度为O(1) - oset（版本0.1.3） - 优点：remove(item)的时间复杂度为O(1) - 缺点：按索引查找的时间复杂度似乎为O(n)

这两种实现都具有add(item)和__contains__(item)（item in my_set）的时间复杂度为O(1)。

- Daniel K

---

一个新的竞争者是collections_extended.setlist。尽管它继承自collections.abc.Set，但像set.union这样的函数在其上不起作用。 - Tim Diels

"OrderedSet"现在支持"remove"方法。具体信息请参见文档。 - warvariuc

还有SortedSet，它来自sortedcontainers 2.3.0，并带有许多其他有序的内容。 - ceprio

Answer 5

我可以给你一个比OrderedSet更好的选择：boltons库有一个纯Python的、2/3兼容的IndexedSet类型，它不仅是一个有序集合，还支持索引（就像列表一样）。

只需执行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，但这也意味着你可以找我解决任何问题。

- Mahmoud Hashemi

---

当提供负索引时，索引不起作用。例如，对于一个非空集合，s[-4：-1]返回IndexedSet（[]）。 - darlove

@darlove 不确定你使用的是哪个版本，但负索引是被支持的，而且你提供的案例在你打开的问题中无法重现：https://github.com/mahmoud/boltons/issues/274 - Mahmoud Hashemi

Answer 6

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

使用pip从PyPI安装很容易：

pip install sortedcontainers

请注意，如果您无法通过pip安装，请从开源库中下载sortedlist.py和sortedset.py文件。

安装完成后，您可以简单地执行以下操作：

from sortedcontainers import SortedSet
help(SortedSet)

sortedcontainers模块还与几种替代实现进行了性能比较。

对于询问Python的bag数据类型的评论，可以使用SortedList数据类型来高效地实现bag。

- GrantJ

---

请注意，那里的SortedSet类要求成员是可比较和可哈希的。 - gsnedders

内置函数set和frozenset也要求元素是可哈希的。SortedSet增加了一个可比较性的限制，但这也是一个显而易见的约束。 - gotgenes

正如其名称所示，它不维护顺序。它只是sorted(set([sequence]))的简写，哪个更好？ - ldmtwo

@ldmtwo，我不确定你指的是哪一个，但为了明确起见，Sorted Containers中的SortedSet确实维护有序。 - GrantJ

这句话的意思是：它的区别在于它是否维护插入顺序或排序顺序。其他大部分答案都涉及插入顺序。我认为你已经根据你的第一句话意识到了这一点，但这可能就是ldmtwo所说的。 - Justin

这个默认在LeetCode上可用。 - Eduardo

Answer 7

正如其他答案所提到的，对于Python 3.7+，字典是有序的。我们可以通过继承`OrderedDict`来实现，也可以使用字典的键来存储值，继承`abc.collections.MutableSet`或`typing.MutableSet`。

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]

我在一个小库中添加了这段代码，并进行了一些测试, 这样任何人都可以直接pip install它。

- bustawin

---

请不要直接使用这段代码。discard方法永远不应该抛出KeyError异常。此外，注意此代码没有提供合理的__repr__方法。 - Jason Forbes

@JasonForbes 你说得对 - 实际上我们在链接的代码库中解决了你的问题。所以我在这个答案中加入了那些修复。感谢你指出来！ :-) - bustawin

Answer 8

如果您已经在代码中使用pandas，它的Index对象就像有序集合一样工作，如此文所示。

以下是文章中的示例：

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

- Berislav Lopac

---

你能在这个回答中包含一个例子吗？链接往往会在一段时间后失效。 - Alechan

对于集合之间的差异，您实际上需要使用indA.difference(indB)，减号执行标准减法。 - gg349

需要注意的是，pd.Index 允许存在重复元素，这一点与 Python 中的 set 不同。 - jfaccioni

Answer 9

有点晚了，但我已经写了一个类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/

PyPI: https://pypi.python.org/pypi/collections-extended

- Michael Lenzen

Answer 10

官方库中没有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']
}

- AbstProcDo

---

这个速查表中有一些奇怪的地方：根据collections.abc，序列是集合，而不是同级。迭代器不支持索引，因此不应与列表和元组放在同一组中。此外，所有文本序列也都是序列。 - MestreLion