连接不可变列表

Question

我有一个List<ImmutableList<T>>. 我想把它压平成一个单一的ImmutableList<T>，它是所有内部ImmutableLists. 这些列表可能很长，因此我不希望此操作执行所有元素的副本。ImmutableLists要展平的数量将相对较小，因此查找与 的数量呈线性关系是可以的ImmutableLists。我强烈希望串联将返回一个Immutable集合。我需要它返回一个List可以在随机位置访问的。

有没有办法在番石榴中做到这一点？

有Iterables.concat但返回一个Iterable. 将其ImmutableList再次转换为列表 IIUC 的大小将是线性的。

Answer 1

根据设计，Guava 不允许您定义自己的ImmutableList实现（如果定义了，则无法强制执行它是不可变的）。通过在com.google.common.collect包中定义自己的类来解决这个问题是一个糟糕的主意。你违背了 Guava 库的承诺，并且在“未定义行为”领域坚定地运行，没有任何好处。

看你的要求：

• 您需要在亚线性时间内连接n 个 ImmutableList实例的元素。
• 您希望结果也是不可变的。
• 您需要执行结果List，并且可能是ImmutableList.

如您所知，您可以通过调用 获得前两个项目符号Iterables.concat()，但是如果您需要 O(1) 随机访问，List这不会削减它。没有List由Lists序列支持的标准实现（在 Java 或 Guava 中），但自己创建一个很简单：

/**
 * A constant-time view into several {@link ImmutableList} instances, as if they were
   concatenated together. Since the backing lists are immutable this class is also
   immutable and therefore thread-safe.
 * 
 * More precisely, this class provides O(log n) element access where n is the number of
 * input lists. Assuming the number of lists is small relative to the total number of
 * elements this is effectively constant time.
 */
public class MultiListView<E> extends AbstractList<E> implements RandomAccess {
  private final ImmutableList<ImmutableList<E>> elements;
  private final int size;
  private final int[] startIndexes;

  private MutliListView(Iterable<ImmutableList<E>> elements) {
    this.elements = ImmutableList.copyOf(elements);
    startIndexes = new int[elements.size()];
    int currentSize = 0;
    for (int i = 0; i < this.elements.size(); i++) {
      List<E> ls = this.elements.get(i);
      startIndexes[i] = ls.size();
      currentSize += ls.size();
    }
  }

  @Override
  public E get(int index) {
    checkElementIndex(index, size);
    int location = Arrays.binarySearch(startIndexes, index);
    if (location >= 0) {
      return elements.get(location).get(0);
    }
    location = (~location) - 1;
    return elements.get(location).get(index - startIndexes[location]);
  }

  @Override
  public int size() {
    return size;
  }

  // The default iterator returned by AbstractList.iterator() calls .get()
  // which is likely slower than just concatenating the backing lists' iterators
  @Override
  public Iterator<E> iterator() {
    return Iterables.concat(elements).iterator();
  }

  public static MultiListView<E> of(Iterable<ImmutableList<E>> lists) {
    return new MultiListView<>(lists);
  }

  public static MultiListView<E> of(ImmutableList<E> ... lists) {
    return of(Arrays.asList(lists));
  }
}

此类是不可变的，即使它不扩展ImmutableList或ImmutableCollection，因此它实际上没有必要扩展ImmutableList。

至于这样的类是否应该由Guava提供；你可以在相关的问题中提出你的案例，但它不存在的原因是令人惊讶的是很少有用户真正需要它。确保Iterable在使用之前没有合理的方法来解决您的问题MultiListView。