哪种 Collection 类型最适合不断更新的、固定大小的字符串数组？

Question

我遇到过这样一种情况，我需要 Android 中的 Collection 类型可以容纳 String 个对象并满足以下条件：

它有一个固定大小（比如 10）。
只会从 Collection
添加一个新对象时，所有其他对象会自动沿着一个 space 移动以容纳它。
如果Collection已满（全部10 space被占用），那么随着从一端添加一个对象，从另一端删除对象。
可以随时在任一方向遍历 Collection 的内容，并在每个位置检索对象。

根据我对集合类型的经验，我觉得 Queue 或 LinkedList 之类的东西比较合适，尽管我个人从未使用过其中任何一种。但是，Android 文档中的一些术语让我对它们是否满足我的要求感到困惑。

例如，在 Queue 的文档中指出：

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner...

这听起来很理想，但是当我考虑 add() 和 offer() 方法时，它们都指定：

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.

这听起来与我所追求的相反。

对于 LinkedList，描述包括以下行：

This class is primarily useful if you need queue-like behavior.

这是完美的，但稍后它又暗示了一个事实，即 LinkedList 在需要灵活的尺寸时很有用。

It may also be useful as a list if you expect your lists to contain zero or one element, but still require the ability to scale to slightly larger numbers of elements.

在 this tutorial site 上：

The major benefit of linked lists is that you do not specify a fixed size for your list. The more elements you add to the chain, the bigger the chain gets.

有人可以澄清这些类型中的一种是否适合我的情况吗？

Answer 1

LinkedList 当然可以。 "add" 逻辑只是：

list.add(newItem);
if (list.size() > MAX_SIZE) {
    list.remove(0);
}

如果你需要超高效，String[MAX_SIZE] 可能是合适的，用 current 索引说明你在其中的位置（例如，环形缓冲区）。 "Add" 逻辑是：

buffer[current] = newItem;
current = (current + 1) % MAX_SIZE;

最后一行移动到下一个位置，如有必要，再次环绕到 0。

假设您预先填充它（例如，它永远不会为空或部分为空），按添加顺序循环逻辑是：

for (int index = (current + 1) % MAX_SIZE; index != current; index = (index + 1) % MAX_SIZE) {
    // ...
}

如果它可能为空或部分为空，并且假设 null 不是有效的非空值，您将执行相同的操作但跳过 nulls。

Answer 2

别偷懒自己做！

public class Collection<T> implements Iterable<T>, RandomAccess{
    private final Object[] data;
    private int size = 0;

    public enum Direction{
        LEFT,
        RIGHT
    }

    private Direction direction = Direction.LEFT;

    public Collection(int capacity){
        data = new Object[capacity];
    }

    public void setDirection(Direction direction){
        this.direction = direction;
    }

    public void add(T item){
        if(size < data.length){
            switch (direction){
                case LEFT:
                    data[data.length - size] = item; 
                    break;
                case RIGHT:
                    data[size] = item;
                    break;
            }
            size++;
        }
        else {
            switch (direction) {
                case LEFT:
                    System.arraycopy(data, 1, data, 0, data.length - 1);
                    data[0] = item;
                    break;
                case RIGHT:
                    System.arraycopy(data, 1, data, 0, data.length - 1);
                    data[data.length - 1] = item;
                    break;
            }
        }
    }

    public void remove(){
        if(size == 0){
            return;
        }
        switch (direction){
            case LEFT:
                remove(data.length - size);
                break;
            case RIGHT:
                remove(size);
                break;
        }
    }

    public int size(){
        return size;
    }

    private void remove(int index) {
        System.arraycopy(data, index + 1, data, index, data.length - 1 - index);
        data[data.length - 1] = null;
    }


    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private int current = direction == Direction.RIGHT ? 0 : data.length - 1;

            @Override
            public boolean hasNext() {
                switch (direction){
                    case LEFT:
                        return current > 0;
                    case RIGHT:
                    default:
                        return current < data.length;
                }
            }

            @Override
            public T next() {
                current += direction == Direction.RIGHT ? 1 : -1;
                Object result = data[current];
                //noinspection unchecked
                return (T) result;
            }

            @Override
            public void remove() {
                Collection.this.remove(current + (direction == Direction.RIGHT ? -1 : 1));
            }
        };
    }
}

Answer 3

有一个 Collection 几乎可以满足您的所有要求 - 它就是 ArrayDeque！

不幸的是，它在一方面不足，引用：

Array deques have no capacity restrictions; they grow as necessary to support usage.

好的方面：

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

此外，如果您的设计基于现有的 class，那么 space 就不会犯错误。

那么，如何将 ArrayDeque 行为更改为在添加元素时不调整大小，而是丢弃旧元素？简单 - 所有添加都通过以下两种方法之一进行：addFirst(E e) 和 addLast(E e)。这些方法是 public，因此可以被覆盖。

因此，我向您展示了一个不调整大小的 ArrayDeque 版本：

private final int maxSize;
public MyArrayDeque(int maxSize) {
    super(maxSize);
    this.maxSize= maxSize;
}

@Override
public void addFirst(E e) {
    if (maxSize == size()) 
        removeLast();
    super.addFirst(e);
}

@Override
public void addLast(E e) {
    if (maxSize == size()) 
        removeFirst();
    super.addLast(e);
}

就是这样。当然，您还应该修改 clone() 的行为和序列化方法，如果您想要真正彻底，则不可以，但这对于大多数用例来说是可选的。另外，不要向任何 OOP 纯粹主义者展示此代码，这不是很好的继承用法 =)

如果您追求性能，您可能想要实际复制 class 中的代码并就地进行修改。这将允许您在无法调整大小时删除一些冗余的检查和方法。它还将允许更快的 for 循环而不创建 Iterator（通过简单地获取 Iterator 中的代码 - 它在精神上接近@T.J。Crowder 的版本，但使用按位运算符，因为数组是 2 的幂长度）。

哪种 Collection 类型最适合不断更新的、固定大小的字符串数组？

Which Collection type is most appropriate for a constantly updated, fixed-size array of Strings?

java

collections

android