数据结构和算法-7-字典排序

问题描述

假如我们想创建一个字典，并且在迭代或序列化这个字典的时候能够控制元素的顺序。如何实现呢？

解决方案

为了能控制字典中元素的顺序，我们可以使用 collections 模块中的 OrderedDict 类。

在迭代操作的时候 OrderedDict 会保持元素被插入时的顺序。

代码示例：

from collections import OrderedDict

import json


def test_ordereddict():
    """使用OrderedDict保持字典中元素的顺序"""
    od = OrderedDict()
    # 向字典中插入元素
    od['one'] = 1
    od['two'] = 2
    od['three'] = 3
    od['four'] = 4

    # 获取字典的值时，顺序没变哦
    assert list(od.values()) == [1, 2, 3, 4]

    # 遍历时,顺序也是没变的哦
    for key in od:
        print(key, od[key])

    # 序列化时顺序也是保持不变的
    assert json.dumps(od) == {"one": 1, "two": 2, "three": 3, "four": 4}

从上面的例子可以看出，如果我们想精确控制使用 JSON 编码后「字段的顺序」，可以使用 OrderedDict 来构建这样的数据。

扩展讨论

OrderedDict 内部维护着一个根据键插入顺序排序的双向链表。

每次当一个新的元素插入进来的时候，它会被放到链表的尾部。对于一个已经存在的键的重复赋值不会改变键的顺序。

需要注意的是，

一个 OrderedDict 的大小是一个普通字典的两倍，因为它内部维护着另外一个链表。

所以如果你要构建一个需要大量 OrderedDict 实例的数据结构的时候（比如读取 100,000 行 CSV 数据到一个 OrderedDict 列表中去），那么你就得仔细权衡一下是否使用 OrderedDict 带来的好处要大过额外内存消耗的影响。