摘要

本PEP提议将有序字典作为collections模块的新数据结构，在本PEP中称之为“OrderedDict”。提议的API整合了从各种实际应用程序和其他编程语言中存在的类似实现中获得的经验。

补丁

包含测试和文档的Py3.1工作补丁位于

OrderedDict补丁

签入的修订版本是：70101和70102

基本原理

在当前的Python版本中，广泛使用的内置dict类型不指定存储的键/值对的顺序。这使得在某些特定用例中很难将字典用作数据存储。

一些动态编程语言（如PHP和Ruby 1.9）保证了迭代时的特定顺序。在这些语言和现有的Python有序字典实现中，项目的顺序由键的插入时间定义。新键附加在末尾，但被覆盖的键不会移动到末尾。

以下示例显示了简单赋值的行为

>>> d = OrderedDict()
>>> d['parrot'] = 'dead'
>>> d['penguin'] = 'exploded'
>>> d.items()
[('parrot', 'dead'), ('penguin', 'exploded')]

保持顺序使OrderedDict在以下几种情况下非常有用

• XML/HTML处理库目前会丢失属性的顺序，使用列表而不是字典，这使得过滤变得繁琐，或者实现自己的有序字典。这会影响ElementTree、html5lib、Genshi和许多其他库。
• 在各种库和应用程序中存在许多有序字典实现，其中大多数都微妙地不兼容。此外，子类化dict是一项不平凡的任务，许多实现未能正确覆盖所有方法，这可能导致意外结果。

  此外，许多有序字典的实现效率低下，使得许多操作比它们应有的复杂。

• PEP 3115允许元类更改用于类主体的映射对象。有序字典可用于创建类似于C结构体的有序成员声明。例如，这对于未来的ctypes版本以及像Django框架中那样的将数据库表定义为类的ORM可能很有用。Django目前使用一种丑陋的技巧来恢复数据库模型中成员的顺序。
• RawConfigParser类接受一个dict_type参数，允许应用程序设置内部使用的字典类型。添加此功能的动机明确是为了允许用户提供有序字典。[1]
• 从其他编程语言（如PHP）移植的代码通常依赖于有序字典。在标准库中拥有一个保持顺序的字典实现可以简化过渡并提高不同库的兼容性。

有序字典API

有序字典API将主要与dict和现有有序字典兼容。注意：本PEP指的是collections.Mapping抽象基类中描述的2.7和3.0字典API。

构造函数和update()都接受元组的可迭代对象以及像dict一样的映射。与常规字典不同，插入顺序得到保留。

>>> d = OrderedDict([('a', 'b'), ('c', 'd')])
>>> d.update({'foo': 'bar'})
>>> d
collections.OrderedDict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])

如果有序字典从常规字典更新，则新键的顺序当然是未定义的。

所有迭代方法以及keys()、values()和items()都返回按键首次插入时间排序的值

>>> d['spam'] = 'eggs'
>>> d.keys()
['a', 'c', 'foo', 'spam']
>>> d.values()
['b', 'd', 'bar', 'eggs']
>>> d.items()
[('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', 'eggs')]

dict上没有的新方法

OrderedDict.__reversed__()

支持按键反向迭代。

问答

如果重新分配现有键会发生什么？

键不会移动，而是在原地分配新值。这与现有实现一致。

如果键在传递给构造函数的列表中多次出现会发生什么？

与常规字典相同——后面的项目覆盖前面的项目。这有一个副作用，即使用第一个键的位置，因为实际上只覆盖了值

>>> OrderedDict([('a', 1), ('b', 2), ('a', 3)])
collections.OrderedDict([('a', 3), ('b', 2)])

此行为与Python、PHP数组和Ruby 1.9中的hashmap中的现有实现一致。

有序字典是dict的子类吗？为什么？

是的。像defaultdict一样，有序字典是dict的子类。作为dict的子类使某些方法（如__getitem__和__len__）更快。更重要的是，作为dict的子类使得有序字典可以通过json等工具使用，这些工具通过测试isinstance(d, dict)来坚持使用dict输入。

子类化dict会产生任何限制吗？

是的。由于Py2.x和Py3.x中dict的API不同，OrderedDict API也必须不同。因此，Py2.7版本将需要覆盖iterkeys、itervalues和iteritems。

OrderedDict.popitem()是否返回特定的键/值对？

是的。它会弹出最近插入的新键及其对应的值。这对应于传统推/弹对所表现出的通常的LIFO行为。它在语义上等同于k=list(od)[-1]; v=od[k]; del od[k]; return (k,v)。实际实现效率更高，直接从已排序的键列表中弹出。

OrderedDict支持索引、切片等操作吗？

事实上，OrderedDict不实现Sequence接口。相反，它是一个记住键插入顺序的MutableMapping。唯一的类序列添加是对reversed的支持。

不允许索引的另一个优点是，它为使用链表的快速C实现留下了可能性。

OrderedDict支持其他排序顺序，例如字母顺序吗？

不。那些想要不同排序顺序的人确实需要使用另一种技术。OrderedDict完全是为了记录插入顺序。如果对任何其他顺序感兴趣，那么另一种结构（例如内存中的dbm）可能更合适。

OrderedDict与json模块、PyYAML和ConfigParser配合得如何？

对于json，好消息是json的编码器尊重OrderedDict的迭代顺序

>>> items = [('one', 1), ('two', 2), ('three',3), ('four',4), ('five',5)]
>>> json.dumps(OrderedDict(items))
'{"one": 1, "two": 2, "three": 3, "four": 4, "five": 5}'

在Py2.6中，json解码器的object_hook会传入一个已经构建好的字典，因此在object hook看到它之前，顺序就会丢失。这个问题正在Python 2.7/3.1中通过添加一个保留顺序的新hook来解决（参见https://github.com/python/cpython/issues/49631）。有了新的hook，顺序可以得到保留

>>> jtext = '{"one": 1, "two": 2, "three": 3, "four": 4, "five": 5}'
>>> json.loads(jtext, object_pairs_hook=OrderedDict)
OrderedDict({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5})

对于PyYAML，完全往返是无问题的

>>> ytext = yaml.dump(OrderedDict(items))
>>> print ytext
!!python/object/apply:collections.OrderedDict
- - [one, 1]
  - [two, 2]
  - [three, 3]
  - [four, 4]
  - [five, 5]

>>> yaml.load(ytext)
OrderedDict({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5})

对于ConfigParser模块，往返也是无问题的。在Py2.6中专门添加了自定义字典以支持有序字典

>>> config = ConfigParser(dict_type=OrderedDict)
>>> config.read('myconfig.ini')
>>> config.remove_option('Log', 'error')
>>> config.write(open('myconfig.ini', 'w'))

OrderedDict如何处理相等性测试？

比较两个有序字典意味着测试将是顺序敏感的，以便列表(od1.items())==list(od2.items())。

当有序字典与其他映射进行比较时，使用它们的顺序不敏感比较。这允许有序字典在任何使用常规字典的地方进行替换。

__repr__格式如何在repr/eval往返中保持顺序？

OrderedDict([(‘a’, 1), (‘b’, 2)])

可能的底层数据结构有什么取舍？

• 维护一个排序的键列表对于所有操作都很快，除了__delitem__()，它变成O(n)操作。这种数据结构代码非常简单，浪费空间很少。
• 维护一个单独的字典来记录插入序列号会使代码稍微复杂一些。所有基本操作都是O(1)，但__setitem__()和__delitem__()的常数因子会增加，这意味着每个用例都必须为此加速付费（因为所有构建都通过__setitem__()）。此外，第一次遍历会产生一次性的O(n log n)排序成本。存储成本是键排序列表方法的两倍。
• 用C编写的版本可以使用链表。代码将比其他两种方法更复杂，但它会节省空间并保持与常规字典相同的大O性能。它是最快且最节省空间的。

参考实现

包含测试和文档的实现位于

OrderedDict补丁

提议的版本有几个优点

• 严格遵守MutableMapping API，没有新方法，因此学习曲线接近于零。它只是一个记住插入顺序的字典。
• 总体性能良好。大O时间与常规字典相同，只是键删除是O(n)。

在各种Python项目或独立库中，启发了此处提议的API的其他有序字典实现有

• Python中的odict
• Babel中的odict
• Django中的OrderedDict
• odict模块
• ordereddict (odict模块的C实现)
• StableDict
• Armin Rigo的OrderedDict

未来方向

随着标准库中提供有序字典，其他库可能会利用这一点。例如，ElementTree将来可能会返回保留源文件属性顺序的odicts。

参考资料

版权

本文档已置于公共领域。