Does Python have an ordered set?

В Python есть упорядоченный словарь. А как насчет упорядоченного набора?

Ответ отрицательный, но начиная с Python 3.7, вы можете использовать simple dict из стандартной библиотеки Python, используя только ключи (и значения как None) для той же цели.

Вот пример того, как использовать dict в качестве упорядоченного набора для фильтрации повторяющихся элементов с сохранением порядка, тем самым эмулируя упорядоченный набор. Используйте dict метод класса fromkeys() для создания dict, затем просто запросите keys() ответ.

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

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

Для более старых версий Python используйте collections.OrderedDict

Для этого существует рецепт упорядоченного набора (возможная новая ссылка), на который есть ссылка в документации Python 2. Это работает на Py2.6 или новее и 3.0 или новее без каких-либо изменений. Интерфейс почти точно такой же, как у обычного набора, за исключением того, что инициализация должна выполняться с помощью списка.

OrderedSet([1, 2, 3])

Это изменяемый набор, поэтому сигнатура для .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 выше для лучшего решения. Оставим этот ответ здесь только по историческим причинам.

Упорядоченный набор функционально является частным случаем упорядоченного словаря.

Ключи словаря уникальны. Таким образом, если пренебречь значениями в упорядоченном словаре (например, путем их присвоения 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__)

Реализации в PyPI

Хотя другие указывали, что в Python (пока) нет встроенной реализации набора, сохраняющего порядок вставки, я чувствую, что на этот вопрос отсутствует ответ, в котором указано, что можно найти в PyPI.

Существуют пакеты:

• упорядоченный набор (на основе Python)


• коллекции-расширенные


• болтоны (в разделе setutils.IndexedSet, на основе Python)


• oset (последнее обновление в 2012 году)

Некоторые из этих реализаций основаны на рецепте, опубликованном Раймондом Хеттингером в ActiveState, который также упоминается в других ответах здесь.

Некоторые отличия

• упорядоченный набор (версия 1.1)


• преимущество: O(1) для поиска по индексу (например, my_set[5])


• oset (версия 0.1.3)


• преимущество: O(1) для remove(item)


• недостаток: по-видимому, O (n) для поиска по индексу

В обеих реализациях есть O(1) для add(item) и __contains__(item) (item in my_set).