python - 如何实现保留顺序并具有快速插入/删除的数据结构？

Question

我正在寻找一种保留其元素顺序的数据结构(在数据结构的生命周期中，元素的顺序可能会发生变化，因为客户端可能会移动元素)。

它应该允许快速搜索、在给定元素之前/之后插入、删除给定元素、查找第一个和最后一个元素以及从给定元素开始双向迭代。

什么是好的实现方案？

这是我的第一次尝试:

从 collections.abc.Iterable 和 collections.abc.MutableSet 派生的类，包含链表和字典。字典的键是元素，值是链表中的节点。字典将处理给定元素的节点搜索。一旦找到一个元素，链表就会处理之前/之后的插入、删除和迭代。字典将通过添​​加或删除相关的键/值对来更新。显然，使用这种方法，元素必须是可散列的且唯一的(否则，我们将需要另一层间接层，其中每个元素由自动分配的数字标识符表示，并且只有这些标识符存储为键)。

在我看来，这在渐近复杂性方面比 list 或 collections.deque 严格来说更好，但我可能是错的。 [编辑:错误，正如@roliu 所指出的。与 list 或 deque 不同，我无法在 O(1) 中通过数字索引找到元素。截至目前，它的复杂度为 O(N)，但我确信如果有必要的话，有某种方法可以使其变为 O(log N)。]

Answer 1

Raymond Hettinger's OrderedSet recipe 的稍微修改版本似乎满足了我所有的要求。我只添加了对基于位置的访问和读/写的支持。

# changes vs. original recipe at http://code.activestate.com/recipes/576696/:
# added a position parameter to add
# changed how pop works, and added popleft
# added find, get_start, get_end, next_pos, prev_pos, __getitem__, __setitem__

class OrderedSetPlus(collections.MutableSet, collections.Iterable):
    '''
    >>> oset = OrderedSetPlus([3, 3, 3, 2, 1, 8, 8])
    >>> oset.add(13)
    >>> p = oset.find(2)
    >>> oset.add(15, p)
    >>> oset
    OrderedSetPlus([3, 15, 2, 1, 8, 13])
    >>> p = oset.next_pos(p)
    >>> oset[p]
    1
    >>> oset.add(7, p)
    >>> oset
    OrderedSetPlus([3, 15, 2, 7, 1, 8, 13])
    >>> oset[p] = 20
    >>> oset
    OrderedSetPlus([3, 15, 2, 7, 20, 8, 13])
    '''

    class DuplicateElement(Exception):
        pass

    def __init__(self, iterable=None):
        self.end = end = [] 
        end += [None, end, end]         # sentinel node for doubly linked list
        self.map = {}                   # key --> [key, prev, next]
        if iterable is not None:
            self |= iterable

    def __len__(self):
        return len(self.map)

    def __contains__(self, key):
        return key in self.map

    def find(self, key):
        return self.map.get(key, None)

    # inserts element before the specified position
    # if pos is None, inserts at the end
    # position can only be obtained by calling instance methods
    def add(self, key, pos = None):
        if pos is None:
            pos = self.end
        if key not in self.map:
            curr = pos[PREV]
            curr[NEXT] = pos[PREV] = self.map[key] = [key, curr, pos]

    def discard(self, key):
        if key in self.map:        
            key, prev, next = self.map.pop(key)
            prev[NEXT] = next
            next[PREV] = prev

    def __iter__(self):
        end = self.end
        curr = end[NEXT]
        while curr is not end:
            yield curr[KEY]
            curr = curr[NEXT]

    def get_end(self):
        return self.end[PREV]

    def get_start(self):
        return self.end[NEXT]

    def next_pos(self, pos):
        pos = pos[NEXT]
        return None if pos is self.end else pos

    def prev_pos(self, pos):
        pos = pos[PREV]
        return None if pos is self.end else pos

    def __getitem__(self, pos):
        return pos[KEY]

    def __setitem__(self, pos, key):
        if key in self.map:
            raise DuplicateElement
        pos[KEY] = key

    def __reversed__(self):
        end = self.end
        curr = end[PREV]
        while curr is not end:
            yield curr[KEY]
            curr = curr[PREV]

    def popleft(self):
        return self.pop(pos = self.get_start())


    def pop(self, pos=None):
        if not self:
            raise IndexError()
        if pos is None:
            pos = self.get_end()
        key = self[pos]
        #key = next(reversed(self)) if last else next(iter(self))
        self.discard(key)
        return key

    def __repr__(self):
        return '{}({})'.format(self.__class__.__name__, list(self))

    def __eq__(self, other):
        if isinstance(other, OrderedSet):
            return len(self) == len(other) and list(self) == list(other)
        return set(self) == set(other)