[Python-ideas] OrderedDict.peekitem()

Grant Jenks grant.jenks at gmail.com
Mon Jul 6 23:51:22 CEST 2015

On Mon, Jul 6, 2015 at 2:30 PM, Neil Girdhar <mistersheik at gmail.com> wrote:
> SortedDict (http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html)
> manages to support indexing.  Can OrderedDict do the same thing?

OrderedDict doesn't currently do the same thing. But you could use a
SortedDict to implement an OrderedDict and have that feature. The use case:

In [2]: o = OrderedDict([(1, 2), (2, 3), (3, 4)])

In [3]: o.index[0]
Out[3]: 1

In [4]: o.index[-1]
Out[4]: 3

A little benchmarking put it at half the speed of collections.OrderedDict.
Here's the recipe:

from itertools import count
from collections import MutableMapping
from sortedcontainers import SortedDict

class OrderedDictIndex(object):
    def __init__(self, nums):
        self._nums = nums

    def __len__(self):
        return len(self._nums)

    def __getitem__(self, index):
        num = self._nums.iloc[index]
        return self._nums[num]

class OrderedDict(MutableMapping):
    def __init__(self, *args, **kwargs):
        self._dict = {}
        self._keys = {}
        self._nums = SortedDict()
        self._count = count()

        self.index = OrderedDictIndex(self._nums)

        self.update(*args, **kwargs)

    def __getitem__(self, key):
        return self._dict[key]

    def __setitem__(self, key, value):
        if key not in self._dict:
            num = next(self._count)
            self._keys[key] = num
            self._nums[num] = key

        self._dict[key] = value

    def __delitem__(self, key):
        del self._dict[key]
        num = self._keys.pop(key)
        del self._nums[num]

    def __len__(self):
        return len(self._dict)

    def __iter__(self):
        return self._nums.itervalues()

More information about the Python-ideas mailing list