来自 技术 2019-04-17 00:00 的文章

python实现有序字典的详细介绍(附代码)

本篇文章给大家带来的内容是关于python实现有序字典的详细介绍(附代码),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

对于一个能够保存键值插入顺序的字典,是如何实现的?

主要有两点:

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

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

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)

【相关推荐:python教程】