使用 ListIterator 且是唯一列表的集合

Question

这让我最近在一个项目中很烦，我的 Google 呼呼让我找不到合适的答案。

是否有一个集合可以访问 ListIterator 但也只允许集合中的唯一值？

出于这个原因，我有一个项目集合，在这个集合中，每个元素应该只有一个。我还希望能够在两个方向上遍历这个集合，同时也进行排序，或者允许我使用 Collections.Sort();

对其进行排序

我没有找到合适的东西，不得不使用以下代码编写自己的 class：

public class UniqueArrayList<E> extends ArrayList<E> {
    @Override
    public boolean add(E element){
        if (this.contains(element))
            return false;
        else
            return super.add(element);
    }

    @Override
    public void add(int index, E element){
        if (this.contains(element))
            return;
        else
            super.add(index, element);
    }

    @Override
    public boolean addAll(Collection<? extends E> c){
        if (new HashSet<E>(c).size() < c.size())
            return false;
        for(E element : c){
            if (this.contains(c))
                return false;
        }
        return super.addAll(c);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        if (new HashSet<E>(c).size() < c.size())
            return false;
        for(E element : c){
            if (this.contains(c))
                return false;
        }
        return super.addAll(index, c);
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > this.size())
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

    @Override
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size();
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size())
                throw new NoSuchElementException();
            Object[] elementData = UniqueArrayList.this.toArray();
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                UniqueArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }


    }

    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = UniqueArrayList.this.toArray();
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                //Need to allow this for the collections sort to work!
                //if (!UniqueArrayList.this.contains(e))
                UniqueArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                UniqueArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }
}

然而，这远非完美，因为我无法覆盖 ListIterator.set();，因为 Collections.sort(); 使用它来移动列表中的项目。如果我试图阻止将非唯一项目添加到此处的列表中，则排序永远不会发生。

那么，有没有人有更好的方法或知道另一个遵守我想要的规则的集合？还是我只需要忍受这个相当恼人的问题？

[编辑]

这是Collections.sort();方法：

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

他们这样做的理由是：

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n² log(n) performance that would result from attempting to sort a linked list in place.

Answer 1

当您需要唯一值时，您应该尝试切换到集合。您可以将 TreeSet 与 Comparator 实例一起使用来对条目进行排序。 TreeSet 的 descendingSet() 方法将为您提供相反的顺序。如果你在某个时候真的需要一个 ListIterator，你可以从集合中创建一个临时列表。

Answer 2

Java 认为 List 允许非唯一项，而 Set 不允许。集合显然不支持 ListIterators，因此使用 ListIterator 的代码可以假定基础集合不是 Set.

Java 8 不再使用 ListIterator 进行排序，但如果您坚持使用 Java 7，那对您没有任何帮助。基本上在很大程度上取决于您的上下文和用法，使用 Set 可能会很有用，就像 Thor Stan 在他的回复中所说的那样，在需要时按需创建 List。

另一种选择是仅提供您自己的 ListIterator，它通过不检查重复项的方法访问列表。这将具有不创建无关对象的优势，但 Set 选项很可能会导致代码更短，并且不太可能在性能方面产生重大影响。

可能还有其他选择，但我想不出任何优雅的选择。

Answer 3

这是一个没有简单答案的问题。

问题是您违反了 add(int, E) 的合同。此方法必须添加元素或抛出异常 - 不允许 return 不添加元素。

如果您重写 set(int, E) 以便有时它不会设置元素，它也会违反该方法的约定，并且会阻止 Collections.sort() 像您确定的那样工作。

我不建议违反这些约定 - 它可能会导致作用于列表的其他方法以不可预测的方式运行。

其他人遇到过这些困难 - 例如，请参阅 SetUniqueList 的 java 文档。

您实施的另一个问题是它会非常慢，因为 ArrayList.contains() 是线性搜索。

一个解决方案是编写一个同时使用 ArrayList 和 HashSet 的 class，然后编写您自己的 add 和 [=18= 版本]，而不是破坏通常版本的合同。这没有经过测试，但你明白了。

public final class MyList<E extends Comparable<? super E>> extends AbstractList<E> {

    private final List<E> list = new ArrayList<>();
    private final Set<E> set = new HashSet<>();

    public E get(int i) {
        return list.get(i);
    }

    public int size() {
        return list.size();
    } 

    public boolean tryAdd(E e) {
        return set.add(e) && list.add(e);
    }

    public boolean tryAdd(int i, E e) {
        if (set.add(e)) {
            list.add(i, e);
            return true;
        }
        return false;
    }

    public boolean trySet(int i, E e) {
        return set.add(e) && set.remove(list.set(i, e));
    }

    public boolean remove(Object o) {
        return set.remove(o) && list.remove(o);
    }

    public void sort() {
        Collections.sort(list);
    }

    // One bonus of this approach is that contains() is now O(1)
    public boolean contains(Object o) {
        return set.contains(o);
    }

    // rest omitted.
}

这样的事情不会破坏 List 的合同。请注意，对于此版本，add 和 set 抛出 UnsupportedOperationException，因为这是从 AbstractList 继承的行为。您可以通过调用 myList.sort() 来 sort。此外，listIterator 方法可以工作，但您不能将它用于 set 或 add（尽管 remove 可以工作）。

如果在遍历此 List 时需要 add 或 set 元素，则需要使用显式索引，而不是 ListIterator。就个人而言，我不认为这是一个主要问题。 ListIterator 对于像 LinkedList 这样没有恒定时间 get 方法的列表是必需的，但是对于 ArrayList 它很好但不是必需的。

Answer 4

如所述，TreeSet 可以满足您的大部分需求。它确保元素是唯一的，它使它们保持排序，并且您可以使用 iterator() 或 descendingIterator().

在任一方向上迭代它

虽然您要求 ListIterator 的原因并不完全清楚。关于 ListIterator 的大多数事情都与位置有关：索引的概念，或者在当前位置添加一些东西，或者设置当前元素。这些对于排序集没有意义。

不过，您可能正在寻找的 ListIterator 的一个方面是在迭代过程中反转方向的能力。您不能直接使用 TreeSet 迭代器执行此操作，因为它仅通过普通 Iterator 而不是 ListIterator.

提供访问权限

但是，TreeSet 实现了 NavigableSet 接口，它允许您按顺序从任一方向单步执行元素。 NavigableSet 接口是 SortedSet 的子接口，它提供了 first() 和 last() 方法让您从集合的 "ends" 之一开始。一旦集合中有了一个元素，就可以使用 lower(E) 和 higher(E) 方法向任一方向移动。或者，如果你想从中间的某个地方开始，你不能通过索引从一个位置开始，但你可以从一个值（不需要是集合的成员）开始，然后调用 lower(E)或 higher(E).

例如：

    TreeSet<String> set = new TreeSet<>(
        Arrays.asList("a", "z", "b", "y"));
    String cur;

    cur = set.first();     // a
    cur = set.higher(cur); // b
    cur = set.higher(cur); // y
    cur = set.higher(cur); // z
    cur = set.lower(cur);  // y
    cur = set.lower(cur);  // b
    cur = set.lower(cur);  // a
    cur = set.lower(cur);  // null

使用 ListIterator 且是唯一列表的集合

Collection that uses ListIterator and is a unique list

java

collections

list

set

java-7

[编辑]