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

User · Answer

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  gt   index and k    key                  self move to end k

User · Answer

I would suggest adding a prepend   method to this pure Python ActiveState recipe or deriving a subclass from it  The code to do so could be a fairly efficient given that the underlying data structure for ordering is a linked-list  Update To prove this approach is feasible  below is code that does what s suggested  As a bonus  I also made a few additional minor changes to get to work in both Python 2 7 15 and 3 7 1  A prepend   method has been added to the class in the recipe and has been implemented in terms of another method that s been added named move to end    which was added to OrderedDict in Python 3 2  prepend   can also be implemented directly  almost exactly as shown at the beginning of  Ashwini Chaudhary s answer   and doing so would likely result in it being slightly faster  but that s been left as an exercise for the motivated reader      Ordered Dictionary for Py2 4 from https   code activestate com recipes 576693    Backport of OrderedDict   class that runs on Python 2 4  2 5  2 6  2 7 and pypy    Passes Python2 7 s test suite and incorporates all the latest updates   try      from thread import get ident as  get ident except ImportError     Python 3      from dummy thread import get ident as  get ident     from  thread import get ident as  get ident    Changed - martineau  try      from  abcoll import KeysView  ValuesView  ItemsView except ImportError      pass  class MyOrderedDict dict        Dictionary that remembers insertion order        An inherited dict maps keys to values        The inherited dict provides   getitem      len      contains    and get        The remaining methods are order-aware        Big-O running times for all methods are the same as for regular dictionaries         The internal self   map dictionary maps keys to links in a doubly linked list        The circular doubly linked list starts and ends with a sentinel element        The sentinel element never gets deleted  this simplifies the algorithm         Each link is stored as a list of length three    PREV  NEXT  KEY        def   init   self   args    kwds              Initialize an ordered dictionary   Signature is the same as for         regular dictionaries  but keyword arguments are not recommended         because their insertion order is arbitrary                       if len args   gt  1              raise TypeError  expected at most 1 arguments  got  d    len args           try              self   root         except AttributeError              self   root   root         sentinel node             root       root  root  None              self   map              self   update  args    kwds       def prepend self  key  value      Added to recipe          self update  key  value           self move to end key  last False            Derived from cpython 3 2 source code      def move to end self  key  last True      Added to recipe             Move an existing element to the end  or beginning if last  False            Raises KeyError if the element does not exist          When last True  acts like a fast version of self key  self pop key                       PREV  NEXT  KEY   0  1  2          link   self   map key          link prev   link PREV          link next   link NEXT          link prev NEXT    link next         link next PREV    link prev         root   self   root          if last              last   root PREV              link PREV    last             link NEXT    root             last NEXT    root PREV    link         else              first   root NEXT              link PREV    root             link NEXT    first             root NEXT    first PREV    link               def   setitem   self  key  value  dict setitem dict   setitem              od   setitem   i  y   lt    gt  od i  y            Setting a new item creates a new link which goes at the end of the linked           list  and the inherited dictionary is updated with the new key value pair          if key not in self              root   self   root             last   root 0              last 1    root 0    self   map key     last  root  key          dict setitem self  key  value       def   delitem   self  key  dict delitem dict   delitem              od   delitem   y   lt    gt  del od y             Deleting an existing item uses self   map to find the link which is           then removed by updating the links in the predecessor and successor nodes          dict delitem self  key          link prev  link next  key   self   map pop key          link prev 1    link next         link next 0    link prev      def   iter   self            od   iter      lt    gt  iter od           root   self   root         curr   root 1          while curr is not root              yield curr 2              curr   curr 1       def   reversed   self            od   reversed      lt    gt  reversed od           root   self   root         curr   root 0          while curr is not root              yield curr 2              curr   curr 0       def clear self            od clear   - gt  None   Remove all items from od           try              for node in self   map itervalues                    del node                root   self   root             root       root  root  None              self   map clear           except AttributeError              pass         dict clear self       def popitem self  last True              od popitem   - gt   k  v   return and remove a  key  value  pair          Pairs are returned in LIFO order if last is true or FIFO order if false                       if not self              raise KeyError  dictionary is empty           root   self   root         if last              link   root 0              link prev   link 0              link prev 1    root             root 0    link prev         else              link   root 1              link next   link 1              root 1    link next             link next 0    root         key   link 2          del self   map key          value   dict pop self  key          return key  value        -- the following methods do not depend on the internal structure --      def keys self            od keys   - gt  list of keys in od          return list self       def values self            od values   - gt  list of values in od          return  self key  for key in self       def items self            od items   - gt  list of  key  value  pairs in od          return   key  self key   for key in self       def iterkeys self            od iterkeys   - gt  an iterator over the keys in od          return iter self       def itervalues self            od itervalues - gt  an iterator over the values in od          for k in self              yield self k       def iteritems self            od iteritems - gt  an iterator over the  key  value  items in od          for k in self              yield  k  self k        def update  args    kwds              od update E    F  - gt  None   Update od from dict iterable E and F           If E is a dict instance  does            for k in E  od k    E k          If E has a  keys   method  does          for k in E keys    od k    E k          Or if E is an iterable of items  does    for k  v in E  od k    v         In either case  this is followed by      for k  v in F items    od k    v                      if len args   gt  2              raise TypeError  update   takes at most 2 positional                                arguments   d given      len args             elif not args              raise TypeError  update   takes at least 1 argument  0 given            self   args 0            Make progressively weaker assumptions about  quot other quot          other              if len args     2              other   args 1          if isinstance other  dict               for key in other                  self key    other key          elif hasattr other   keys                for key in other keys                    self key    other key          else              for key  value in other                  self key    value         for key  value in kwds items                self key    value        update   update    let subclasses override update without breaking   init          marker   object        def pop self  key  default   marker              od pop k  d   - gt  v  remove specified key and return the corresponding value          If key is not found  d is returned if given  otherwise KeyError is raised                       if key in self              result   self key              del self key              return result         if default is self   marker              raise KeyError key          return default      def setdefault self  key  default None            od setdefault k  d   - gt  od get k d   also set od k  d if k not in od          if key in self              return self key          self key    default         return default      def   repr   self   repr running               od   repr      lt    gt  repr od           call key   id self    get ident           if call key in  repr running              return                repr running call key    1         try              if not self                  return   s       self   class     name                 return   s  r      self   class     name    self items            finally              del  repr running call key       def   reduce   self            Return state information for pickling          items     k  self k   for k in self          inst dict   vars self  copy           for k in vars MyOrderedDict                 inst dict pop k  None          if inst dict              return  self   class     items    inst dict          return self   class     items        def copy self            od copy   - gt  a shallow copy of od          return self   class   self        classmethod     def fromkeys cls  iterable  value None              OD fromkeys S   v   - gt  New ordered dictionary with keys from S         and values equal to v  which defaults to None                        d   cls           for key in iterable              d key    value         return d      def   eq   self  other              od   eq   y   lt    gt  od  y   Comparison to another OD is order-sensitive         while comparison to a regular mapping is order-insensitive                       if isinstance other  MyOrderedDict               return len self   len other  and self items      other items           return dict   eq   self  other       def   ne   self  other           return not self    other        -- the following methods are only used in Python 2 7 --      def viewkeys self            quot od viewkeys   - gt  a set-like object providing a view on od s keys quot          return KeysView self       def viewvalues self            quot od viewvalues   - gt  an object providing a view on od s values quot          return ValuesView self       def viewitems self            quot od viewitems   - gt  a set-like object providing a view on od s items quot          return ItemsView self   if   name         main          d1   MyOrderedDict    a    1      b    2         d1 update   c   3        print d1     - gt  MyOrderedDict    a    1      b    2      c    3          d2   MyOrderedDict    a    1      b    2         d2 prepend  c   100      print d2     - gt  MyOrderedDict    c   100     a    1      b    2

User · Answer

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

User · Answer

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    gt  gt  gt  d   MyOrderedDict    a    1      b    2      gt  gt  gt  d MyOrderedDict    a    1      b    2      gt  gt  gt  d prepend  c   100   gt  gt  gt  d MyOrderedDict    c   100     a    1      b    2      gt  gt  gt  d prepend  a   d  a     gt  gt  gt  d MyOrderedDict    a    1      c   100     b    2      gt  gt  gt  d prepend  d   200   gt  gt  gt  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    gt  gt  gt  d   OrderedDict    a    1      b    2      gt  gt  gt  ordered dict prepend d   c   100   gt  gt  gt  d OrderedDict    c   100     a    1      b    2      gt  gt  gt  ordered dict prepend d   a   d  a     gt  gt  gt  d OrderedDict    a    1      c   100     b    2      gt  gt  gt  ordered dict prepend d   d   500   gt  gt  gt  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    gt  gt  gt  d1   OrderedDict    a    1      b    2      gt  gt  gt  d1 update   c   3     gt  gt  gt  d1 move to end  c   last False   gt  gt  gt  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   -- gt  A B C D       unique everseen  ABBCcAD   str lower  -- gt  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

User · Answer

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

User · Answer

I got an infinity loop while trying to print or save the dictionary using  Ashwini Chaudhary answer with Python 2 7  But I managed to reduce his code a little  and got it working here   def move to dict beginning dictionary  key                   Move a OrderedDict item to its beginning  or add it to its beginning          Compatible with Python 2 7              if sys version info 0   lt  3          value   dictionary key          del dictionary key          root   dictionary  OrderedDict  root          first   root 1          root 1    first 0    dictionary  OrderedDict  map key     root  first  key          dict   setitem   dictionary  key  value       else          dictionary move to end  key  last False

User · Answer

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

User · Answer

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    gt  gt  gt  d1   ListDict    a    1      b    2      gt  gt  gt  d1 insert before  a     c   3    gt  gt  gt  d1 ListDict    c   3     a    1      b    2

User · Answer

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   gt  gt  gt  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

User · Answer

This is now possible with move to end key  last True    gt  gt  gt  d   OrderedDict fromkeys  abcde    gt  gt  gt  d move to end  b    gt  gt  gt     join d keys     acdeb   gt  gt  gt  d move to end  b   last False   gt  gt  gt     join d keys     bacde    https   docs python org 3 library collections html collections OrderedDict move to end

User · Answer

This is a default  ordered dict which allows to insert items in any position and use the   operator to create keys   from collections import OrderedDict  class defdict OrderedDict         protected      OrderedDict  root     OrderedDict  map     cb            cb   None      def   init   self  cb None           super defdict  self    init             self  cb   cb      def   setattr   self  name  value             if the attr is not in self  protected set a key         if name in self  protected              OrderedDict   setattr   self  name  value          else              OrderedDict   setitem   self  name  value       def   getattr   self  name           if name in self  protected              return OrderedDict   getattr   self  name          else                implements missing keys               if there is a callable  cb  create a key with its value             try                  return OrderedDict   getitem   self  name              except KeyError as e                  if callable self  cb                       value   self name    self  cb                       return value                 raise e      def insert self  index  name  value           items     k  v  for k  v in self items            items insert index   name  value           self clear           for k  v in items              self k    v   asd   defdict lambda  10  asd k1    Hey  asd k3    Bye  asd k4    Hello  asd insert 1   k2    New item   print asd k5   access a missing key will create one when there is a callback   10 asd k6    5    adding to a missing key print asd k6   15 print asd keys       k1    k2    k3    k4    k5    k6   print asd values       Hey    New item    Bye    Hello   10  15

[python] How to add an element to the beginning of an OrderedDict?

Examples related to python

Examples related to python-3.x

Examples related to dictionary

Examples related to python-2.x

Examples related to ordereddict