-2

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

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

容器做了一些额外的工作，它的精确实现可能会改变。

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

如果容器是list-like，有效的移除需要知道对象的索引；知道对象本身不好（我不想在整个容器中搜索元素）。

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

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

如果容器就像一个双向链表，我需要对对象本身的引用。

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

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

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

4

4 回答 4

0

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

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

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

于 2012-04-30T22:20:09.887 回答
0

只需封装 a list and a dict/ a list and a set, ...

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

于 2012-04-30T22:20:42.797 回答
0

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

于 2012-04-30T22:50:38.810 回答
0

除非其他人通过找到更好的解决方案来提供帮助，否则我会这样做：

# 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
    # ...
于 2012-04-30T23:28:34.290 回答