摘要

本 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 版本以及将数据库表定义为类的 ORM（如 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 中的哈希映射中的现有实现一致。

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

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

从 dict 子类化会产生什么限制？

是的。由于 dict 的 API 在 Py2.x 和 Py3.x 中不同，因此 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（参见 https://github.com/python/cpython/issues/49631）。使用新钩子，可以保留顺序

>>> 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(n) 性能。它是最快、最节省空间的。

参考实现

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

OrderedDict 补丁

提议的版本有几个优点

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

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

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

未来方向

随着标准库中提供了有序字典，其他库可以利用它。例如，ElementTree 可以在将来返回保留源文件属性顺序的 odict。

参考文献

版权

本文档已置于公共领域。