設置和列表接口的Java組合

我有一個數據結構，目前我使用的是一個ArrayList。我意識到，在這個結構中，我不希望有任何重複出現。我的第一個想法是使用某種形式的集合，但是順序也很重要。在搜索了一下Google搜索文檔後，我發現LinkedHashSet幾乎完成了這項工作。不幸的是，維持秩序的主要原因之一是因爲我正在使用ArrayList的get(int index)方法進行隨機訪問，我看不到任何解決方法。設置和列表接口的Java組合

更簡潔 - 我需要一個保存順序並允許隨機訪問的集合。到目前爲止，我所看到的這些類都沒有提供這種功能。有人知道有這樣的課程，還是我必須自己做？如果是後一種情況，那麼在創建人們都知道的這樣一個結構時是否有任何缺陷？

（或者，檢查和刪除重複的快速和容易的方式形成一個ArrayList或類似的結構就足夠了）

編輯：爲清楚起見，它是元素被添加到這一點很重要列表中的順序，他們沒怎麼彼此比較

來源

2011-10-15 James

使用TreeMap 。 –

你可以在你的類型和整數之間使用雙向映射。 http://commons.apache.org/collections/api-3.1/org/apache/commons/collections/BidiMap.html這樣，您可以確保唯一性並快速查找。不過，您將需要一個全局計數器用於新的整數鍵。 –

@Maurício：這不行。地圖允許重複的值。限制僅限於鑰匙。 – BalusC

我只是延長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()方法符合the contract：

確保此collection包含指定的元素（可選操作）。如果此集合因呼叫而改變，則返回true。（如果此集合不允許重複且已包含指定元素，則返回false。）

來源

2011-10-16 01:02:32 BalusC

如果客戶端使用這種類型作爲List，他們是否可以插入重複項來破壞Set重合項被刪除的重合項？ – Raedwald

這樣做會很不方便：ArrayList.contains（）執行順序搜索;也就是說，如果您有一百萬個元素，並且需要再添加一個元素，則必須進行一百萬次比較。 –

SetUniqueList從公共資源的集合：

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

（不幸的是，公共的集合仍然不支持泛型，所以你必須要抑制警告他）

來源

2011-10-15 21:56:22 Bozho

它使用內部Set來執行存在檢查，所以它在速度方面是一個足夠好的解決方案，即使它會花費一點額外的內存。 –

如何創建一個將ArrayList作爲其後備存儲的AbstractList的子類，覆蓋大多數方法將它們委託給後臺存儲，並且重寫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); 
    } 
}

來源

2011-10-15 21:56:54 pholser

集不拋出異常。他們取代了這個元素。 – Bozho

如果你要走這條路線，並且內存效率不是最重要的，你可以同時保留'ArrayList'和'HashSet'作爲後備存儲。如果你走這條路線，只有刪除操作 - 「remove（int）'和'remove（Object）'等 - 將是O（n）。 –

Duh：P好吧，我非常厚我可以擴展ArrayList和ovveride add（）來拒絕重複項，我甚至不需要備份列表。這個答案指出了這一點。 – James

您可以使用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();} 
}

來源

2011-10-15 21:59:07 Vlad

如果集合實現了'List'接口 – Bozho

設置和列表接口的Java組合

回答

相關問題