Python有有序集合吗？

Question

Python有一个叫做有序字典的东西。那么，有序集合呢？

Answer 1

更新: 这个回答在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__)

Answer 2

答案是否定的，不过从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。

Answer 3

这里有一个关于有序集合的做法（可能还有新链接），这个做法在Python 2 文档中有提到。它可以在Python 2.6及以上版本和3.0及以上版本上运行，不需要任何修改。这个有序集合的使用方式和普通集合几乎一模一样，唯一的不同是初始化时需要用一个列表。

OrderedSet([1, 2, 3])

这个是一个可变集合（MutableSet），所以它的.union方法和普通集合的定义不太一样，但因为它包含了__or__，所以可以很容易地添加类似的功能：

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

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

Python有有序集合吗？

16 个回答

撰写回答