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

Question

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')]) 

---