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)