创建一个包含两个键并引用同一值的字典。

Question

我希望有一个字典（或支持此功能的数据结构），可以通过两个键访问值，但是当你使用其中一个键 .pop() 弹出值时，它也会弹出另一个条目。

• 整个字典中只能存在两个相同的项
• 这些项位于不同的列表中。列表通过键访问
• 删除这两个项必须是 O(1) 的（就像简单地使用 .pop() 一样）

我的尝试：

from collections import defaultdict

class Value:
    def __init__(self, v=None):
        self.v = v

    def __repr__(self):
        return str(self.v)

list_of_words = ['barrd', 'laary', 'grrup']
words = defaultdict(list)

for word in list_of_words:
    temp_word = Value(word)
    words[word[1:2]+'P'].append(temp_word)
    words[word[-2:-1]+'S'].append(temp_word)


print(words)
current = 'baard'
print(words[current[-2:-1]+'P'].pop())
print(words)

实际输出：

defaultdict(<class 'list'>, {'aP': [barrd, laary], 'rS': [barrd, laary], 'rP': [grrup], 'uS': [grrup]})
grrup
defaultdict(<class 'list'>, {'aP': [barrd, laary], 'rS': [barrd, laary], 'rP': [], 'uS': [grrup]})

期望输出：（'grrup' 从两个关键位置中删除）

defaultdict(<class 'list'>, {'aP': [barrd, laary], 'rS': [barrd, laary], 'rP': [grrup], 'uS': [grrup]})
grrup
defaultdict(<class 'list'>, {'aP': [barrd, laary], 'rS': [barrd, laary], 'rP': [], 'uS': []})

简单示例:

示例代码:

d = {'a': [10, 2, 3], 'b': [2, 10]}
d.pop('b') # pop's 10 from key 'b', also removing it from 'a'
d = {'a': [2, 3], 'b': [2]}

- Wizard

---

简化示例如下：{'a': [1, 2, 3], 'b': [2, 3]}。如果弹出值为2，结果是{'a': [1, 3], 'b': [3]}还是其他什么？对于相同键的重复值，弹出它们只会删除一个实例还是所有实例？如果您在帖子中提供一些更简单的示例输入/输出，将有助于解决问题。 - Jon Clements

还有这样的情况怎么办：data = [1, 2]; d = {'a': data, 'b': data}... ? 这是有保证的，还是值总是应该是列表？ - Jon Clements

从列表中删除两个项必须是O(1)，实际上你不能真正在O(1)时间内从列表中删除一个项。 - Aran-Fey

你的简化示例与你的限制不一致：如何在O(1)中从d[a]中删除10？ - sciroccorics

我的问题是关于一种能够实现这个功能的数据结构。我知道你可以用较慢的时间将其删除。因此，我想知道是否可以将这些项配对，或者使用多个字典的映射来实现O(1)的删除。 - Wizard

Answer 1

这样怎么样？

from collections import defaultdict

class MyDataStructure(defaultdict):
    def mypop(self, value):
        for key in self:
            self[key] = [i for i in self[key] if str(i) != str(value)]
        return self

class Value:
    def __init__(self, v=None):
        self.v = v

    def __repr__(self):
        return str(self.v)

list_of_words = ['barrd', 'laary', 'grrup']
words = MyDataStructure(list)
# pdb.set_trace()

for word in list_of_words:
    temp_word = Value(word)
    # second letter + P
    words[word[1:2] + 'P'].append(temp_word)
    # second last letter + S
    words[word[-2:-1] + 'S'].append(temp_word)

print(words)
current = 'barrd'
words.mypop(current)
print(words)

输出：

defaultdict(<class 'list'>, {'aP': [barrd, laary], 'rS': [barrd, laary], 'rP': [grrup], 'uS': [grrup]})
defaultdict(<class 'list'>, {'aP': [laary], 'rS': [laary], 'rP': [grrup], 'uS': [grrup]})

- Ashish Acharya