How to add an element to the beginning of an OrderedDict?

Posted on

Question :

How to add an element to the beginning of an OrderedDict?

I have this:

d1 = OrderedDict([('a', '1'), ('b', '2')])

If I do this:

d1.update({'c':'3'})

Then I get this:

OrderedDict([('a', '1'), ('b', '2'), ('c', '3')])

but I want this:

[('c', '3'), ('a', '1'), ('b', '2')]

without creating new dictionary.

Answer #1:

There’s no built-in method for doing this in Python 2. If you need this, you need to write a prepend() method/function that operates on the OrderedDict internals with O(1) complexity.

For Python 3.2 and later, you should use the move_to_end method. The method accepts a last argument which indicates whether the element will be moved to the bottom (last=True) or the top (last=False) of the OrderedDict.

Finally, if you want a quick, dirty and slow solution, you can just create a new OrderedDict from scratch.

Details for the four different solutions:


Extend OrderedDict and add a new instance method

from collections import OrderedDict

class MyOrderedDict(OrderedDict):

    def prepend(self, key, value, dict_setitem=dict.__setitem__):

        root = self._OrderedDict__root
        first = root[1]

        if key in self:
            link = self._OrderedDict__map[key]
            link_prev, link_next, _ = link
            link_prev[1] = link_next
            link_next[0] = link_prev
            link[0] = root
            link[1] = first
            root[1] = first[0] = link
        else:
            root[1] = first[0] = self._OrderedDict__map[key] = [root, first, key]
            dict_setitem(self, key, value)

Demo:

>>> d = MyOrderedDict([('a', '1'), ('b', '2')])
>>> d
MyOrderedDict([('a', '1'), ('b', '2')])
>>> d.prepend('c', 100)
>>> d
MyOrderedDict([('c', 100), ('a', '1'), ('b', '2')])
>>> d.prepend('a', d['a'])
>>> d
MyOrderedDict([('a', '1'), ('c', 100), ('b', '2')])
>>> d.prepend('d', 200)
>>> d
MyOrderedDict([('d', 200), ('a', '1'), ('c', 100), ('b', '2')])

Standalone function that manipulates OrderedDict objects

This function does the same thing by accepting the dict object, key and value. I personally prefer the class:

from collections import OrderedDict

def ordered_dict_prepend(dct, key, value, dict_setitem=dict.__setitem__):
    root = dct._OrderedDict__root
    first = root[1]

    if key in dct:
        link = dct._OrderedDict__map[key]
        link_prev, link_next, _ = link
        link_prev[1] = link_next
        link_next[0] = link_prev
        link[0] = root
        link[1] = first
        root[1] = first[0] = link
    else:
        root[1] = first[0] = dct._OrderedDict__map[key] = [root, first, key]
        dict_setitem(dct, key, value)

Demo:

>>> d = OrderedDict([('a', '1'), ('b', '2')])
>>> ordered_dict_prepend(d, 'c', 100)
>>> d
OrderedDict([('c', 100), ('a', '1'), ('b', '2')])
>>> ordered_dict_prepend(d, 'a', d['a'])
>>> d
OrderedDict([('a', '1'), ('c', 100), ('b', '2')])
>>> ordered_dict_prepend(d, 'd', 500)
>>> d
OrderedDict([('d', 500), ('a', '1'), ('c', 100), ('b', '2')])

Use OrderedDict.move_to_end() (Python >= 3.2)

Python 3.2 introduced the OrderedDict.move_to_end() method. Using it, we can move an existing key to either end of the dictionary in O(1) time.

>>> d1 = OrderedDict([('a', '1'), ('b', '2')])
>>> d1.update({'c':'3'})
>>> d1.move_to_end('c', last=False)
>>> d1
OrderedDict([('c', '3'), ('a', '1'), ('b', '2')])

If we need to insert an element and move it to the top, all in one step, we can directly use it to create a prepend() wrapper (not presented here).


Create a new OrderedDict – slow!!!

If you don’t want to do that and performance is not an issue then easiest way is to create a new dict:

from itertools import chain, ifilterfalse
from collections import OrderedDict


def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in ifilterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

d1 = OrderedDict([('a', '1'), ('b', '2'),('c', 4)])
d2 = OrderedDict([('c', 3), ('e', 5)])   #dict containing items to be added at the front
new_dic = OrderedDict((k, d2.get(k, d1.get(k))) for k in 
                                           unique_everseen(chain(d2, d1)))
print new_dic

output:

OrderedDict([('c', 3), ('e', 5), ('a', '1'), ('b', '2')])

Answered By: Ashwini Chaudhary

Answer #2:

EDIT (2019-02-03)
Note that the following answer only works on older versions of Python. More recently, OrderedDict has been rewritten in C. In addition this does touch double-underscore attributes which is frowned upon.

I just wrote a subclass of OrderedDict in a project of mine for a similar purpose. Here’s the gist.

Insertion operations are also constant time O(1) (they don’t require you to rebuild the data structure), unlike most of these solutions.

>>> d1 = ListDict([('a', '1'), ('b', '2')])
>>> d1.insert_before('a', ('c', 3))
>>> d1
ListDict([('c', 3), ('a', '1'), ('b', '2')])
Answered By: Jared

Answer #3:

You have to make a new instance of OrderedDict. If your keys are unique:

d1=OrderedDict([("a",1),("b",2)])
d2=OrderedDict([("c",3),("d",99)])
both=OrderedDict(list(d2.items()) + list(d1.items()))
print(both)

#OrderedDict([('c', 3), ('d', 99), ('a', 1), ('b', 2)])

But if not, beware as this behavior may or may not be desired for you:

d1=OrderedDict([("a",1),("b",2)])
d2=OrderedDict([("c",3),("b",99)])
both=OrderedDict(list(d2.items()) + list(d1.items()))
print(both)

#OrderedDict([('c', 3), ('b', 2), ('a', 1)])
Answered By: dolphin

Answer #4:

If you know you will want a ‘c’ key, but do not know the value, insert ‘c’ with a dummy value when you create the dict.

d1 = OrderedDict([('c', None), ('a', '1'), ('b', '2')])

and change the value later.

d1['c'] = 3
Answered By: Terry Jan Reedy

Answer #5:

This is now possible with move_to_end(key, last=True)

>>> d = OrderedDict.fromkeys('abcde')
>>> d.move_to_end('b')
>>> ''.join(d.keys())
'acdeb'
>>> d.move_to_end('b', last=False)
>>> ''.join(d.keys())
'bacde'

https://docs.python.org/3/library/collections.html#collections.OrderedDict.move_to_end

Answered By: simP

Answer #6:

FWIW Here is a quick-n-dirty code I wrote for inserting to an arbitrary index position. Not necessarily efficient but it works in-place.

class OrderedDictInsert(OrderedDict):
    def insert(self, index, key, value):
        self[key] = value
        for ii, k in enumerate(list(self.keys())):
            if ii >= index and k != key:
                self.move_to_end(k)
Answered By: Tom Aldcroft

Answer #7:

You may want to use a different structure altogether, but there are ways to do it in python 2.7.

d1 = OrderedDict([('a', '1'), ('b', '2')])
d2 = OrderedDict(c='3')
d2.update(d1)

d2 will then contain

>>> d2
OrderedDict([('c', '3'), ('a', '1'), ('b', '2')])

As mentioned by others, in python 3.2 you can use OrderedDict.move_to_end('c', last=False) to move a given key after insertion.

Note: Take into consideration that the first option is slower for large datasets due to creation of a new OrderedDict and copying of old values.

Answered By: wihlke

Answer #8:

If you need functionality that isn’t there, just extend the class with whatever you want:

from collections import OrderedDict

class OrderedDictWithPrepend(OrderedDict):
    def prepend(self, other):
        ins = []
        if hasattr(other, 'viewitems'):
            other = other.viewitems()
        for key, val in other:
            if key in self:
                self[key] = val
            else:
                ins.append((key, val))
        if ins:
            items = self.items()
            self.clear()
            self.update(ins)
            self.update(items)

Not terribly efficient, but works:

o = OrderedDictWithPrepend()

o['a'] = 1
o['b'] = 2
print o
# OrderedDictWithPrepend([('a', 1), ('b', 2)])

o.prepend({'c': 3})
print o
# OrderedDictWithPrepend([('c', 3), ('a', 1), ('b', 2)])

o.prepend([('a',11),('d',55),('e',66)])
print o
# OrderedDictWithPrepend([('d', 55), ('e', 66), ('c', 3), ('a', 11), ('b', 2)])
Answered By: georg

Leave a Reply

Your email address will not be published.