Java的侵入式列表实现？

Question

是否有任何(良好实现的)侵入式双链表类可用于Java？或者我应该自己做？Boost为C++提供了它:http://beta.boost.org/doc/libs/1_40_0/doc/html/boost/intrusive/list.html.

侵入列表是一个容器(在这种情况下)是元素中的next和prev指针,因此像replace和remove这样的典型列表操作可以直接定位到基本类而不是容器类.在某些情况下,侵入列表是最佳解决方案.

我试着给出一个恰当的例子.假设我有不同类型的X1和Y2所拥有的链表L list1和L list2.

Q类(没有任何关系或者不容易访问x1和Y2的接口,否则)需要做i)替换,ii)删除元素e的操作,它总是存在于某个地方,在list1 xor list2中取决于运行时状态,但该信息不会直接存储在任何地方.

使用intrussive列表Q可以将元素的引用存储到成员元素e,并且它总是指向正确的位置.

否则,您必须从几个明显更复杂的解决方法中选择一个或另一个. - 元素e的包装类和完成操作i和ii的其他方法.没有.

基本上,问题仍然不是性能而是架构复杂性.这也可以理解为一种共享对象情况,其中解决方案IL避免了对每个客户端Lx和Q的更新需求.

请注意,我没有必要与其他标准容器兼容.只是一个通用的侵入式lsit实现,具有与未知元素类一起使用的迭代,添加,删除和查找操作.

谢谢.

Answer 1

我不知道任何现有的实现(不,我不认为普通的Java集合是侵入性的).

这可能是因为这样一个列表在Java中唯一的主要优点就是快速remove()调用,当你已经有元素被删除时(并且没有Iterator在那个位置).not-copying-the-element不是Java中的有效参数,因为Java List实现无论如何只处理引用(并且永远不会复制整个对象).

但是List,通过创建必要的接口,您可以轻松编写一个侵入性的通用实现:

public interface IntrusiveListElement<E extends<IntrusiveListElement<E>> {
  public void setNext(E next);
  public E getNext();
  public void setPrev(E prev);
  public E getPrev();
}

public class IntrusiveList<E extends IntrusiveListElement<E>> implements List<E> {
  // implement your run-of-the-mill double-linked list here
}

您的元素类可能如下所示:

public class MyBusinessElement implements IntrusiveListElement<MyBusinessElement> {
  private MyBusinessElement prev;
  private MyBusinessElement next;

  public void setNext(MyBusinessElement next) {
    this.next = next;
  }

      public MyBusinessElement getNext() {
    return next;
  }

  public void setPrev(MyBusinessElement prev) {
    this.prev = prev;
  }

  public MyBusinessElement getPrev() {
    return prev;
  }
}

Answer 2

是否有任何(良好实现的)侵入式双链表类可用于Java？

我不相信你会找到一个.

我对"侵入式"的理解是,要存储在数据结构中的应用程序对象需要直接包含("入侵")应用程序对象中的next/prev指针.

这与"指针包装器"方法形成对比,其中数据结构节点包含指向应用程序对象的指针,因此不需要修改应用程序对象.侵入式方法有许多好处,包括避免对"指针包装器"方法通用的双重解除引用(一次用于节点,一次用于节点指向应用程序对象的指针).

我不相信你会找到一个针对Java的侵入式数据结构库.Java缺乏类似C++的模板,也没有多重继承,并且它不容易支持整个对象的按值复制.因此,我认为没有办法将下一个/ prev实例字段一般性地添加到Java对象中.

例如,给定应用程序对象:

class Foo {
    int bar;
}

不知何故,你需要能够为它或它的衍生物添加next/prev字段和列表管理方法:

class Foo2 {
    int bar;
    Foo2 prev;
    Foo2 next;
}

添加这些字段的一种方法是通过为这些应用程序类提供这些字段的基类来扩展 - 这是Boost的方法.但是,这种方法在像Java这样的单继承语言中非常有限.

Java接口通常是Java对多重继承的回答,例如需要应用程序类的getNext()和getPrev()方法的接口.但是,如果出于性能原因需要侵入式数据结构,则通过方法访问next/prev字段可能会对这些目标产生负面影响.

Java泛型也不以所需方式扩展类.

或者我应该自己做？

如果有一次针对特定情况进行仔细评估需求,请确保自己动手.如果你试图将通用的一个用于通用目的,我不确定它是否值得.

一个非常重要的方法是自定义扩展应用程序类以添加所需的字段:

class Foo3 extends Foo {
    Foo3 prev;
    Foo3 next;
}

并使用cut-n-paste重用来添加列表管理方法.但我强烈建议不要使用这种方法.

肥皂盒

您没有说明为什么需要侵入式数据结构.也许你有正当理由需要一个,但很难想象它们.Java非常依赖于使用对象指针并试图避免它们,因为这很难.

我恭敬地建议你考虑一下:

• 你想过早地优化,
• 你是否添加了不必要的复杂功
• 如果速度和内存管理是最重要的,你使用正确的语言吗？