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

Question

I have it:

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 a new dictionary.

Answer 1

There is no built-in method for this in Python 2. If you need it, you need to write a prepend() method / function that works with internal OrderedDict with O (1) complexity.

For Python 3.2 and later move_to_end you should use the move_to_end method. The method takes a last argument, which indicates whether the item will be moved down ( last=True ) or up ( last=False ) OrderedDict .

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

Details for 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 version:

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

---

A standalone function that manipulates OrderedDict objects

This function does the same, accepting a 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 version:

 >>> 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 introduces the OrderedDict.move_to_end() method. Using it, we can move the existing key to either end of the dictionary O (1) times.

 >>> 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 up, all in one step, we can directly use it to create prepend() shell (not shown here).

---

Create a new OrderedDict - slowly !!!

If you do not want to do this, and performance is not a problem, then the 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') --> ABCD # unique_everseen('ABBCcAD', str.lower) --> ABCD 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 

exit:

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

---

Answer 2

EDIT (2019-02-03) Note that the following answer only works on older versions of Python. More recently, OrderedDict been rewritten in C. Also, this applies to double underlined attributes that are deprecated.

I just wrote a subclass of OrderedDict in an OrderedDict project for a similar purpose. Here is the point .

Insert operations are also performed with a constant time of O(1) (they do not require restructuring 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')]) 

Answer 3

You need to create 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, be careful, as you may or may not need this behavior:

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

Answer 4

If you know that you need the c key, but don’t know the value, insert a c with a dummy value when creating the dict.

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

and change the value later.

 d1['c'] = 3 

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

Answer 6

If you need functionality that isn't there, just extend the class with what 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 very effective, but it 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)]) 

Answer 7

FWIW Here is the quick-dirty code that I wrote to insert into an arbitrary index position. Not necessarily effective, but works locally.

 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) 

Answer 8

You might want to use a completely different structure, but there are ways to do this in Python 2.7 .

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

d2 will contain

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

As already mentioned, in Python 3.2 you can use OrderedDict.move_to_end('c', last=False) to move this key after insertion.

Note. Note that the first option is slower for large datasets due to creating a new OrderedDict and copying old values.

Answer 9

This is what you need differently.

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

Answer 10

I would suggest adding the prepend() method to this pure Python ActiveState recipe or extracting a subclass from it. The code for this can be quite efficient, given that the underlying data structure for ordering is a linked list.

Refresh

To prove that such an approach is feasible, below is the code that does what was suggested. As a bonus, I also made a few additional minor changes to get started with Python 2.7.15 and 3.7.1.

The prepend() method was added to the class in the recipe and implemented in terms of another added method called move_to_end() , which was added to OrderedDict in Python 3.2.

prepend() can also be implemented directly, in much the same way as shown at the beginning of @Ashwini Chaudhary's answer - and this will probably lead to it being a little faster, but it will be 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 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) > 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) <==> 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) <==> 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__() <==> iter(od)' root = self.__root curr = root[1] while curr is not root: yield curr[2] curr = curr[1] def __reversed__(self): 'od.__reversed__() <==> reversed(od)' root = self.__root curr = root[0] while curr is not root: yield curr[2] curr = curr[0] def clear(self): 'od.clear() -> 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() -> (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() -> list of keys in od' return list(self) def values(self): 'od.values() -> list of values in od' return [self[key] for key in self] def items(self): 'od.items() -> list of (key, value) pairs in od' return [(key, self[key]) for key in self] def iterkeys(self): 'od.iterkeys() -> an iterator over the keys in od' return iter(self) def itervalues(self): 'od.itervalues -> an iterator over the values in od' for k in self: yield self[k] def iteritems(self): 'od.iteritems -> 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) -> 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) > 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 "other" 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]) -> 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]) -> 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__() <==> 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() -> a shallow copy of od' return self.__class__(self) @classmethod def fromkeys(cls, iterable, value=None): '''OD.fromkeys(S[, v]) -> 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) <==> 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): "od.viewkeys() -> a set-like object providing a view on od keys" return KeysView(self) def viewvalues(self): "od.viewvalues() -> an object providing a view on od values" return ValuesView(self) def viewitems(self): "od.viewitems() -> a set-like object providing a view on od items" return ItemsView(self) if __name__ == '__main__': d1 = MyOrderedDict([('a', '1'), ('b', '2')]) d1.update({'c':'3'}) print(d1) # -> MyOrderedDict([('a', '1'), ('b', '2'), ('c', '3')]) d2 = MyOrderedDict([('a', '1'), ('b', '2')]) d2.prepend('c', 100) print(d2) # -> MyOrderedDict([('c', 100), ('a', '1'), ('b', '2')]) 

Answer 11

I got an endless loop when trying to print or save a dictionary using @Ashwini Chaudhary's answer with Python 2.7 . But I managed to slightly reduce its code, and it worked 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] < 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 ) 

Answer 12

This is the default, ordered dict, which allows you to insert elements at any position and use. The operator for creating 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]