How can I add an element at the top of an OrderedDict in python? -

i have this

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

if this

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

then this

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

but want this

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

without creating new dictionary

there's no built-in method doing in python 2. if need this, need write prepend() method/function operates on ordereddict internals o(1) complexity.

for python 3.2 , later, can use move_to_end¹ method. method accepts last argument indicates whether element moved bottom (last=true) or top (last=false) of ordereddict.

finally, if want quick, dirty , slow solution, can create new ordereddict scratch.

details 4 different solutions:

---

extend ordereddict , add 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 manipulates ordereddict objects

this function same thing accepting dict object, key , value. prefer 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 ordereddict.move_to_end() method. using it, can move existing key either end of 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 need insert element , move top, in 1 step, can directly use create prepend() wrapper (not presented here).

---

create new ordereddict - slow!!!

if don't want , performance not issue easiest way create new dict:

from itertools import chain, ifilterfalse collections import ordereddict   def unique_everseen(iterable, key=none):     "list unique elements, preserving order. remember elements ever seen."     # unique_everseen('aaaabbbccdaabbb') --> b c d     # unique_everseen('abbccad', str.lower) --> b c d     seen = set()     seen_add = seen.add     if key none:         element in ifilterfalse(seen.__contains__, iterable):             seen_add(element)             yield element     else:         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 added @ front new_dic = ordereddict((k, d2.get(k, d1.get(k))) k in \                                            unique_everseen(chain(d2, d1))) print new_dic 

output:

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

---