python实现有序字典
2019-04-12 09:33:07来源:博客园 阅读 ()
对于一个能够保存键值插入顺序的字典,是如何实现的?
主要有两点:
一个双向链表,用来记录字典的键值的插入顺序
一个键和链表节点的映射,主要用来删除键的时候,找到键对应的节点
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
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:机器学习之模型评分
- python3基础之“术语表(2)” 2019-08-13
- python3 之 字符串编码小结(Unicode、utf-8、gbk、gb2312等 2019-08-13
- Python3安装impala 2019-08-13
- 小白如何入门 Python 爬虫? 2019-08-13
- python_字符串方法 2019-08-13
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash