java - 为实现Iterable的类编写remove方法

Question

因此，我有一个实现Iterable的类，以为其编写一组方法。他们中的大多数都很容易思考，但是，我在为类编写remove方法时遇到了麻烦。

import java.util.Iterator;

public class Bag<Item> implements Iterable<Item> {

    private Item[] data = (Item[]) new Object[5];

    // The size variable keeps track of how many items
    private int size = 0;

    public String toString() {
        StringBuilder b = new StringBuilder("[");
        for (Item i : this)
            b.append(i + " ");
        return b.toString() + "]";
    }

    public void expandArray() {
        int capacity = data.length * 2;
        Item[] newData = (Item[]) new Object[capacity];
        for (int i = 0; i < data.length; i++)
            newData[i] = data[i];
        data = newData;
    }

    public boolean add(Item x) {
        if (size == data.length)
            expandArray();
        data[size++] = x;
        return true;
    }

    // return an Iterator for the bag
    public Iterator<Item> iterator() {
        return new BagIterator<Item>();
    }

    // Iterator class
    public class BagIterator<Item> implements Iterator<Item> {

        private int i = 0;

        public boolean hasNext() {
            return i < size;
        }

        public Item next() {
            return (Item) data[i++];
        }

    }

    public boolean contains(Item x) {
        for (int i = 0; i < data.length; i++) {
            if (data[i] == x)
                return true;
        }
        return false;
    }

    public boolean addUnique(Item x) {
        for (int i = 0; i < data.length; i++) {
            if (data[i] == x)
                return false;
        }
        this.size++;
        this.add(x);
        return true;
    }

    public boolean remove(Item x) {

        Item lastItem = x; // holds x item
        Item swap; // holds item to swap
        int swapIndex; // holds index of item to swap

        for (int i = 0; i < data.length; i++) {
            if (data[i] == x) {
                // Save the last item
                lastItem = data[3];
                // Save the swapped item
                swap = data[i];
                // Save the index of swapped item
                swapIndex = i;
                // move swap item to end of list
                data[3] = swap;
                // move last item to swap pos
                data[swapIndex] = lastItem;
                // remove last item in list
                this.size--;
                return true;
            }
        }
        return false;
    }

    public boolean equals(Object o) {
        Bag<Item> b = (Bag<Item>) o;
        return false;
    }
}

我对remove方法的想法如下：穿过袋子，找到要删除的物品，取出相同的物品并将其移至袋子的末端（将其与袋子中的最后一个物品交换位置），然后减小袋子的尺寸（以为可以去除）它）。

现在显然我的想法有些问题。 1）袋子仍然是原始尺寸。 2）袋子现在是无序的，稍后在比较两个袋子时会引起问题。

所以我的问题是，我如何能有效地编写一个remove方法来从我的包类中取出一个项目，而不会遇到前面提到的问题。

主要

public class Main {

    public static void main (String[] args) {

        Bag<Integer> bag = new Bag<>();

        bag.add(1);
        bag.add(2);
        bag.add(3);
        bag.add(4);

        System.out.println(bag); // [1, 2, 3, 4]

        System.out.println(bag.remove(4)); // should remove 4 and return true **WORKING
        System.out.println(bag.remove(1)); // should remove 1 and return  true **WORKING
        System.out.println(bag.remove(1)); // should NOT remove 1 and return false **NOT WORKING

        System.out.println(bag); // [4 ] 

    }
}

Answer 1

不知何故，我第一次完全误读了你的问题；我知道现在您甚至没有实现Iterator.remove()。 Iterable.remove()也是棘手的，让我们谈谈！

首先，您可能不想直接实现Iterable。它只允许您遍历一系列元素（并可以选择调用Iterator.remove()），而没有别的。您的Bag类可能应该实现Collection（或扩展AbstractCollection），这是大多数Java数据结构实现的常规接口（它指定.add()，.remove()，.size()等）。

创建数据结构（例如bag）时要记住的关键是强制执行invariants。粗略地说，不变是关于数据结构或方法的行为的保证。例如，每次在空数据结构上调用.size()时，它将返回0。一旦调用.add()，以后所有对.size()的调用都将返回1（直到您进一步修改数据结构）。这是不变的。看起来似乎很明显，但是随着数据结构变得越来越复杂，这些简单的保证使代码推理变得更加简单。

关于您的特定问题。首先，您的想法是将物品移到最后，这是一个很好的直觉。这比将其余元素复制到新索引中要有效得多。

您首先担心的是，Bag的大小仍然相同，这实际上不是问题。由于递减size，有效地删除了数组末尾的项目。您可以将其设置为null以删除引用，但就正确性而言，它不是必需的。相反，您应该查看其他方法，例如contains()，并确保它们尊重size。您应该只查看小于size的索引，而不是data.length，因为size和data.length之间的值可能是垃圾。

关于比较两个Bag的第二个问题是暴露另一个问题。您的类实际上没有提供将要对数组进行排序的不变性（再次有该词），因此在.remove()期间对其进行重新排序不会使事情变得比以前更糟。问题是您的类不会覆盖.equals()和.hashcode()（您必须两者都不做），这意味着无论元素的顺序如何，都不能将两个Bag实例视为等效的。如果打算比较Bag，则需要正确实现这些方法。假设您要这样做，绝对是棘手的。一般而言，没有一种比较两个无序对象集合的有效方法-您唯一的选择是遍历两个集合的所有元素，直到您确认它们包含相同的元素。性能为O（n ^ 2）或二次方（即非常慢）。

您有两个基本选择；确保您的支持数组始终排序（这是不变的-在将对数组进行排序的每种方法的末尾），或者使用效率更高的数据结构进行相等性检查，例如Set。两种选择都有权衡。正确地确保始终对数组进行排序非常棘手； Java的TreeMap做到了这一点，大多数人认为这是他们永远不想自己重新实现的代码类型。使用Set可让您有效地检查集合中是否存在某个元素，但这是以防止重复元素为代价的。 “袋子”数据结构通常允许重复，因此对于您的用例，使用Set作为后备数据结构可能是不可接受的。使用一个Map<E, Integer>值是一个计数将是可行的，但是要跟踪的工作量却更多。

但是，作为起点，标准的蛮力.equals()实现可能就足够了。优秀软件工程的核心任务是避免过度优化。从可行的东西开始，然后使其变得更好，而不是尝试从一开始就使效率完全提高。