Python有一个有序字典。那么有序集呢?


当前回答

有一个pip库是这样做的:

pip install ordered-set

然后你可以使用它:

from ordered_set import OrderedSet

其他回答

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

有一个pip库是这样做的:

pip install ordered-set

然后你可以使用它:

from ordered_set import OrderedSet

正如其他答案所提到的,对于python 3.7+,字典是按定义排序的。我们可以继承abc.collections.MutableSet或typing,而不是继承OrderedDict。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]

我在一个小库中添加了这些代码和一些测试,所以任何人都可以安装它。

答案是否定的,但是您可以使用集合。OrderedDict来自Python标准库,其中只有键(值为None),用于相同的目的。

更新:从Python 3.7(和CPython 3.6)开始,标准dict保证保留顺序,并且比OrderedDict性能更好。(但是,为了向后兼容性,特别是可读性,您可能希望继续使用OrderedDict。)

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

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

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

我可以为您提供一个比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是我写的,但这也意味着如果有任何问题,您可以找我麻烦。:)