6

我正在用 Java 搜索一个列表数据结构，它允许廉价地附加长列表。我试过 LinkedList 但我在addAll的文档中发现，一个迭代器用于附加两个列表。这意味着附加的列表在操作期间被克隆。迭代器遍历整个列表，返回每个元素。是否有任何可用的集合在附加两个列表时省略了迭代？

4

10 回答 10

6

您可以使用Guava 的 Iterables.concat方法来创建连接的 Iterable View..

Iterable<T> combined = Iterables.concat(list1, list2);
  • 这不会将元素从一个列表复制到另一个列表。
  • 因此，它不会更改您的任何列表..
  • 此外，这不会创建一个新列表（它会创建一个Iterable不是列表）

基本上它创建了一个Iterable你可以通过它迭代two列表背靠背（它从list1然后从list2迭代元素..

注意： - 如果您想要一个列表作为 的串联，那么这可能对您没有多大帮助..因为它不会创建一个列表，而是一个 Iterable.. 在这种情况下，除了列表two lists之外，您别无选择Iterating和copy你的每一个参考..

从文档： -

它将两个可迭代对象组合成一个可迭代对象。返回的可迭代对象有一个迭代器，它遍历 a 中的元素，然后是 b 中的元素。直到必要时才会轮询源迭代器。当对应的输入迭代器支持时，返回的迭代器的迭代器支持 remove()。

你也有这个方法的一个var-args版本..参见文档..这可以接受任意数量的列表，并返回可以按顺序迭代这些列表的 Iterables..所以，你可以这样做..

Iterable<T> combined = Iterables.concat(list1, list2, list3, list4, ...);

这个链接 --> google-guava-libraries-essentials你可能也感兴趣..

于 2012-10-10T12:07:08.540 回答
5

并非如此，因为所有“附加”操作都不会对基础集合做出任何假设。从技术上讲，可以直接附加两个链表，但附加必须是通用的，因此它使用迭代。

不允许直接连接的另一个很好的理由是，在追加更改一个列表后也会影响另一个列表，我确信这不是一个理想的属性。

于 2012-10-10T12:02:44.670 回答
4

ArrayList 中的addAll将其转换为 Array，然后使用系统调用进行复制（System.arraycopy）。这应该比在 java 中循环更快，因为它是本机的，我认为没有便宜的附加程序。

于 2012-10-10T12:03:13.113 回答
3

可能是 ArrayList 的 addAll 应该更快，因为它不迭代，而是使用 System.arrayCopy。代码看起来像

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
        int numNew = a.length;
    ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
    return numNew != 0;
    }
于 2012-10-10T12:05:16.747 回答
1

这意味着附加的列表在操作期间被克隆。

创建迭代器不会克隆集合。

在大多数情况下，addAll 方法调用 toArray() 以确保以原子方式提取数据，从而将集合的元素克隆为数组，这很可能使用 Iterator 来完成。

是否有任何可用的集合在附加两个列表时省略了迭代？

不，但如果这真的很重要，您可以自己迭代集合。

最有效的可能是

List<E> list1 = ... random access list ...
List<E> list2 = ... random access list ...

for(int i = 0; i < list2.size(); i++)
    list1.add(list2.get(i));

这不会创建任何对象，并且有O(n)时间nlist2 的大小在哪里。

于 2012-10-10T12:15:02.287 回答
0

即使您确实找到了这样一个集合类，您也不能保证它会在未来的 Java 版本中继续以这种方式工作。这是因为这是 Collection 接口中未指定的行为，因此受类开发人员的突发奇想影响。

当然，您可以编写自己的集合类，但即便如此，您也会对其他集合类的行为做出假设

于 2012-10-10T12:04:09.990 回答
0

addAll方法的默认实现AbstractCollections使用迭代器添加，但addAll方法在提供自定义特定实现的子类中被覆盖

像

  • ArrayList 使用System.arraycopy
  • LinkedList 使用循环遍历元素。
于 2012-10-10T12:05:22.803 回答
0

我认为标准 API 没有办法，但根据您的需要，您可以尝试自己实现一个。例如，您可以实现一个内部有一个集合引用列表，每次调用 addAll 方法时添加。

于 2012-10-10T12:06:55.777 回答
0

通过这种行为，添加到第一个列表的列表将被消耗（即修改）或导致第二个列表成为具有各种陷阱的较大列表的子列表（例如，如果您添加两次列表会发生什么......），

addAll 有一个隐含的 const 参数（意味着第二个列表将在多次调用中保持不变），因此除非您自己滚动，否则此行为将不存在

于 2012-10-10T12:21:42.193 回答
0

我会简单地采用 ArrayList，并愉快地将我的东西添加到它。选择的 List 实现如何执行 addAll() 操作并不重要，迭代或 toArray 都相对便宜，而且这不太可能成为性能瓶颈（假设您的应用程序对列表元素进行了有用的工作，而不仅仅是创建列表...）。

addAll() 中的迭代确实没有办法，如果你想要一个包含 N 个源列表中的元素的独立列表，则必须将元素引用复制到某个地方（你可以在 addAll() 之后更改源列表，但是不得影响已联系的列表，因此副本是不可避免的）。

如果你真的不需要List 语义（独立于源），那么使用已经建议的 Guava 创建多个列表的视图（或者滚动你自己的，如果你不想要依赖，它不是火箭科学） .

于 2012-10-10T12:32:55.840 回答