Java Set 和 List 接口的组合

Question

我有一个数据结构，目前我正在使用 ArrayList。我意识到在这个结构中我不希望出现任何重复项。我的第一个想法是使用某种形式的集合，但是顺序也很重要。经过一番谷歌搜索并搜索 Collections 文档后，我发现 LinkedHashSet 几乎可以完成这项工作。不幸的是，保留顺序的主要原因之一是因为我使用 ArrayList 的 get(int index) 方法进行随机访问，并且我看不到任何解决此问题的方法。

更简洁 - 我需要一个保留顺序并允许随机访问的集合。到目前为止，我所见过的类都没有提供此功能。有谁知道提供此服务的课程，还是我必须自己制作？如果是后一种情况，在创建人们意识到的这种结构时是否存在任何陷阱？

（或者，一种快速简单的方法来检查和删除 ArrayList 或类似结构中的重复项就足够了）

编辑：为了清楚起见，重要的是元素添加到列表的顺序，而不是它们如何相互比较

Answer 1

SetUniqueList 来自 commons-collections：（

List<Foo> uniqueList = SetUniqueList.decorate(new ArrayList<Foo>());

不幸的是，commons-collections 仍然不支持泛型，所以你必须在此处抑制警告）

Answer 2

我只是扩展ArrayList。

public class SetList<E> extends ArrayList<E> {

    @Override
    public boolean add(E e) {
        return contains(e) ? false : super.add(e);
    }

    @Override
    public void add(int index, E e) {
        if (!contains(e)) {
            super.add(index, e);
        }
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size(), c);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        Collection<E> copy = new ArrayList<E>(c);
        copy.removeAll(this);
        return super.addAll(index, copy);
    }

}

请注意，add()方法符合合同：

确保此集合包含指定的元素（可选操作）。如果此集合因调用而发生更改，则返回 true。 （如果此集合不允许重复且已包含指定元素，则返回 false。）

Answer 3

如何创建 AbstractList 的子类，将 ArrayList 作为其后备存储，重写大多数方法以将它们委托给后备存储，并重写 add() 以拒绝重复项？

class NoDupesList<E> extends AbstractList<E> {
    private final List<E> backing;

    NoDupesList() {
        backing = new ArrayList<E>();
    }

    public E get(int index) {
        return backing.get(index);
    }

    // ...

    public boolean contains(Object o) {
        return backing.contains(o);
    }

    public boolean add(E e) {
        if (contains(e))
            throw new IllegalArgumentException("duplicates disallowed: " + e):

        return backing.add(e);
    }
 }

Answer 4

您可以一起使用 ArrayList 和 HashMap：

import java.util.*;

class AS<T>{

    private HashMap<T, Integer> m = new HashMap<T, Integer>();
    private ArrayList<T> a = new ArrayList<T>();

    public void add(T object){
        if (!m.containsKey(object)){
            m.put(object, a.size());
            a.add(object);
        }
    }
    public void remove(T object){
        Integer i = m.get(object);
        if (i!=null){
            a.remove(i.intValue());
            m.remove(object);
        }
    }
    public void remove(int index){
        m.remove(a.get(index));
        a.remove(index);
    }
    public T get(int index){
        return a.get(index);
    }

    public String toString(){return a.toString();}
}