用于插入、删除和搜索的高效数据结构

Question

在使用某些资源时，我需要跟踪打开和关闭状态。我使用的第一个结构是两个open_states_list和closed_states_list，当状态更新时，我会添加和删除它们。你知道吗

• 插入是O（1）如果我们忽略内存分配和再分配机制，我猜：open_states_list.append(x)。你知道吗
• 删除是O（n）：open_states_list.remove(x)。你知道吗
• 搜索，就像删除一样，是O（n）：x in open_states_list。你知道吗
• 得到名单显然是O（1）。你知道吗

我使用的第二个结构是一个布尔值为open_states = {}的字典，如果open_states[x]是True，那么x是打开的，如果是False，那么它是关闭的。你知道吗

• “Inserting”是O（1），因为我们只是设置一个键和一个值：open_states[x] = True。你知道吗
• “Deleting”是O（1），原因相同：open_states[x] = False。你知道吗
• “search”也是O（1），只是访问键的值：open_states[x]。你知道吗
• 获取列表是O（n）：[x for x, s in open_states.iteritems() if s]。你知道吗

我们最常见的操作是检查x是否打开（搜索），因此第二个选项更好。但是我们第二个最常见的操作，获取打开或使用状态的列表，紧跟搜索操作，在第一个选项中效率更高。但是我们不能选择第一个选项，因为检查资源的状态是O（n）。你知道吗

插入也很常见。移除没有必要。你知道吗

满足这些需求的最有效的数据结构是什么？你知道吗