将新项添加到原始项中,进行排序,创建一个新字典:
>>> arr =
>>> 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
方法作为指南,创建一个新方法将遍历双向链表;找到要插入的位置;然后插入新的键 - 可能可以在这里使用二分法或其他双向链表排序插入算法
- 覆盖
__setitem__
方法,并在其中调用新方法 - 或者使用前面一个项目中想出的算法来替换添加新键到末尾的代码。
保持键排序的排序字典
我无法弄清楚如何使有序字典子类起作用 - 它有许多被名称修饰的属性 - 只需要重写其中一两个方法,而我不想花时间弄清楚名称修饰方面的内容。
所以只需将整个有序字典类从源从这里 - 到这里复制到一个单独的模块中,以便您可以导入它,并包括这些导入。
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 SortOrderedDict(dict):
- 重写
__setitem__
方法。以下使用bisect
查找插入顺序。不知道是否真的有必要,它必须先制作一个字典键视图列表,但那部分应该是快速的C代码(?我在猜测)
def __setitem__(self, key, value,
dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
'od.__setitem__(i, y) <==> od[i]=y'
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:
link.prev, link.next = last, root
last.next = link
root.prev = proxy(link)
elif link.key < 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:
soft_link = root.prev
link.prev, link.next = soft_link, root
soft_link.next = link
root.prev = proxy(link)
else:
keys = list(self.keys())
i = bisect.bisect_left(keys,key)
right = self.__map[keys[i]]
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):
如果使用二分法不值得,那就遍历链表直到找到插入点。(上面列出的所有其他更改仍然适用)
def __setitem__(self, key, value,
dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
'od.__setitem__(i, y) <==> od[i]=y'
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:
link.prev, link.next = last, root
last.next = link
root.prev = proxy(link)
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 =
>>> arr = SortOrderedDict(arr)
>>> arr
SortOrderedDict([('a', 1111), ('b', 2222), ('f', 3333)])
>>> other =
>>> 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
>>>
dict
默认是有序的(在规范中)。你可以简单地执行arr = dict((('a',1111),('b',2222),('f',3333)))
,从而插入一个有序字典。 - modesitt