2

退屈だったので、IEnumerable を使用して List の実装をゼロから作成することにしました。正直なところ、解決方法がわからないいくつかの問題に遭遇しました。

  1. インデックスが null またはデフォルト (T) に設定されている場合、ジェネリック配列 (T[]) のサイズをどのように変更しますか?
  2. T を null にすることはできないため、値がデフォルトで 0 である数値プリミティブの問題をどのように解決しますか?
  3. #2 に関して何もできない場合、数値データ型を使用しているときに GetEnumerator() メソッドが 0 を返すのをどのように停止しますか?

最後になりましたが、配列のダウンサイジングに関する標準的な方法は何ですか? アップサイジングの最善の解決策の 1 つは、現在の長さを 2 のべき乗で増やすことであることは確かです。縮小する場合、いつ縮小しますか? Remove/RemoveAtごと、または現在使用されている長さ% 2?

これまでに行ったことは次のとおりです。

public class List<T> : IEnumerable<T>
{
    T[] list = new T[32];
    int current;

    public void Add(T item)
    {
        if (current + 1 > list.Length)
        {
            T[] temp = new T[list.Length * 2];
            Array.Copy(list, temp, list.Length);
            list = temp;
        }

        list[current] = item;
        current++;
    }

    public void Remove(T item)
    {
        for (int i = 0; i < list.Length; i++)
            if (list[i].Equals(item))
                list[i] = default(T);
    }

    public void RemoveAt(int index)
    {
        list[index] = default(T);
    }

    public IEnumerator<T> GetEnumerator()
    {
        foreach (T item in list)
            if (item != null && !item.Equals(default(T)))
                yield return item;
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        foreach (T item in list)
            if (item != null && !item.Equals(default(T)))
                yield return item;
    }
}

前もって感謝します。

4

2 に答える 2

5

まず、RemoveandRemoveAtメソッドは と同じ動作を実装しませんList<T>。List<T>はサイズが 1 減少しますListが、あなたのサイズは一定のままです。より高いインデックスの値を、削除されたオブジェクトから 1 つ低いインデックスにシフトする必要があります。

また、GetEnumerator値に関係なく、配列内のすべての項目を反復処理します。

あなたが抱えているすべての問題を解決できると信じています。誰かが adefault(T)をリストに追加すると、が anであり 0 であるか、クラス型で であるdefault(T)かに関係なく、 a が再び取り出されます。Tintnull

最後に、ダウンサイジングについて: 一部の拡張可能な配列の実装では、配列が非常に大きくなったことがある場合、通常よりも再び大きくなる可能性が高いと合理化されています。そのため、ダウンサイジングを特に避けています。

于 2013-08-28T01:07:52.043 に答える
4

あなたが直面している重要な問題は、内部配列を維持することと、 remove が何をするかです。 List<T>は部分配列を内部的にサポートしていません。できないというわけではありませんが、そうするのははるかに複雑です。正確に模倣List<T>するには、配列と、実際に使用される配列内の要素数 (配列の長さ以下のリストの長さ) のフィールドを保持する必要があります。

追加は簡単です。あなたがしたように要素を最後に追加します。

削除はより複雑です。末尾から要素を削除する場合は、末尾の要素を に設定しdefault(T)、リストの長さを変更します。最初または途中から要素を削除する場合は、配列の内容をシフトし、最後の要素を に設定する必要がありますdefault(T)。最後の要素を に設定する理由はdefault(T)、参照をクリアするためであり、「使用中」かどうかを判断できるようにするためではありません。配列内の位置と保存されたリストの長さに基づいて、それが「使用中」であるかどうかがわかります。

実装のもう 1 つの鍵は、列挙子です。リストの長さに達するまで、最初の要素をループします。null をスキップしないでください。

これは完全な実装ではありませんが、開始したメソッドの正しい実装である必要があります。

ところで、私は同意しません

アップサイジングの最善の解決策は、現在の長さを 2 のべき乗で増やすことであることは確かです。

これは のデフォルトの動作ですList<T>が、すべての状況で最適なソリューションではありません。まさにそれが理由ですList<T>容量を指定できます。ソースからリストをロードしていて、追加するアイテムの数がわかっている場合は、リストの容量を事前に初期化してコピーの数を減らすことができます。同様に、既定のサイズよりも大きい、またはさらに大きくなる可能性のある数百または数千のリストを作成している場合、リストを同じサイズになるように事前に初期化すると、メモリ使用率が向上する可能性があります。そうすれば、それらが割り当てて解放するメモリは同じ連続ブロックになり、より効率的に割り当てと割り当て解除を繰り返し行うことができます。たとえば、実行ごとに約 300,000 のリストを作成するレポート計算エンジンがあり、1 秒間に多くの実行が行われます。リストは常にそれぞれ数百のアイテムであることがわかっているため、すべてのリストを 1024 の容量に事前に初期化します。これはほとんどのニーズを超えていますが、

    public class MyList<T> : IEnumerable<T>
    {
        T[] list = new T[32];
        int listLength;

        public void Add(T item)
        {
            if (listLength + 1 > list.Length)
            {
                T[] temp = new T[list.Length * 2];
                Array.Copy(list, temp, list.Length);
                list = temp;
            }

            list[listLength] = item;
            listLength++;
        }

        public void Remove(T item)
        {
            for (int i = 0; i < list.Length; i++)
                if (list[i].Equals(item))
                {
                    RemoveAt(i);
                    return;
                }
        }

        public void RemoveAt(int index)
        {
            if (index < 0 || index >= listLength)
            {
                throw new ArgumentException("'index' must be between 0 and list length.");
            }

            if (index == listLength - 1)
            {
                list[index] = default(T);
                listLength = index;
                return;
            }

            // need to shift the list
            Array.Copy(list, index + 1, list, index, listLength - index + 1);
            listLength--;
            list[listLength] = default(T);
        }

        public IEnumerator<T> GetEnumerator()
        {                
            for (int i = 0; i < listLength; i++)
            {
                yield return list[i];
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
于 2013-08-28T01:10:13.180 に答える