Comment ajouter un élément au début d'un OrderedDict ?

Question

J'ai ça :

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

Si je fais ça :

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

Puis je reçois ça :

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

mais je veux ça :

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

sans créer de nouveau dictionnaire.

Answer 1

Il n'y a pas de méthode intégrée pour faire cela dans Python 2. Si vous en avez besoin, vous devez écrire un fichier prepend() méthode/fonction qui opère sur le OrderedDict internes avec une complexité O(1).

Pour Python 3.2 et les versions ultérieures, il faut devrait utiliser le move_to_end méthode. La méthode accepte un last qui indique si l'élément sera déplacé vers le bas ( last=True ) ou le haut ( last=False ) de la OrderedDict .

Enfin, si vous voulez un rapide, sale et lent vous pouvez simplement créer une nouvelle OrderedDict à partir de rien.

Détails pour les quatre solutions différentes :

---

Étendre le site OrderedDict et ajouter une nouvelle méthode d'instance

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)

Démonstration :

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

---

Fonction autonome qui manipule OrderedDict objets

Cette fonction fait la même chose en acceptant l'objet dict, key et value. Personnellement, je préfère la classe :

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)

Démonstration :

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

---

Utilisez OrderedDict.move_to_end() (Python >= 3.2)

Introduction de Python 3.2 le site OrderedDict.move_to_end() méthode. En l'utilisant, nous pouvons déplacer une clé existante vers l'une ou l'autre extrémité du dictionnaire en O(1) temps.

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

Si nous avons besoin d'insérer un élément et de le déplacer vers le haut, tout cela en une seule étape, nous pouvons l'utiliser directement pour créer un élément de type prepend() (non présenté ici).

---

Créer un nouveau OrderedDict - lent ! !!

Si vous ne voulez pas faire ça et la performance n'est pas un problème Le moyen le plus simple est de créer un nouveau 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

sortie :

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

---

Answer 2

ÉDITER (2019-02-03) Notez que la réponse suivante ne fonctionne que sur les anciennes versions de Python. Plus récemment, OrderedDict a été réécrit en C. De plus, cela touche les attributs de double-sous-entrée, ce qui est mal vu.

Je viens d'écrire une sous-classe de OrderedDict dans un de mes projets dans un but similaire. Voici l'essentiel .

Les opérations d'insertion sont également à temps constant O(1) (ils ne vous obligent pas à reconstruire la structure des données), contrairement à la plupart de ces solutions.

>>> d1 = ListDict([('a', '1'), ('b', '2')])
>>> d1.insert_before('a', ('c', 3))
>>> d1
ListDict([('c', 3), ('a', '1'), ('b', '2')])

Answer 3

Vous devez créer une nouvelle instance de OrderedDict . Si vos clés sont uniques :

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

Mais si ce n'est pas le cas, méfiez-vous car ce comportement peut ou non être souhaité pour vous :

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

Ceci est maintenant possible avec 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 5

Si vous savez que vous aurez besoin d'une clé 'c', mais que vous ne connaissez pas sa valeur, insérez 'c' avec une valeur fictive lorsque vous créez le dict.

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

et changer la valeur plus tard.

d1['c'] = 3