How to Implement an Ordered, Default Dict

How to implement an ordered, default dict?

The following (using a modified version of this recipe) works for me:

from collections import OrderedDict, Callable

class DefaultOrderedDict(OrderedDict):
    # Source: http://stackoverflow.com/a/6190500/562769
    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))

Adding default values to a list of ordered dict

It seems like there's no escaping looking through all the dicts first because you need to know which keys to include. You can do that a little more simply by passing the keys into an OrderedDict() in the order seen:

default = OrderedDict((k, val) for d in l for k in d.keys())

With that you can blend the dictionaries in the list:

def add_defaults(l, val):
    default = OrderedDict((k, val) for d in l for k in d.keys())
    return [OrderedDict({**default, **d}) for d in l]

first = OrderedDict([('k1', 'v1'), ('k2', 'v2'), ('k3', 'v3')])
second = OrderedDict([('k1', 'v1'), ('k2', 'v2'), ('k4', 'v4')])
third = OrderedDict([('k2', 'v2'), ('k5', 'v5'), ('k6', 'v6')])

lst=[first, second, third]

print(add_defaults(lst, ''))

Prints:

[
 OrderedDict([('k1', 'v1'), ('k2', 'v2'), ('k3', 'v3'), ('k4', ''), ('k5', ''), ('k6', '')]), 
 OrderedDict([('k1', 'v1'), ('k2', 'v2'), ('k3', ''), ('k4', 'v4'), ('k5', ''), ('k6', '')]), 
 OrderedDict([('k1', ''), ('k2', 'v2'), ('k3', ''), ('k4', ''), ('k5', 'v5'), ('k6', 'v6')])
]

How are Counter / defaultdict ordered in Python 3.7?

Counter and defaultdict are both ordered now, and you can rely on it. Counter just doesn't look ordered because its repr was designed before dict ordering was guaranteed, and Counter.__repr__ sorts entries by descending order of value.

def __repr__(self):
    if not self:
        return '%s()' % self.__class__.__name__
    try:
        items = ', '.join(map('%r: %r'.__mod__, self.most_common()))
        return '%s({%s})' % (self.__class__.__name__, items)
    except TypeError:
        # handle case where values are not orderable
        return '{0}({1!r})'.format(self.__class__.__name__, dict(self))

How does collections.defaultdict work?

Usually, a Python dictionary throws a KeyError if you try to get an item with a key that is not currently in the dictionary. The defaultdict in contrast will simply create any items that you try to access (provided of course they do not exist yet). To create such a "default" item, it calls the function object that you pass to the constructor (more precisely, it's an arbitrary "callable" object, which includes function and type objects). For the first example, default items are created using int(), which will return the integer object 0. For the second example, default items are created using list(), which returns a new empty list object.

How can i use default ordered dict in python

To have default values in your dict, you have to set default_factory, which must be a callable.

Example usage:

d = DefaultOrderedDict(lambda: None)
assert d['item'] is None

# as with normal dict, you can init it with another dict
d = {'key': 'value'}
d = DefaultOrderedDict(list, d)
assert d['item'] == []
assert d['key'] == 'value'

DefaultDict ,on append elements, maintain keys sorted in the order of addition

You can use collections.OrderedDict to maintain the order of the insertion of keys.

>>> from collections import OrderedDict
>>> d = OrderedDict()
>>> for i in range(4):
...     d.setdefault(input(), []).append(i)
... 
bcdef
abcdefg
bcde
bcdef
>>> print("\n".join(d))
bcdef
abcdefg
bcde

Here, we use setdefault method, which will set the default value (the second argument) for the key, if it is not found in the dictionary already. And the setdefault returns the value corresponding to the key, so in this case, if the key is not there, then a new list is assigned against the key and it will be returned. If the key already exists, then the existing list corresponding to that will be returned. And we simply call append on the list returned.

subclassing from OrderedDict and defaultdict

Inheriting from OrderedDict as in the answer you linked to is the simplest way. It is more work to implement an ordered store than it is to get default values from a factory function.

All you need to implement for defaultdict is a bit of custom __init__ logic and the extremely simple __missing__.

If you instead inherit from defaultdict, you have to delegate to or re-implement at least __setitem__, __delitem__ and __iter__ to reproduce the in-order operation. You still have to do setup work in __init__, though you might be able to inherit or simply leave out some of the other methods depending on your needs.

Take a look at the original recipe or any of the others linked to from another Stack Overflow question for what that would entail.

---

Related Topics