python - 如何将项目添加到 OrderedDict

Question

我有一个OrderedDict，我需要在保持排序的同时添加一个元素

import sys
import bisect
from collections import OrderedDict

arr = {('a',1111),('b',2222),('f',3333)}
arr = OrderedDict(arr)

bisect.insort(arr,('c',4444))
#expectedly      arr = {('a',1111),('b',2222),('c',4444),('f',3333)}

#but actually     TypeError: collections.OrderedDict is not a sequence

更新:我需要按键排序存储项目但与

import sys
import bisect
from collections import OrderedDict
from sortedcontainers import sorteddict
arr = {('a',1111),('b',2222),('f',3333)}
arr = OrderedDict(arr)
arr.update({'c':4444})   #or arr['c'] = 4444
print(arr)

OrderedDict([('b', 2222), ('f', 3333), ('a', 1111), ('c', 4444)])

改为 OrderedDictх([('a',1111),('b',2222),('c',4444),('f',3333)])

像c++中的 map

Answer 1

将新项添加到原始项中，排序，生成新字典:

>>> arr = {('a',1111),('b',2222),('f',3333)}
>>> arr = collections.OrderedDict(arr)
>>> new = ('c',4444)
>>> items = list(arr.items())
>>> items.append(new)
>>> items.sort()
>>> arr = collections.OrderedDict(items)
>>> arr
OrderedDict([('a', 1111), ('b', 2222), ('c', 4444), ('f', 3333)])

---

或者更复杂的选项:

• 子类 collections.OrderedDict
• 使用move_to_end方法作为指导，创建一个将遍历双向链表的新方法；找到插入的地方；然后插入新键——也许可以在这里使用 bisect 或其他一些双向链表排序插入算法
• 覆盖 __setitem__ 方法并在中调用新方法 - 或者只是替换 add-new-key-to-the-end 使用您在上一项目符号中提出的算法编写代码。

---

维护键排序顺序的排序字典

我无法弄清楚如何使 OrderedDict 子类工作 - 它有许多属性名称被破坏 - 只需要覆盖一两个方法，我不想花时间弄清楚名称修改方面。

因此只需从源代码中复制整个 OrderedDict 类from here - to here到一个单独的模块中，因此您可以导入它，并包含这些导入。

from _weakref import proxy as _proxy
from collections import _Link, _OrderedDictKeysView
from collections import _OrderedDictItemsView, _OrderedDictValuesView
import _collections_abc
from _weakref import proxy as _proxy
from reprlib import recursive_repr as _recursive_repr
from operator import itemgetter as _itemgetter, eq as _eq
import bisect

然后在类中更改以下内容:

• 类(class)名称当然可以随心所欲。类名后面是文档字符串和一些描述类行为的注释 - 这些应该更新。

    class SortOrderedDict(dict):

• 覆盖 __setitem__ 方法。下面使用 bisect 来查找插入顺序。不知道是否真的有必要，它必须先列出字典键 View ，但那部分应该是快速的 C 代码(？在这里猜测)

    def __setitem__(self, key, value,
                    dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
        'od.__setitem__(i, y) <==> od[i]=y'
        # Setting a new item creates a new link in the linked list,
        # inserted at its key sorted position - uses less than comparisons,
        # and the inherited dictionary is updated with the new key/value pair.
        if key not in self:
            self.__map[key] = link = Link()
            root = self.__root
            last = root.prev
            link.key = key
            curr = root.next
            if curr is root:    # first item!
                link.prev, link.next = last, root
                last.next = link
                root.prev = proxy(link)
            elif link.key < root.next.key:    # at the beginning?
                #print(f'{link.key} before {root.next.key}')
                soft_link = root.next
                link.prev, link.next = root, soft_link
                soft_link.prev = link
                root.next = link
            elif root.prev.key < link.key:    # at the end?
                #print(f'{link.key} at the end after {root.prev.key}')
                soft_link = root.prev
                link.prev, link.next = soft_link, root
                soft_link.next = link
                root.prev = proxy(link)
            else:    # in the middle somewhere - use bisect
                keys = list(self.keys())
                i = bisect.bisect_left(keys,key)
                right = self.__map[keys[i]]
                #print(f'{link.key} between {right.prev.key} and {right.key}')
                soft_link = right.prev
                link.prev,link.next = soft_link,right
                right.prev = link
                soft_link.next = link

        dict_setitem(self, key, value)

• 添加 update 方法 - 此类是 dict 的子类，它会覆盖其更新方法，迫使它使用 __setitem__。

    def update(self,other):
        try:
            other = other.items()
        except AttributeError:
            pass
        for k,v in other:
            self[k] = v

• 将此行 update = __update = _collections_abc.MutableMapping.update 更改为

    __update = update

• 在 __reduce__ 方法中，将 for k in vars(OrderedDict()): 中的类名更改为您命名类的任何名称

    for k in vars(SortOrderedDict()):

• __eq__ 方法中的相同内容。将 if isinstance(other, OrderedDict): 更改为

    if isinstance(other, SortOrderedDict):

---

如果使用 bisect 似乎不值得，只需遍历链表直到找到插入点。 (上面列出的所有其他更改仍然适用)

    def __setitem__(self, key, value,
                    dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
        'od.__setitem__(i, y) <==> od[i]=y'
        # Setting a new item creates a new link in the linked list,
        # inserted at its key sorted position - uses less than comparisons,
        # and the inherited dictionary is updated with the new key/value pair.
        if key not in self:
            self.__map[key] = link = Link()
            root = self.__root
            last = root.prev
            link.key = key
            curr = root.next
            if curr is root:    # first item!
                link.prev, link.next = last, root
                last.next = link
                root.prev = proxy(link)
            # traverse the linked list; find sorted insertion point; insert
            while curr is not root:
                if link.key < curr.key:
                    soft_link = curr.prev
                    soft_link.next = link
                    link.prev = soft_link
                    link.next = curr
                    curr.prev = link
                    break
                elif curr.next is root:
                    link.prev, link.next = curr, root
                    curr.next = link
                    root.prev = proxy(link)
                    break
                curr = curr.next
        dict_setitem(self, key, value)

用法

>>> arr = {('a',1111),('f',3333),('b',2222)}
>>> arr = SortOrderedDict(arr)
>>> arr
SortOrderedDict([('a', 1111), ('b', 2222), ('f', 3333)])
>>> other = {k:v for k,v in zip('tvsnpqkl',range(8))}
>>> arr.update(other)
>>> arr
SortOrderedDict([('a', 1111), ('b', 2222), ('f', 3333), ('k', 6), ('l', 7), ('n', 3), ('p', 4), ('q', 5), ('s', 2), ('t', 0), ('v', 1)])
>>> b = SortOrderedDict((('a',1111),('f',3333),('b',2222)))
>>> b.update(other)
>>> arr == b
True
>>> b == arr
True
>>>