使用.index()方法的Python OrderedSet

Question

有没有人知道python的快速OrderedSet实现:

• 记住插入订单
• 有一个index()方法(就像列出一个提供)

我找到的所有实现都缺少.index()方法.

Answer 1

您始终可以将其添加到子类中.以下是OrderedSet您在评论中链接的基本实现:

class IndexOrderedSet(OrderedSet):
    def index(self, elem):
        if key in self.map:
            return next(i for i, e in enumerate(self) if e == elem)
        else:
            raise KeyError("That element isn't in the set")

您提到您只需要add,index并且按顺序迭代.您可以使用OrderedDictas storage来实现此目的.作为奖励,您可以将collections.Set抽象类子类化以获得其他集合操作frozenset的支持:

from itertools import count, izip
from collections import OrderedDict, Set

class IndexOrderedSet(Set):
    """An OrderedFrozenSet-like object
       Allows constant time 'index'ing
       But doesn't allow you to remove elements"""
    def __init__(self, iterable = ()):
        self.num = count()
        self.dict = OrderedDict(izip(iterable, self.num))
    def add(self, elem):
        if elem not in self:
            self.dict[elem] = next(self.num)
    def index(self, elem):
        return self.dict[elem]
    def __contains__(self, elem):
        return elem in self.dict
    def __len__(self):
        return len(self.dict)
    def __iter__(self):
        return iter(self.dict)
    def __repr__(self):
        return 'IndexOrderedSet({})'.format(self.dict.keys())

您不能进行子类化,collections.MutableSet因为您不能支持从集合中删除元素并保持索引正确.