Добавить новый элемент к исходным элементам, отсортировать, сделать новый дикт:
>>> 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)])
Или чуть более сложный вариант:
- Коллекции подклассов. OrderedDict
- Используя метод
move_to_end в качестве руководства, создайте новый метод, который будет проходить по двусвязному списку; найти место для вставки; затем вставьте новый ключ - может быть, здесь можно использовать bisect или какой-либо другой алгоритм вставки отсортированного списка с двумя связанными списками - переопределить метод
__setitem__ и в вызовите новый метод - или просто замените код add-new-key-to-the-end с алгоритмом, который вы придумали в предыдущем пункте.
Sorted dict, который поддерживает порядок сортировки ключей
Я не мог понять, как заставить работать подкласс OrderedDict - у него есть ряд атрибутов, которые искажают имя - нужно переопределить только один или два метода, и я не хотел тратить время выяснение аспекта искажения имени.
Так что просто скопируйте класс целом OrderedDict из источника отсюда - сюда в отдельный модуль, так что вы можете импортировать его и включить эти импорт.
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 для поиска порядка вставки. Не знаю, действительно ли это оправдано, сначала он должен составить список представлений «dict keys», но эта часть должна быть быстрой 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
>>>