是否可以交换有序字典的两个键？

Question

注意：我使用的是python 3.8.2，所以字典被认为是有序的

我正在创建一棵二叉树，并使用字典为树建模。例如： {1:[2, 3], 2:[4, 5], 3:[], 4:[], 5:[]}

在示例中，上面的树看起来像这样：

我试图模拟一些节点的“上升”，并保持dict的顺序。我知道使用 myDict[key1], myDict[key2] = myDict[key2], myDict[key1] 是行不通的，因为值的位置会发生变化，而不是键。

我也在考虑使用 .popitem() 删除最后一个值，直到我在 key1 或 key2，然后继续直到我到达另一个键，但这似乎有点难。还有其他方法吗？

Answer 1

由于您只想交换两个密钥，我们可以从以下代码开始：

>>> changedDict = {}
>>> for key, value in myDict.items():
...     if key not in (key1, key2):
...         changedDict[key] = value

并继续如下：

...     elif key == key1:
...         changedDict[key] = myDict[key2]
...     else:
...         changedDict[key] = myDict[key1]

Answer 2

字典，尽管它们现在保持插入顺序，但不能任意排序。如果你真的想使用 dict 顺序信息来构建你的树，我认为唯一可靠的方法是构建一个新的字典，为每个交换操作复制原始字典的内容。

如果您想要一个任意排序的字典，一个更合理的方法是继承自 collections.abc.MutableMapping并使用字典和其他一些数据结构（例如列表）在该对象中跟踪您的数据.

听起来可能很复杂，但它可能比你想象的要简单：

from collections.abc import MutableMapping

class SuperOrdered(MutableMapping):
    def __init__(self):
        self.data = {}
        self.order = []
    def __setitem__(self, key, value):
        if key not in self.data:
            self.order.append(key)
        self.data[key] = value
    def __getitem__(self, key):
        return self.data[key]
    def __delitem__(self, key):
        del self.data[key]
        self.order.remove(key)
    def __len__(self):
        return len(self.data)
    def __iter__(self):
        yield from iter(self.order)
    def replace_key(self, oldkey, newkey, value):
        if newkey in self.data:
            del self[newkey]
        position = self.order.index(oldkey)
        self.order[position] = newkey
        self.data[newkey] = value
    def __repr__(self):
        return f"{self.__class__.__name__}({{{', '.join(repr(key) + ':' + repr(self.data[key]) for key in self)}}})"

瞧瞧 - 映射 +“replace_key”方法应该足以让您按照您的想法构建您的树。

这是上面互动提示中的class：

In [18]: aa = SuperOrdered()                                                                                             

In [19]: aa["a"] = 1;aa["b"] = 2;aa["c"] = 3                                                                             

In [20]: aa                                                                                                              
Out[20]: SuperOrdered({'a':1, 'b':2, 'c':3})

In [21]: aa.replace_key("a", "d", 4)                                                                                     

In [22]: aa                                                                                                              
Out[22]: SuperOrdered({'d':4, 'b':2, 'c':3})

除了这个答案，而且是题外话：如果你想检查我希望“生产就绪”的树实现，我已经发布了一个作为我的 extradict 包的一部分（pip 可安装).

update：也可以从 collections.OrderedDict 继承并在那里添加一个 replace_key 方法。该代码必须处理 OrderedDict 内部结构，但这并不难。

外部链接： Github modification

是否可以交换有序字典的两个键？

Is it possible to swap two keys of an ordered dictionary?

python-3.x

ordereddictionary