Python:递增字典键

Question

我有一本大的（订购的）词典（1万到5万个词条）：

from collections import OrderedDict

d = OrderedDict()
...
d[100] = [x100, y100]
d[101] = [x101, y101]
d[102] = [x102, y102]
...

我想在字典中的键100和{}之间插入一个新条目，并更新大于第一个键的每个键。在

^{pr2}$

我该怎么做？在

当我从字典中删除条目时，我可以使用这种方法

for key in d:
    if key > inserted_value:
        d[key - 1] = d[key]
        del d[key]

但当我添加条目时，这不起作用（因为在更新密钥之前，d[key + 1]已经存在）。在

有什么想法吗？在

Answer 1

对于使用算法方法的插入，您需要转到字典的最后一个元素，然后将每个元素向右移动，为要插入的元素创建空间。在

现在，问题将转到字典的最后一个元素，只有将dictionary转换为list时才有可能。在

d.keys()[-1]

要求字典中的“最后一个”键是没有意义的，因为字典键是无序的。如果你愿意的话，你可以得到一个键列表和最后一个键，但这在任何意义上都不是“字典中的最后一个键”。在

既然你有一个有序的列表字典似乎是一个错误的选择，你可能会想到使用一个列表。以防万一，如果你需要引入一些解决方案，把dict转换成前面提到的列表。在

Answer 2

下面是一些实际可行的代码（我相信它在Python2或3中也能工作）。在

def insert(d, key, value):
    # when you're moving up, start at the top
    up = max(d.keys()) + 1    # Py2: iterkeys() uses less memory
    while up > key:
        d[up] = d[up - 1]     # pull up each item
        up -= 1
    d[key] = value

用法：

^{pr2}$

您可以轻松地将其合并到OrderedDict的子类中：

from collections import OrderedDict

class InsertableOrderedDict(OrderedDict):
    def insert(self, key, value):
        up = max(self.keys()) + 1    # Py2: iterkeys()
        while up > key:
            self[up] = self[up - 1]
            up -= 1
        self[key] = value

请注意，OrderedDict会回忆条目被添加到字典中的顺序，而从技术上讲，这个顺序不会被这个过程更新。（Order是由OrderedDict类在内部保存的，我们无法方便地访问它。）但是，它仍然可以工作，因为添加了一个新的项，而这个项是最近添加的项，它显示为OrderedDict的最后一个项，正好是我们想要的位置！在

不过，OrderedDict并不是你真正想要的。正如其他人所指出的，在一个简单的dict字典中使用这个也不是一个好主意。一个list将是更好的更好：内存效率更高，插入速度更快。在

Answer 3

你想做的似乎是在破坏使用字典的目的。在

不管怎样，如果您使用的是OrderedDict，您可以先获取字典键的副本，然后以相反的顺序迭代它们，重新分配值，这样以前由键k_i键控的值现在由键k_i+1键控。当达到边界键值时，中断循环。最后，插入新值。在

keys = list(d.keys())
keys.sort(reverse=True)
increased_k = keys[0] + 1  # use +1 to increment the largest key 
for k in keys:
    if k < new_key: break
    d[increased_k] = d[k]
    increased_k = k

d[new_key] = new_value  # insert the new item

这假设字典中已经存在new_key，因此保留了顺序。在