通用引用，允许从各种容器中有效删除

Question

我正在编写一个自定义容器类。构成对象是独立于容器创建的，可以是无容器的成员，也可以是多个容器的成员。容器的公共 API 应支持三个操作：

• 迭代所有对象
• 插入新对象
• 删除现有对象

容器执行一些额外的工作，其精确实现可能会更改。

如何将公共 API 写入此类，以便在更改实现时保持稳定？

如果容器是list的，有效的删除需要了解对象的索引;知道对象本身是不好的(我不想在整个容器中搜索元素(。

如果容器set类似，则没有与索引等效的内容，我需要对象本身。

如果容器就像一个单向链表，我需要在删除对象之前对对象的某种引用。

如果容器类似于双向链表，我需要对对象本身的引用。

我正在考虑让删除方法reference取一个参数，这在删除方法之外没有任何意义或用途。迭代将产生一对(object，reference(。

这个设计有什么问题吗？是否有我可以查找的示例或设计模式？

理想情况下，我宁愿让迭代产生一个包含原始object和reference的复杂对象，并展示两者的接口。但我不认为这是可行的？

Answer 1

大多数容器类型都有一个很好的方向 - 从索引到索引，从当前到下一个，等等。 有些是双向的，但远非全部。

尝试在不使用

索引的情况下在python列表中查找值几乎是O(n(。 您要么需要接受 O(n(，要么使用不同的类型。

关于这一点，我想到的一件事是，如果您需要从大量容器类型中快速删除某些内容，则可以在值中添加"ignore_this"属性。 如果将其设置为 true，则所有容器类型都会开始忽略它，甚至在看到它时将其删除。

Answer 2

只需封装一个list和一个dict/一个list和一个set，...

大约使您的内存使用量和操作时间翻倍，但巧妙的封装通常会使几乎所有与问题相关的操作O(1)。

Answer 3

如果您

使用的是Python 2.7及更高版本，则可能值得查看collections.OrderedDict： http://docs.python.org/library/collections.html#collections.OrderedDict

Answer 4

以下是我会做的，除非其他人通过找到更好的解决方案来提供帮助：

# to get __hash__ and __eq__ return id(self)
class Reference:
  def __init__(self, item):
    self.item = item
class RemovalAPI:
  def add_removal_info(self, item, removal_info):
    try:
      references = item.__reference
    except AttributeError:
      references = item.__reference = {}
    references[Reference(self)] = removal_info
  def get_removal_info(self, item):
    try:
      references = item.__reference
      self_reference = Reference(self)
      return references[self_reference]

class Container(list, RemovalAPI):
  def __iter__(self):
    for i in range(len(self)):
      item = self[i]
      self.add_removal_info(item, i)
      yield item
  def remove(self, item):
    removal_info = self.get_removal_info(item)
    del self[removal_info]
  def insert(self, item):
    self.add_removal_info(item, len(self))
    self.append(item)
    # do whatever post-processing I need
    # ...

如果我随后决定将实现从list更改为其他数据结构，则公共接口可以保持不变：

class Container(orderedset, RemovalAPI):
  # inheriting __iter__, remove from parent
  def insert(self, item):
    self.add(item)
    # do whatever post-processing I need
    # ...

或。。。

class Container(linkedlist, RemovalAPI):
  def __iter__(self):
    it = super().__iter__()
    last_item = None
    for item in it:
      self.add_removal_info(item, last_item)
      yield item
  def remove(self, item):
    removal_info = self.get_removal_info(item)
    if removal_info is None:
      self.remove_first()
    else:
      self.remove_after(removal_info)
  def insert(self, item):
    self.add_removal_info(item, None)
    self.add_to_front(item)
    # do whatever post-processing I need
    # ...