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