如何实现一个有序的默认字典？

Question

我想要将collections中的OrderedDict()和defaultdict()结合到一个对象中，使其成为一个有序且带默认值的dict。
这是否可能？

- jlconlin

---

尽管您已经接受了一个解决方案，但您可能想要查看我为此答案编写的相对简单的"OrderedDefaultdict"类。 - martineau

我想知道为什么不能创建一个继承OrderedDict和defaultdict的类？ - drs

@drs 请看下面的答案，它恰好能够实现您需要的功能：https://dev59.com/SG025IYBdhLWcg3wJCVD#35968897 - avyfain

我了解从Python 3.7开始，任何继承自常规“dict”的内容都会保持插入顺序 - 包括“defaultdict”。 - Peter Kilczuk

Answer 1

以下代码（使用修改版这个示例）适用于我：

```python # 代码示例 ```

```python # 示例输出 ```

from collections import OrderedDict, Callable

class DefaultOrderedDict(OrderedDict):
    # Source: https://dev59.com/SG025IYBdhLWcg3wJCVD#6190500
    def __init__(self, default_factory=None, *a, **kw):
        if (default_factory is not None and
           not isinstance(default_factory, Callable)):
            raise TypeError('first argument must be callable')
        OrderedDict.__init__(self, *a, **kw)
        self.default_factory = default_factory

    def __getitem__(self, key):
        try:
            return OrderedDict.__getitem__(self, key)
        except KeyError:
            return self.__missing__(key)

    def __missing__(self, key):
        if self.default_factory is None:
            raise KeyError(key)
        self[key] = value = self.default_factory()
        return value

    def __reduce__(self):
        if self.default_factory is None:
            args = tuple()
        else:
            args = self.default_factory,
        return type(self), args, None, None, self.items()

    def copy(self):
        return self.__copy__()

    def __copy__(self):
        return type(self)(self.default_factory, self)

    def __deepcopy__(self, memo):
        import copy
        return type(self)(self.default_factory,
                          copy.deepcopy(self.items()))

    def __repr__(self):
        return 'OrderedDefaultDict(%s, %s)' % (self.default_factory,
                                               OrderedDict.__repr__(self))

- Zach Kelling

---

已删除我的答案，虽然思路相似，但是是即兴设计的（因此需要实现其他不同的功能）。 - dr jimbob

@Neil G：您可以直接使用内置的 callable() 函数来测试 default_factory。使用 isinstance(default_factory, Callable) 实际上需要它具有不仅是可调用性的更多特征--参见文档--而这里只需要检查其是否可调用即可。 - martineau

@Neil G：实际上，callable()在Python 3.0中首先被删除，然后在Python 3.2中重新引入。无论如何，如果您愿意，可以考虑自己进行更改（我更喜欢自己的答案;-)）。通常情况下，我倾向于避免直接跳进并更改别人的答案，而是像我在这里所做的那样只发表评论。 - martineau

我认为你可能需要在__reduce__函数中将 self.items() 改为 iter(self.items())，否则会引发PicklingError异常，该异常会抱怨__reduce__的第五个参数必须是一个迭代器。 - max

当我使用copy.deepcopy()复制此对象的实例时，会出现最大递归深度异常。在DefaultOrderedDict.__deepcopy__中，我的快速修复方法是将参数copy.deepcopy(self.items())更改为copy.deepcopy(tuple(self.items())。 - chfoo

Answer 2

以下是另一个可能性，灵感来自Raymond Hettinger的super()函数，在Python 2.7.X和3.4.X上测试通过：

from collections import OrderedDict, defaultdict

class OrderedDefaultDict(OrderedDict, defaultdict):
    def __init__(self, default_factory=None, *args, **kwargs):
        #in python3 you can omit the args to super
        super(OrderedDefaultDict, self).__init__(*args, **kwargs)
        self.default_factory = default_factory

如果您查看类的MRO（也称为help(OrderedDefaultDict)），您将看到以下内容：

class OrderedDefaultDict(collections.OrderedDict, collections.defaultdict)
 |  Method resolution order:
 |      OrderedDefaultDict
 |      collections.OrderedDict
 |      collections.defaultdict
 |      __builtin__.dict
 |      __builtin__.object

这意味着当OrderedDefaultDict的一个实例被初始化时，它会延迟到OrderedDict的初始化，但是这个类将在调用__builtin__.dict之前调用defaultdict的方法，这正是我们想要的。

- avyfain

---

尽管此答案非常简洁优雅，但在Python3中无法运行。由于有序字典（OrderedDict）和默认字典（defaultdict）均是用C实现的，因此会出现TypeError错误："multiple bases have instance lay-out conflict." 这是因为这些C类对内部数据结构的布局具有不同且不兼容的想法。上面接受的答案在Python3中可以很好地工作，只需要进行一些微小的更改（super().getitem(...代替OrderedDict._getitem(...)）。我正在使用Python3.5。 - ivanlan

有趣的是，这在Python 3.4.3中可以正常运行。有没有办法查看C代码中TypeError出现的位置？ - avyfain

从Python 3.6开始，这将是不必要的，因为所有的字典（dicts）和默认字典（defaultdicts）都是有序的。我可以接受它在3.5上无法使用 ;) - avyfain

尽管CPython 3.6中的字典（dicts）保留顺序，但这是一项不应被依赖的实现细节，详情请参见https://dev59.com/6VkS5IYBdhLWcg3wXFg9#39980548。如果您需要有序的字典，请使用`OrderedDict`。 - amjoconn

现在官方已经获得Guido批准了。 - Fruch

Answer 3

如果你想要一个简单的解决方案而不需要类，你可以使用 OrderedDict.setdefault(key, default=None) 或者 OrderedDict.get(key, default=None) 。如果你只从几个地方获取 / 设置（比如在循环中），你可以轻松地使用 setdefault。

totals = collections.OrderedDict()

for i, x in some_generator():
    totals[i] = totals.get(i, 0) + x

使用setdefault处理列表甚至更容易:

agglomerate = collections.OrderedDict()

for i, x in some_generator():
    agglomerate.setdefault(i, []).append(x)

但是如果您使用它多于几次，最好设置一个类，就像其他答案中所述。

- Artyer

---

这真是最清晰的答案！ - ruohola

Answer 4

如果您的用例很简单，而且不想在代码中添加DefaultOrderedDict类的实现，那么可以考虑另一种解决方案。

from collections import OrderedDict

keys = ['a', 'b', 'c']
items = [(key, None) for key in keys]
od = OrderedDict(items)

(None是我期望的默认值。)

请注意，如果您的要求之一是动态插入带有默认值的新键，则此解决方案将无法工作。这是简单性的一种权衡。

更新3/13/17 - 我了解到这种用例的一个便利函数。与上述相同，但您可以省略items = ...行，并只需：

od = OrderedDict.fromkeys(keys)

输出：

OrderedDict([('a', None), ('b', None), ('c', None)])

如果你的键是单个字符，你只需要传递一个字符串：

OrderedDict.fromkeys('abc')

这个输出与上面两个例子的输出相同。

你也可以将默认值作为第二个参数传递给OrderedDict.fromkeys(...)。

- Taylor D. Edmiston

---

感谢！ od = OrderedDict((k, None) for k in iterable) - n8henrie

这假设你的键在某个可迭代对象中预定义，因此下游对象需要知道添加新键需要一个初始值。更准确地说，对于像这样的东西，你不能假设有一个初始值：`>>> od = OrderedDefaultDict(int) >>> od['foo'] += 100 OrderedDefaultDict([('foo', 100)])`这种情况可以通过这个解决方案来正确处理。 - avyfain

@avyfain 没错。对于我的用例来说，这只是初始数据，因此未定义的键的未来插入并不相关。我会添加一条注释，使这个假设明确化。 - Taylor D. Edmiston

Answer 5

另一个简单的方法是使用字典 get 方法。

>>> from collections import OrderedDict
>>> d = OrderedDict()
>>> d['key'] = d.get('key', 0) + 1
>>> d['key'] = d.get('key', 0) + 1
>>> d
OrderedDict([('key', 2)])
>>> 

- snebel29

Answer 6

一个简单而优雅的解决方案，基于@NickBread的构建。虽然设置工厂的API略有不同，但拥有良好的默认值总是很好的。

class OrderedDefaultDict(OrderedDict):
    factory = list

    def __missing__(self, key):
        self[key] = value = self.factory()
        return value

- F Pereira

Answer 7

@zeekay的回答可以简化为以下内容：

from collections import OrderedDict

class OrderedDefaultListDict(OrderedDict): #name according to default
    def __missing__(self, key):
        self[key] = value = [] #change to whatever default you want
        return value

- Neck Beard

---

你甚至可以重写 __init__ 方法来捕获新项的 "default_factory"。 - pepoluan

Answer 8

defaultdict 在 Python 3.7+（以及 CPython 3.6+）中按插入顺序排序。

- user3064538

Answer 9

我创建了一个稍微改进和更简化的已接受答案的版本，适用于Python 3.7。

from collections import OrderedDict
from copy import copy, deepcopy
import pickle
from typing import Any, Callable


class DefaultOrderedDict(OrderedDict):
    def __init__(
            self,
            default_factory: Callable[[], Any],
            *args,
            **kwargs,
    ):
        super().__init__(*args, **kwargs)
        self.default_factory = default_factory

    def __getitem__(self, key):
        try:
            return super().__getitem__(key)
        except KeyError:
            return self.__missing__(key)

    def __missing__(self, key):
        self[key] = value = self.default_factory()
        return value

    def __reduce__(self):
        return type(self), (self.default_factory, ), None, None, iter(self.items())

    def copy(self):
        return self.__copy__()

    def __copy__(self):
        return type(self)(self.default_factory, self)

    def __deepcopy__(self, memo):
        return type(self)(self.default_factory, deepcopy(tuple(self.items()), memo))

    def __repr__(self):
        return f'{self.__class__.__name__}({self.default_factory}, {OrderedDict(self).__repr__()})'

而且，更重要的是，提供了一些测试。

a = DefaultOrderedDict(list)

# testing default
assert a['key'] == []
a['key'].append(1)
assert a['key'] == [1, ]

# testing repr
assert repr(a) == "DefaultOrderedDict(<class 'list'>, OrderedDict([('key', [1])]))"

# testing copy
b = a.copy()
assert b['key'] is a['key']
c = copy(a)
assert c['key'] is a['key']
d = deepcopy(a)
assert d['key'] is not a['key']
assert d['key'] == a['key']

# testing pickle
saved = pickle.dumps(a)
restored = pickle.loads(saved)
assert restored is not a
assert restored == a

# testing order
a['second_key'] = [2, ]
a['key'] = [3, ]
assert list(a.items()) == [('key', [3, ]), ('second_key', [2, ])]

- Nikolay Prokopyev

Answer 10

受到本帖其他答案的启发，您可以使用类似以下的代码：

from collections import OrderedDict

class OrderedDefaultDict(OrderedDict):
    def __missing__(self, key):
        value = OrderedDefaultDict()
        self[key] = value
        return value

我想知道在missing方法中初始化另一个相同类的对象是否有任何缺点。

- Samarth

---

这是一个有序字典，其中默认值始终为另一个有序字典。这并不是问题所在。 - Ivan Ivanov