如何正確使用Java泛型爲ADT的數組實現

我想教我的學生使用Java泛型的正確方法。我正在教一個數據結構課程，所以我希望它們能夠處理數組和自己的鏈表，而不是與Java集合（例如沒有ArrayList）。一個典型的問題是爲ADT提供一個數組實現。下面是一個例子，我試圖使用一個實現爲數組的堆來提供優先級隊列。我願意支持任何形式的優先級隊列中的數據對象，所以我用一個通用的我開始與接口：如何正確使用Java泛型爲ADT的數組實現

public interface PriQue<E> { 
    void insert(int pri, E data); 
    E remove(); // return null when empty 
    boolean isEmpty(); 
}

然後，我實現了它：

public class ArrayHeap<E> implements PriQue<E> { 
//private class Entry<E> { hides E of ArrayHeap which means remove fails 
    private class Entry { // uses E of ArrayHeap 
     int pri; 
     E data; 
    . . . 
    } // end of Entry 
    Entry heap[]; 
    int cnt; 
    public ArrayHeap(int size) { 
     // heap = new Entry[size]; can not create generic array error 
     // heap = (Entry[])new Object[size]; blows up on a cast error 
     heap = (Entry[])new Object[size]; 
     cnt = 0; 
    } 
    . . . 
    public E remove() { 
     E tmp = (E)heap[--cnt].getData(); //bad don't want to cast 
     // trickle down code here 
     return tmp; 
    }

由於接口是參數化我在實現類中使用了相同的泛型 - 我認爲這很好。我需要創建一個包含優先級和相應數據項的條目數組。所以我創建了一個私人課程。這裏我的問題開始了。如果我離開參數，那麼因爲它是ArrayHeap的一部分，它應該在那裏選擇E泛型。當我嘗試創建一個Entry數組時，這會編譯但爆炸。或者，我可以爲Entry指定一個明確的通用參數。如果我選擇E，它會從ArrayHeap中「隱藏」E，並且當我試圖從數組中刪除E時，它不會意識到它與ArrayHeap E相同。如果我將其命名爲V，則它不能將E分配給V，我不能存儲任何數據。我認爲這是實現數據結構的一個相當常見的情況。
我試過閱讀http://www.angelikalanger.com/GenericsFAQ/FAQSections/ParameterizedTypes.html#FAQ104 但它沒有涵蓋嵌套類（主要是關於什麼不起作用）我試過閱讀Java集合地圖實現的代碼，但我沒有看到有什麼不同。

來源

2014-03-12 JMHunt

你用_own_泛型類型聲明你的內部類 - 說'V'。然後，當你聲明_instance_如果內部類使用'E' - 'Entry heap [];'。這是當你設置'V'等於'E'。舉一個例子，看一看[AbstractMap的源代碼]（http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/AbstractMap。 Java），它具有完全相同的模式。你不能創建通用數組;這是你看來的主要問題。 –

如何'刪除（）'失敗，當你使用'入境''而不是Entry'？ –

你看過GrepCode上HashMap的源代碼嗎？它使用帶泛型的嵌套類：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.Entry另外，我當你說「應該在那裏選擇E泛型」時，不明白你的意思。你能澄清嗎？ – mttdbrd

這爲我工作：

public class ArrayHeap<E> implements PriQue<E> { 
    private static class Entry<E> { 
     int pri; 
     E data; 

     // ... 

     public E getData() { 
      return data; 
     } 
    } 

    Entry<E>[] heap; 
    int cnt; 

    public ArrayHeap(int size) { 
     heap = (Entry<E>[])new Entry<?>[size]; 
     // or: heap = new Entry[size]; 
     cnt = 0; 
    } 

    public E remove() { 
     E tmp = heap[--cnt].getData(); 
     return tmp; 
    } 

    // ... 
}

的關鍵是Entry改變成爲一個靜態嵌套類，而不是一個非靜態內部類（這仍依賴於您的外部類的類型參數）。然後你可以創建一個Entry<?>的數組，並從中進行演員陣容。

來源

2014-03-12 16:13:45

你甚至可以執行'Entry [] heap = new Entry [size]'並交換強制轉換以產生編譯器警告。值得指出的是OP應該也停止使用遺留數組表示法。 –

@BoristheSpider是的，的確如此。（事實上，即使演員陣容也會導致編譯器警告。） –

@BoristheSpider我已經實現了你的建議，謝謝！ –

問題是因爲Java在編譯時擦除泛型類型參數，所以創建一個包含泛型類型的數組是不安全的。你需要在某個地方進行演員表演：你可以做的最好的事情就是將其隱藏在輔助功能中。

例如，如果您看一下ArrayList的JDK實現，您會發現它的核心是一個Object[]。

來源

2014-03-12 16:11:58

我很清楚，在編譯時間結束時刪除泛型類型的決定，是爲了避免必須更新被認爲廣泛分佈的JVM，意味着Java中的所有東西（除primatives之外）都會以運行時的Object結尾。問題是 - 這個問題是否足以使用Java來教授ADT。鑑於Java集合類似乎工作正常，似乎有辦法做到這一點。 – JMHunt

如何正確使用Java泛型爲ADT的數組實現

回答

相關問題