python实现有序字典

野性酷女 2021-12-21 23:59 247阅读 0赞

#### **对于一个能够保存键值插入顺序的字典，是如何实现的？** ####

主要有两点：

一个双向链表，用来记录字典的键值的插入顺序

一个键和链表节点的映射，主要用来删除键的时候，找到键对应的节点

**python代码实现**

class Link:
        __slots__ = 'prev', 'next', 'key'
    
    
    class OrderDict:
        def __init__(self):
            self.root = Link()
            self.map = {}
            self._node_map = {}
            self.root.next = self.root
            self.root.prev = self.root
    
        def __setitem__(self, key, value):
            if key in self._node_map:
                self.map[key] = value
            else:
                root = self.root
                last = root.prev
                link = Link()
                link.prev, link.next, link.key = last, root, key
                last.next = link
                root.prev = link
                self._node_map[key] = link
                self.map[key] = value
    
        def __getitem__(self, item):
            return self.map[item]
    
        def __delitem__(self, key):
            del self.map[key]
            link = self._node_map.pop(key)
            link_prev, link_next = link.prev, link.next
            link_prev.next, link_next.prev = link_next, link_prev
            link.prev, link.next = None, None
    
        def pop(self):
            """
            LIFO
            :return:
            """
            if not self._node_map:
                raise KeyError('dict is empty')
            root = self.root
            link = root.prev
            link_prev = link.prev
            link_prev.next = root
            root.prev = link_prev
            link.prev, link.next = None, None
            self._node_map.pop(link.key)
            return self.map.pop(link.key)
    
        def __iter__(self):
            root = self.root
            curr = root.next
            while curr != root:
                yield curr.key
                curr = curr.next
    
        def values(self):
            root = self.root
            curr = root.next
            while curr != root:
                yield self.map[curr.key]
                curr = curr.next

def __str__(self):
            root = self.root
            curr = root.next
            out = []
            while curr != root:
                out.append((curr.key, self.map[curr.key]))
                curr = curr.next
            return str(out)
    
    
    if __name__ == '__main__':
        d = OrderDict()
        d['a'] = '1'
        d['b'] = '2'
        d['c'] = 'c'    
        print(d)

转载于:https://www.cnblogs.com/time-read/p/10696198.html